How to verify if g is a generator for p?












3












$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







share|improve this question









$endgroup$








  • 1




    $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
    14 hours ago










  • $begingroup$
    @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
    $endgroup$
    – Ken
    13 hours ago










  • $begingroup$
    You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
    $endgroup$
    – puzzlepalace
    13 hours 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
    12 hours 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
    12 hours ago
















3












$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







share|improve this question









$endgroup$








  • 1




    $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
    14 hours ago










  • $begingroup$
    @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
    $endgroup$
    – Ken
    13 hours ago










  • $begingroup$
    You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
    $endgroup$
    – puzzlepalace
    13 hours 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
    12 hours 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
    12 hours ago














3












3








3





$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







share|improve this question









$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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 15 hours ago









KenKen

312




312








  • 1




    $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
    14 hours ago










  • $begingroup$
    @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
    $endgroup$
    – Ken
    13 hours ago










  • $begingroup$
    You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
    $endgroup$
    – puzzlepalace
    13 hours 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
    12 hours 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
    12 hours ago














  • 1




    $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
    14 hours ago










  • $begingroup$
    @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
    $endgroup$
    – Ken
    13 hours ago










  • $begingroup$
    You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
    $endgroup$
    – puzzlepalace
    13 hours 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
    12 hours 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
    12 hours ago








1




1




$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
14 hours 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
14 hours ago












$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
13 hours ago




$begingroup$
@puzzlepalace sorry, I'm still confused about q. Where do I actually get the q?
$endgroup$
– Ken
13 hours ago












$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
$endgroup$
– puzzlepalace
13 hours ago




$begingroup$
You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = frac{p-1}{2}$ is also prime.
$endgroup$
– puzzlepalace
13 hours 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
12 hours 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
12 hours 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
12 hours 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
12 hours ago










2 Answers
2






active

oldest

votes


















5












$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.






share|improve this answer









$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
    14 hours 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
    14 hours ago












  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    14 hours ago










  • $begingroup$
    @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
    $endgroup$
    – Ilmari Karonen
    11 hours ago








  • 1




    $begingroup$
    What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
    $endgroup$
    – orlp
    8 hours ago



















3












$begingroup$

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well



Step 1:



Verify that $0leqslant g lt p$ and $(g,p)=1$



In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.



Where $g$ is the element of the group in question and p is the modulus being used (or: $mathbb{Z}_p$).



Step 2:



Calculate $phi(p)$ where $phi$ is the Totient Function. If it happens that $p$ is prime, $phi(p)=p-1$



Then break $phi(p)$ into it's prime factors such that $phi(p)=prodlimits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



Verify that $g^{phi(p)/q_i}notequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbb{Z}_p$.






share|improve this answer








New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
    $endgroup$
    – Ken
    2 hours ago













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
});


}
});














draft saved

draft discarded


















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

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









5












$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.






share|improve this answer









$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
    14 hours 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
    14 hours ago












  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    14 hours ago










  • $begingroup$
    @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
    $endgroup$
    – Ilmari Karonen
    11 hours ago








  • 1




    $begingroup$
    What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
    $endgroup$
    – orlp
    8 hours ago
















5












$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.






share|improve this answer









$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
    14 hours 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
    14 hours ago












  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    14 hours ago










  • $begingroup$
    @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
    $endgroup$
    – Ilmari Karonen
    11 hours ago








  • 1




    $begingroup$
    What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
    $endgroup$
    – orlp
    8 hours ago














5












5








5





$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.






share|improve this answer









$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.







share|improve this answer












share|improve this answer



share|improve this answer










answered 15 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
    14 hours 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
    14 hours ago












  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    14 hours ago










  • $begingroup$
    @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
    $endgroup$
    – Ilmari Karonen
    11 hours ago








  • 1




    $begingroup$
    What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
    $endgroup$
    – orlp
    8 hours 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
    14 hours 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
    14 hours ago












  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    14 hours ago










  • $begingroup$
    @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
    $endgroup$
    – Ilmari Karonen
    11 hours ago








  • 1




    $begingroup$
    What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
    $endgroup$
    – orlp
    8 hours 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
14 hours 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
14 hours 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
14 hours 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
14 hours ago














$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
14 hours ago




$begingroup$
Thank you so much @poncho
$endgroup$
– Ken
14 hours ago












$begingroup$
@Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
$endgroup$
– Ilmari Karonen
11 hours ago






$begingroup$
@Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself.
$endgroup$
– Ilmari Karonen
11 hours ago






1




1




$begingroup$
What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
$endgroup$
– orlp
8 hours ago




$begingroup$
What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply?
$endgroup$
– orlp
8 hours ago











3












$begingroup$

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well



Step 1:



Verify that $0leqslant g lt p$ and $(g,p)=1$



In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.



Where $g$ is the element of the group in question and p is the modulus being used (or: $mathbb{Z}_p$).



Step 2:



Calculate $phi(p)$ where $phi$ is the Totient Function. If it happens that $p$ is prime, $phi(p)=p-1$



Then break $phi(p)$ into it's prime factors such that $phi(p)=prodlimits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



Verify that $g^{phi(p)/q_i}notequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbb{Z}_p$.






share|improve this answer








New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
    $endgroup$
    – Ken
    2 hours ago


















3












$begingroup$

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well



Step 1:



