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?

Unreliable Magic - Is it worth it?

Can the discrete variable be a negative number?

What is the opposite of 'gravitas'?

Is a stroke of luck acceptable after a series of unfavorable events?

Why Were Madagascar and New Zealand Discovered So Late?

What is the intuitive meaning of having a linear relationship between the logs of two variables?

Flow chart document symbol

Is this apparent Class Action settlement a spam message?

Two monoidal structures and copowering

What does "I’d sit this one out, Cap," imply or mean in the context?

How do scammers retract money, while you can’t?

Term for the "extreme-extension" version of a straw man fallacy?

Is HostGator storing my password in plaintext?

Tiptoe or tiphoof? Adjusting words to better fit fantasy races

What happens if you roll doubles 3 times then land on "Go to jail?"

How long to clear the 'suck zone' of a turbofan after start is initiated?

How do I rename a Linux host without needing to reboot for the rename to take effect?

India just shot down a satellite from the ground. At what altitude range is the resulting debris field?

System.debug(JSON.Serialize(o)) Not longer shows full string

Valid Badminton Score?

What is the difference between "behavior" and "behaviour"?

Is exact Kanji stroke length important?

How to pronounce the slash sign

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?



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?













4












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










share|improve this question









$endgroup$







  • 2




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










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










  • $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
    yesterday










  • $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
    yesterday










  • $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
    yesterday















4












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










share|improve this question









$endgroup$







  • 2




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










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










  • $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
    yesterday










  • $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
    yesterday










  • $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
    yesterday













4












4








4





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










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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked yesterday









KenKen

362




362







  • 2




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










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










  • $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
    yesterday










  • $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
    yesterday










  • $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
    yesterday












  • 2




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










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










  • $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
    yesterday










  • $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
    yesterday










  • $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
    yesterday







2




2




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




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












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




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












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




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












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




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












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




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










3 Answers
3






active

oldest

votes


















6












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










  • $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
    yesterday











  • $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    yesterday










  • $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
    yesterday







  • 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
    yesterday


















4












$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: $mathbbZ_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_iq_i^r_i$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



(This notation simply implies that $phi(p)$ is to be broken down into it's prime factors $q_i$ such that $phi(p)=q_1^r_1times q_2^r_2times ...$)



Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$



Ignore the power $r_i$ for this calculation.



Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.




Example:



Let $p=101$, $g=2$.



Step 1:



$0leqslant 2 lt 101$ $checkmark$



and



$(2,101) = 1$ $checkmark $



Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).



Step 2



Calculate $phi(p)=p-1=phi(101)=101-1=100$ (Assuming $p$ is prime).



Now that we know $phi(101)=100$, we can break it down into it's prime factors. Check that:



$100=2^2times5^2$



This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.



Finally, we check:



$2^phi(101)/q_1=2^(101-1)/2=2^50equiv100notequiv1(mod 101)checkmark$
$2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(mod 101)checkmark$



$therefore g$ is a generator $mod 101$.



(Read: therefore $g$ is a generator $mod 101$.)



Note that this process is to be done $forall q_i$, in our case there were only two.



(Read: note that this process is to be done for all $q_i$...)




In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).






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
    23 hours ago











  • $begingroup$
    @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
    $endgroup$
    – TryingToPassCollege
    15 hours ago










  • $begingroup$
    Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
    $endgroup$
    – poncho
    13 hours ago



















0












$begingroup$

$p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $1, 2, q, 2q$, corresponding respectively to




  • $g equiv 1 pmod p$,


  • $g equiv -1 pmod p$,


  • $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h notin 0,pm1$ such that $g equiv h^2 pmod p$, and


  • $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^(p - 1)/2 bmod p = g^q bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a equiv b equiv 3 pmod 4$, whereas $(a|b) = (b|a)$ if either $a equiv 1 pmod 4$ or $b equiv 1 pmod 4$.




  • $3 equiv p equiv 3 pmod 4$, so $(3|p) = -(p|3) = -p^(3 - 1)/2 bmod 3 = -p^1 bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.


  • $5 equiv 1 pmod 4$, so $(5|p) = (p|5) = p^(5 - 1)/2 bmod 5 = p^2 bmod 5 = 4 bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.

  • The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p equiv pm 1 pmod 8$. In this case, $p equiv 3 pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.





