Efficient way to find primitive root without prime factorization
up vote
1
down vote
favorite
1
I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization.
My approach is as follows:
- Get a random residue class $[x]$ smaller than $p$.
- Set
exponentto $1$. - Calculate
result = [x]^exponent mod p. - Check if
resultis $1$. - If
resultis $1$, check ifexponentis $p-1$. - If condition 5 is true, we have found a primitive root.
- If condition 5 is not true, we get a new random residue class $[x]$ smaller than $p$.
- In each iteration, increase
exponentby $1$.
algorithms prime-numbers exponentiation prime-factorization primitive-roots
edited Nov 23 at 11:21
Klangen
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
add a comment |
up vote
1
down vote
favorite
1
I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization.
My approach is as follows:
- Get a random residue class $[x]$ smaller than $p$.
- Set
exponentto $1$. - Calculate
result = [x]^exponent mod p. - Check if
resultis $1$. - If
resultis $1$, check ifexponentis $p-1$. - If condition 5 is true, we have found a primitive root.
- If condition 5 is not true, we get a new random residue class $[x]$ smaller than $p$.
- In each iteration, increase
exponentby $1$.
algorithms prime-numbers exponentiation prime-factorization primitive-roots
edited Nov 23 at 11:21
Klangen
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44
add a comment |
up vote
1
down vote
favorite
1
up vote
1
down vote
favorite
1
1
I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization.
My approach is as follows:
- Get a random residue class $[x]$ smaller than $p$.
- Set
exponentto $1$. - Calculate
result = [x]^exponent mod p. - Check if
resultis $1$. - If
resultis $1$, check ifexponentis $p-1$. - If condition 5 is true, we have found a primitive root.
- If condition 5 is not true, we get a new random residue class $[x]$ smaller than $p$.
- In each iteration, increase
exponentby $1$.
algorithms prime-numbers exponentiation prime-factorization primitive-roots
edited Nov 23 at 11:21
Klangen
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization.
My approach is as follows:
- Get a random residue class $[x]$ smaller than $p$.
- Set
exponentto $1$. - Calculate
result = [x]^exponent mod p. - Check if
resultis $1$. - If
resultis $1$, check ifexponentis $p-1$. - If condition 5 is true, we have found a primitive root.
- If condition 5 is not true, we get a new random residue class $[x]$ smaller than $p$.
- In each iteration, increase
exponentby $1$.
algorithms prime-numbers exponentiation prime-factorization primitive-roots
algorithms prime-numbers exponentiation prime-factorization primitive-roots
edited Nov 23 at 11:21
Klangen
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
edited Nov 23 at 11:21
Klangen
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
edited Nov 23 at 11:21
Klangen
1,25811129
edited Nov 23 at 11:21
Klangen
1,25811129
edited Nov 23 at 11:21
Klangen
1,25811129
1,25811129
asked Oct 26 '15 at 8:35
Pierre
61
asked Oct 26 '15 at 8:35
Pierre
61
asked Oct 26 '15 at 8:35
Pierre
61
61
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44
add a comment |
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Mathematics 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1498166%2fefficient-way-to-find-primitive-root-without-prime-factorization%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $left(Bbb{Z}/pBbb{Z}right)^times$ is guaranteed to be a proper divisor of $p-1$.
– A.P.
Oct 26 '15 at 9:24
From these answers it looks like you are out of luck.
– A.P.
Oct 26 '15 at 9:44