Verify that $0leqslant g lt p$ and $(g,p)=1$



In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.



Where $g$ is the element of the group in question and p is the modulus being used (or: $mathbb{Z}_p$).



Step 2:



Calculate $phi(p)$ where $phi$ is the Totient Function. If it happens that $p$ is prime, $phi(p)=p-1$



Then break $phi(p)$ into it's prime factors such that $phi(p)=prodlimits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



Verify that $g^{phi(p)/q_i}notequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbb{Z}_p$.






share|improve this answer








New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
    $endgroup$
    – Ken
    2 hours ago
















3












3








3





$begingroup$

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well



Step 1:



Verify that $0leqslant g lt p$ and $(g,p)=1$



In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.



Where $g$ is the element of the group in question and p is the modulus being used (or: $mathbb{Z}_p$).



Step 2:



Calculate $phi(p)$ where $phi$ is the Totient Function. If it happens that $p$ is prime, $phi(p)=p-1$



Then break $phi(p)$ into it's prime factors such that $phi(p)=prodlimits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



Verify that $g^{phi(p)/q_i}notequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbb{Z}_p$.






share|improve this answer








New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$



In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well



Step 1:



Verify that $0leqslant g lt p$ and $(g,p)=1$



In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.



Where $g$ is the element of the group in question and p is the modulus being used (or: $mathbb{Z}_p$).



Step 2:



Calculate $phi(p)$ where $phi$ is the Totient Function. If it happens that $p$ is prime, $phi(p)=p-1$



Then break $phi(p)$ into it's prime factors such that $phi(p)=prodlimits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



Verify that $g^{phi(p)/q_i}notequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbb{Z}_p$.







share|improve this answer








New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this answer



share|improve this answer






New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









answered 8 hours ago









TryingToPassCollegeTryingToPassCollege

411




411




New contributor




TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






TryingToPassCollege is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
    $endgroup$
    – Ken
    2 hours ago




















  • $begingroup$
    Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
    $endgroup$
    – Ken
    2 hours ago


















$begingroup$
Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
$endgroup$
– Ken
2 hours ago






$begingroup$
Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to.
$endgroup$
– Ken
2 hours ago




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Bruad Bilen | Luke uk diar | NawigatsjuunCommonskategorii: BruadCommonskategorii: RunstükenWikiquote: Bruad

Image
Öömrang ArtiikelKultuurIidj an drankHoonwerk ualhuuchsjiiskualgermaanskurnweederkwegelssees Wikiquote: Bruad (function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003EFersteegu003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="frr" dir="ltr"u003Eu003Cdiv id="sitenotice"u003Enu003Ccenteru003Enu003Ctable class="rahmenfarbe4" style="border-style: solid; border-width: thin; width: 70%;"u003Ennu003Ctbodyu003Eu003Ctru003Enu003Ctd style="text-align:center;"u003Eu003Ca href="/wiki/Datei:Nordfriesischeflagge.svg" class="image"u003Eu003Cimg alt="Nordfriesischeflagge.svg" src="//upload.wikimedia.or...
Read more

Færeyskur hestur Heimild | Tengill | Tilvísanir | LeiðsagnarvalRossið - síða um færeyska hrossið á færeyskuGott ár hjá færeyska hestinum

Image
FæreyjarHestar færeyskahjaltlandshestinumíslenski hesturinnBretlandskolanámumenskuWikipediafæreyskuWikipediaRossið - síða um færeyska hrossið á færeysku Færeyskur hestur Úr Wikipediu, frjálsa alfræðiritinu Jump to navigation Jump to search Rani og Grani. Grani í vetrarfeldi. Færeyski hesturinn (færeyska: Føroyska rossið ) er hestur sem hefur lifað í Færeyjum í hundruði ára. Hann er smágerður, 120-132 cm á hæð, og helst skyldur hjaltlandshestinum. Hlutverk hans var að draga vagna og plóg og bera klyfjar. Hann hefur fjórar gangtegundir eins og íslenski hesturinn (þar með talið tölt) og er með fjölda litaafbrigði. Nú til dags er hann notaður til frístunda. Í lok 19. aldar voru til um 800 hross. Mö...
Read more

He _____ here since 1970 . Answer needed [closed]What does “since he was so high” mean?Meaning of “catch birds for”?How do I ensure “since” takes the meaning I want?“Who cares here” meaningWhat does “right round toward” mean?the time tense (had now been detected)What does the phrase “ring around the roses” mean here?Correct usage of “visited upon”Meaning of “foiled rail sabotage bid”It was the third time I had gone to Rome or It is the third time I had been to Rome

Image
Engineer refusing to file/disclose patents Extending the spectral theorem for bounded self adjoint operators to bounded normal operators Do varchar(max), nvarchar(max) and varbinary(max) columns affect select queries? Why is it that I can sometimes guess the next note? What linear sensor for a keyboard? Why don’t women say שלא עשני גויה and שפחה, according to Ashkenazim? Did arcade monitors have same pixel aspect ratio as TV sets? anything or something to eat Query about absorption line spectra Can I use my Chinese passport to enter China after I acquired another citizenship? Fuse symbol on toroidal transformer Create all possible words using a set or letters Does the Mind Blank spell prevent the target from being frightened? Can I sign legal documents with a smiley face? When quoting, must I also copy hyphens used to divide words that continue on the next line? ...
Read more