share|improve this answer











$endgroup$












    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

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    6












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










    • $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
      yesterday











    • $begingroup$
      Thank you so much @poncho
      $endgroup$
      – Ken
      yesterday










    • $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
      yesterday







    • 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
      yesterday















    6












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










    • $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
      yesterday











    • $begingroup$
      Thank you so much @poncho
      $endgroup$
      – Ken
      yesterday










    • $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
      yesterday







    • 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
      yesterday













    6












    6








    6





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









    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
      yesterday










    • $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
      yesterday











    • $begingroup$
      Thank you so much @poncho
      $endgroup$
      – Ken
      yesterday










    • $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
      yesterday







    • 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
      yesterday
















    • $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
      yesterday










    • $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
      yesterday











    • $begingroup$
      Thank you so much @poncho
      $endgroup$
      – Ken
      yesterday










    • $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
      yesterday







    • 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
      yesterday















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




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












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





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













    $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    yesterday




    $begingroup$
    Thank you so much @poncho
    $endgroup$
    – Ken
    yesterday












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





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





    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
    yesterday




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











    4












    $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: $mathbbZ_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_iq_i^r_i$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



    (This notation simply implies that $phi(p)$ is to be broken down into it's prime factors $q_i$ such that $phi(p)=q_1^r_1times q_2^r_2times ...$)



    Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$



    Ignore the power $r_i$ for this calculation.



    Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.




    Example:



    Let $p=101$, $g=2$.



    Step 1:



    $0leqslant 2 lt 101$ $checkmark$



    and



    $(2,101) = 1$ $checkmark $



    Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).



    Step 2



    Calculate $phi(p)=p-1=phi(101)=101-1=100$ (Assuming $p$ is prime).



    Now that we know $phi(101)=100$, we can break it down into it's prime factors. Check that:



    $100=2^2times5^2$



    This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.



    Finally, we check:



    $2^phi(101)/q_1=2^(101-1)/2=2^50equiv100notequiv1(mod 101)checkmark$
    $2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(mod 101)checkmark$



    $therefore g$ is a generator $mod 101$.



    (Read: therefore $g$ is a generator $mod 101$.)



    Note that this process is to be done $forall q_i$, in our case there were only two.



    (Read: note that this process is to be done for all $q_i$...)




    In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).






    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
      23 hours ago











    • $begingroup$
      @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
      $endgroup$
      – TryingToPassCollege
      15 hours ago










    • $begingroup$
      Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
      $endgroup$
      – poncho
      13 hours ago
















    4












    $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: $mathbbZ_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_iq_i^r_i$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



    (This notation simply implies that $phi(p)$ is to be broken down into it's prime factors $q_i$ such that $phi(p)=q_1^r_1times q_2^r_2times ...$)



    Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$



    Ignore the power $r_i$ for this calculation.



    Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.




    Example:



    Let $p=101$, $g=2$.



    Step 1:



    $0leqslant 2 lt 101$ $checkmark$



    and



    $(2,101) = 1$ $checkmark $



    Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).



    Step 2



    Calculate $phi(p)=p-1=phi(101)=101-1=100$ (Assuming $p$ is prime).



    Now that we know $phi(101)=100$, we can break it down into it's prime factors. Check that:



    $100=2^2times5^2$



    This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.



    Finally, we check:



    $2^phi(101)/q_1=2^(101-1)/2=2^50equiv100notequiv1(mod 101)checkmark$
    $2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(mod 101)checkmark$



    $therefore g$ is a generator $mod 101$.



    (Read: therefore $g$ is a generator $mod 101$.)



    Note that this process is to be done $forall q_i$, in our case there were only two.



    (Read: note that this process is to be done for all $q_i$...)




    In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).






    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
      23 hours ago











    • $begingroup$
      @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
      $endgroup$
      – TryingToPassCollege
      15 hours ago










    • $begingroup$
      Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
      $endgroup$
      – poncho
      13 hours ago














    4












    4








    4





    $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: $mathbbZ_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_iq_i^r_i$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



    (This notation simply implies that $phi(p)$ is to be broken down into it's prime factors $q_i$ such that $phi(p)=q_1^r_1times q_2^r_2times ...$)



    Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$



    Ignore the power $r_i$ for this calculation.



    Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.




    Example:



    Let $p=101$, $g=2$.



    Step 1:



    $0leqslant 2 lt 101$ $checkmark$



    and



    $(2,101) = 1$ $checkmark $



    Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).



    Step 2



    Calculate $phi(p)=p-1=phi(101)=101-1=100$ (Assuming $p$ is prime).



    Now that we know $phi(101)=100$, we can break it down into it's prime factors. Check that:



    $100=2^2times5^2$



    This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.



    Finally, we check:



    $2^phi(101)/q_1=2^(101-1)/2=2^50equiv100notequiv1(mod 101)checkmark$
    $2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(mod 101)checkmark$



    $therefore g$ is a generator $mod 101$.



    (Read: therefore $g$ is a generator $mod 101$.)



    Note that this process is to be done $forall q_i$, in our case there were only two.



    (Read: note that this process is to be done for all $q_i$...)




    In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).






    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: $mathbbZ_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_iq_i^r_i$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.



    (This notation simply implies that $phi(p)$ is to be broken down into it's prime factors $q_i$ such that $phi(p)=q_1^r_1times q_2^r_2times ...$)



    Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$



    Ignore the power $r_i$ for this calculation.



    Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.




    Example:



    Let $p=101$, $g=2$.



    Step 1:



    $0leqslant 2 lt 101$ $checkmark$



    and



    $(2,101) = 1$ $checkmark $



    Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).



    Step 2



    Calculate $phi(p)=p-1=phi(101)=101-1=100$ (Assuming $p$ is prime).



    Now that we know $phi(101)=100$, we can break it down into it's prime factors. Check that:



    $100=2^2times5^2$



    This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.



    Finally, we check:



    $2^phi(101)/q_1=2^(101-1)/2=2^50equiv100notequiv1(mod 101)checkmark$
    $2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(mod 101)checkmark$



    $therefore g$ is a generator $mod 101$.



    (Read: therefore $g$ is a generator $mod 101$.)



    Note that this process is to be done $forall q_i$, in our case there were only two.



    (Read: note that this process is to be done for all $q_i$...)




    In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).







    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








    edited 15 hours ago





















    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 yesterday









    TryingToPassCollegeTryingToPassCollege

    513




    513




    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
      23 hours ago











    • $begingroup$
      @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
      $endgroup$
      – TryingToPassCollege
      15 hours ago










    • $begingroup$
      Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
      $endgroup$
      – poncho
      13 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
      23 hours ago











    • $begingroup$
      @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
      $endgroup$
      – TryingToPassCollege
      15 hours ago










    • $begingroup$
      Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
      $endgroup$
      – poncho
      13 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
    23 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
    23 hours ago













    $begingroup$
    @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
    $endgroup$
    – TryingToPassCollege
    15 hours ago




    $begingroup$
    @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps.
    $endgroup$
    – TryingToPassCollege
    15 hours ago












    $begingroup$
    Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
    $endgroup$
    – poncho
    13 hours ago





    $begingroup$
    Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x bmod n$ is all members of $mathbbZ_n^*$
    $endgroup$
    – poncho
    13 hours ago












    0












    $begingroup$

    $p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $1, 2, q, 2q$, corresponding respectively to




    • $g equiv 1 pmod p$,


    • $g equiv -1 pmod p$,


    • $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h notin 0,pm1$ such that $g equiv h^2 pmod p$, and


    • $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

    If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^(p - 1)/2 bmod p = g^q bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a equiv b equiv 3 pmod 4$, whereas $(a|b) = (b|a)$ if either $a equiv 1 pmod 4$ or $b equiv 1 pmod 4$.




    • $3 equiv p equiv 3 pmod 4$, so $(3|p) = -(p|3) = -p^(3 - 1)/2 bmod 3 = -p^1 bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.


    • $5 equiv 1 pmod 4$, so $(5|p) = (p|5) = p^(5 - 1)/2 bmod 5 = p^2 bmod 5 = 4 bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.

    • The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p equiv pm 1 pmod 8$. In this case, $p equiv 3 pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.





    share|improve this answer











    $endgroup$

















      0












      $begingroup$

      $p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $1, 2, q, 2q$, corresponding respectively to




      • $g equiv 1 pmod p$,


      • $g equiv -1 pmod p$,


      • $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h notin 0,pm1$ such that $g equiv h^2 pmod p$, and


      • $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

      If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^(p - 1)/2 bmod p = g^q bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a equiv b equiv 3 pmod 4$, whereas $(a|b) = (b|a)$ if either $a equiv 1 pmod 4$ or $b equiv 1 pmod 4$.




      • $3 equiv p equiv 3 pmod 4$, so $(3|p) = -(p|3) = -p^(3 - 1)/2 bmod 3 = -p^1 bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.


      • $5 equiv 1 pmod 4$, so $(5|p) = (p|5) = p^(5 - 1)/2 bmod 5 = p^2 bmod 5 = 4 bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.

      • The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p equiv pm 1 pmod 8$. In this case, $p equiv 3 pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.





      share|improve this answer











      $endgroup$















        0












        0








        0





        $begingroup$

        $p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $1, 2, q, 2q$, corresponding respectively to




        • $g equiv 1 pmod p$,


        • $g equiv -1 pmod p$,


        • $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h notin 0,pm1$ such that $g equiv h^2 pmod p$, and


        • $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

        If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^(p - 1)/2 bmod p = g^q bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a equiv b equiv 3 pmod 4$, whereas $(a|b) = (b|a)$ if either $a equiv 1 pmod 4$ or $b equiv 1 pmod 4$.




        • $3 equiv p equiv 3 pmod 4$, so $(3|p) = -(p|3) = -p^(3 - 1)/2 bmod 3 = -p^1 bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.


        • $5 equiv 1 pmod 4$, so $(5|p) = (p|5) = p^(5 - 1)/2 bmod 5 = p^2 bmod 5 = 4 bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.

        • The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p equiv pm 1 pmod 8$. In this case, $p equiv 3 pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.





        share|improve this answer











        $endgroup$



        $p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $1, 2, q, 2q$, corresponding respectively to




        • $g equiv 1 pmod p$,


        • $g equiv -1 pmod p$,


        • $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h notin 0,pm1$ such that $g equiv h^2 pmod p$, and


        • $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

        If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^(p - 1)/2 bmod p = g^q bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a equiv b equiv 3 pmod 4$, whereas $(a|b) = (b|a)$ if either $a equiv 1 pmod 4$ or $b equiv 1 pmod 4$.




        • $3 equiv p equiv 3 pmod 4$, so $(3|p) = -(p|3) = -p^(3 - 1)/2 bmod 3 = -p^1 bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.


        • $5 equiv 1 pmod 4$, so $(5|p) = (p|5) = p^(5 - 1)/2 bmod 5 = p^2 bmod 5 = 4 bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.

        • The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p equiv pm 1 pmod 8$. In this case, $p equiv 3 pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.






        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited 11 hours ago

























        answered 11 hours ago









        Squeamish OssifrageSqueamish Ossifrage

        21.4k13199




        21.4k13199



























            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







            -elgamal-encryption, prime-numbers, rsa

            Popular posts from this blog

            Frič See also Navigation menuinternal link

            Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

            fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox