How to verify if g is a generator for p?How large should a Diffie-Hellman p be?Why is it impractical to generate a semiprime dictionary?Help with example RSA problemObtaining Diffie-Hellman generator“Prime conspiracy”'s effect on cryptographyHow is it possible that $g^q equiv 1 pmod p$ for a generator g?What algorithm does .NET use to generate primes for RSA and how can I verify it?How to find a generator g for a large prime p?RSA finding p and q integer with conditionEl-Gamal like encryption, how can i guess the key?
Modulo 2 binary long division in European notation
What would happen if the UK refused to take part in EU Parliamentary elections?
Greatest common substring
Can I convert a rim brake wheel to a disc brake wheel?
Efficiently merge handle parallel feature branches in SFDX
Failed to fetch jessie backports repository
Is there any reason not to eat food that's been dropped on the surface of the moon?
How to verify if g is a generator for p?
Tiptoe or tiphoof? Adjusting words to better fit fantasy races
Using parameter substitution on a Bash array
Opposite of a diet
Go Pregnant or Go Home
Implement the Thanos sorting algorithm
How does a character multiclassing into warlock get a focus?
Is there a problem with hiding "forgot password" until it's needed?
How could Frankenstein get the parts for his _second_ creature?
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?
What is the oldest known work of fiction?
Best way to store options for panels
Your magic is very sketchy
Is there an Impartial Brexit Deal comparison site?
Why did Kant, Hegel, and Adorno leave some words and phrases in the Greek alphabet?
Can I use my Chinese passport to enter China after I acquired another citizenship?
How to verify if g is a generator for p?
How large should a Diffie-Hellman p be?Why is it impractical to generate a semiprime dictionary?Help with example RSA problemObtaining Diffie-Hellman generator“Prime conspiracy”'s effect on cryptographyHow is it possible that $g^q equiv 1 pmod p$ for a generator g?What algorithm does .NET use to generate primes for RSA and how can I verify it?How to find a generator g for a large prime p?RSA finding p and q integer with conditionEl-Gamal like encryption, how can i guess the key?
$begingroup$
For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
rsa prime-numbers elgamal-encryption
asked 2 hours ago
KenKen
261
$endgroup$
add a comment |
$begingroup$
For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
rsa prime-numbers elgamal-encryption
asked 2 hours ago
KenKen
261
$endgroup$
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago
add a comment |
$begingroup$
For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
rsa prime-numbers elgamal-encryption
asked 2 hours ago
KenKen
261
$endgroup$
For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
rsa prime-numbers elgamal-encryption
rsa prime-numbers elgamal-encryption
asked 2 hours ago
KenKen
261
asked 2 hours ago
KenKen
261
asked 2 hours ago
KenKen
261
asked 2 hours ago
KenKen
261
asked 2 hours ago
KenKen
261
261
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago
add a comment |
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^(p-1)/q notequiv 1pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
answered 2 hours ago
ponchoponcho
93.4k2146242
$endgroup$
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5);Is it like this in? In Java.
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68317%2fhow-to-verify-if-g-is-a-generator-for-p%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^(p-1)/q notequiv 1pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
answered 2 hours ago
ponchoponcho
93.4k2146242
$endgroup$
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5);Is it like this in? In Java.
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
add a comment |
$begingroup$
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^(p-1)/q notequiv 1pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
answered 2 hours ago
ponchoponcho
93.4k2146242
$endgroup$
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5);Is it like this in? In Java.
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
add a comment |
$begingroup$
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^(p-1)/q notequiv 1pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
answered 2 hours ago
ponchoponcho
93.4k2146242
$endgroup$
Steps:
Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^(p-1)/q notequiv 1pmod p$
If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.
answered 2 hours ago
ponchoponcho
93.4k2146242
answered 2 hours ago
ponchoponcho
93.4k2146242
answered 2 hours ago
ponchoponcho
93.4k2146242
answered 2 hours ago
ponchoponcho
93.4k2146242
93.4k2146242
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5);Is it like this in? In Java.
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
add a comment |
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5);Is it like this in? In Java.
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler?
$endgroup$
– Ken
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
@Ken: Compute $g^2685735182215186/2 bmod p$. Compute $g^2685735182215186/1342867591107593 bmod p$. If they are both something other than 1, then $g$ is a generator
$endgroup$
– poncho
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5); Is it like this in? In Java.$endgroup$
– Ken
1 hour ago
$begingroup$
public class generator public static void main (String[] args) long p = 2685735182104907l; long p2 = p - 1; long p3 = p2 / 2; long p4 = 2 ^ (p2 / 2) % p; long p5 = 2 ^ (p2 / p3) % p; System.out.println(p4); System.out.println(p5); Is it like this in? In Java.$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
1 hour ago
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68317%2fhow-to-verify-if-g-is-a-generator-for-p%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer).
$endgroup$
– puzzlepalace
1 hour ago
$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
26 mins ago
$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = fracp-12$ is also prime.
$endgroup$
– puzzlepalace
15 mins ago
$begingroup$
@puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime.
$endgroup$
– Ken
6 mins ago
$begingroup$
@puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator?
$endgroup$
– Ken
4 mins ago