Mixing
order of an element modulo safe prime
$begingroup$
I have to find and element of order $frac{p-1}{2}$ in a group with p-1 elements (say in the group of units modulo $p$). Now I know that $p$ is prime and that $frac{p-1}{2}$ is also a prime (that is $p$ is a so called safe prime). I actually have an exact value for $p$ but it is of such magnitude that there is no point writing it here. Now since $p$ is a prime we have that $p-1$ is even and by Lagrange we know that the order of any subgroup has to divide the order of the group. This fact leaves us with 3 choices for possible orders for subgroups in this group, namely $2$, $q$ and $2cdot q=p-1$ where $q=frac{p-1}{2}$. I would like to find an element that definitely has order $neq 2$ and $neq p-1=2q$ cause this will leave us with only one choice. Now since $p$ is greater than say $10^{30}$ the first couple of hundred elements will definitely satisfy that they won't have order $2$ (so we can try with small values like $2,3,4,ldots$). But now I am stuck, how can I find an element that is definitely NOT a generator? (like is there any way to tell that $3$ for example cannot be a generator) Is there any easy ways? Knowing that $p$ is a safe prime?
group-theory
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
$endgroup$
add a comment |
$begingroup$
I have to find and element of order $frac{p-1}{2}$ in a group with p-1 elements (say in the group of units modulo $p$). Now I know that $p$ is prime and that $frac{p-1}{2}$ is also a prime (that is $p$ is a so called safe prime). I actually have an exact value for $p$ but it is of such magnitude that there is no point writing it here. Now since $p$ is a prime we have that $p-1$ is even and by Lagrange we know that the order of any subgroup has to divide the order of the group. This fact leaves us with 3 choices for possible orders for subgroups in this group, namely $2$, $q$ and $2cdot q=p-1$ where $q=frac{p-1}{2}$. I would like to find an element that definitely has order $neq 2$ and $neq p-1=2q$ cause this will leave us with only one choice. Now since $p$ is greater than say $10^{30}$ the first couple of hundred elements will definitely satisfy that they won't have order $2$ (so we can try with small values like $2,3,4,ldots$). But now I am stuck, how can I find an element that is definitely NOT a generator? (like is there any way to tell that $3$ for example cannot be a generator) Is there any easy ways? Knowing that $p$ is a safe prime?
group-theory
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
$endgroup$
3
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
2
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
2
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36
add a comment |
$begingroup$
I have to find and element of order $frac{p-1}{2}$ in a group with p-1 elements (say in the group of units modulo $p$). Now I know that $p$ is prime and that $frac{p-1}{2}$ is also a prime (that is $p$ is a so called safe prime). I actually have an exact value for $p$ but it is of such magnitude that there is no point writing it here. Now since $p$ is a prime we have that $p-1$ is even and by Lagrange we know that the order of any subgroup has to divide the order of the group. This fact leaves us with 3 choices for possible orders for subgroups in this group, namely $2$, $q$ and $2cdot q=p-1$ where $q=frac{p-1}{2}$. I would like to find an element that definitely has order $neq 2$ and $neq p-1=2q$ cause this will leave us with only one choice. Now since $p$ is greater than say $10^{30}$ the first couple of hundred elements will definitely satisfy that they won't have order $2$ (so we can try with small values like $2,3,4,ldots$). But now I am stuck, how can I find an element that is definitely NOT a generator? (like is there any way to tell that $3$ for example cannot be a generator) Is there any easy ways? Knowing that $p$ is a safe prime?
group-theory
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
$endgroup$
I have to find and element of order $frac{p-1}{2}$ in a group with p-1 elements (say in the group of units modulo $p$). Now I know that $p$ is prime and that $frac{p-1}{2}$ is also a prime (that is $p$ is a so called safe prime). I actually have an exact value for $p$ but it is of such magnitude that there is no point writing it here. Now since $p$ is a prime we have that $p-1$ is even and by Lagrange we know that the order of any subgroup has to divide the order of the group. This fact leaves us with 3 choices for possible orders for subgroups in this group, namely $2$, $q$ and $2cdot q=p-1$ where $q=frac{p-1}{2}$. I would like to find an element that definitely has order $neq 2$ and $neq p-1=2q$ cause this will leave us with only one choice. Now since $p$ is greater than say $10^{30}$ the first couple of hundred elements will definitely satisfy that they won't have order $2$ (so we can try with small values like $2,3,4,ldots$). But now I am stuck, how can I find an element that is definitely NOT a generator? (like is there any way to tell that $3$ for example cannot be a generator) Is there any easy ways? Knowing that $p$ is a safe prime?
group-theory
group-theory
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
edited Feb 23 '15 at 12:10
Vinyl_coat_jawa
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
asked Feb 23 '15 at 11:58
Vinyl_coat_jawaVinyl_coat_jawa
2,2311028
2,2311028
3
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
2
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
2
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36
add a comment |
3
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
2
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
2
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36
3
3
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
2
2
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
2
2
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $a$ of $mathbb Z bmod p$. The (multiplicative) order of $a$ must divide the order of the multiplicative group, namely $p-1$.
By assumption (that $p$ is a safe prime) the prime factorization of $p-1$ is $2cdot frac{p-1}{2}$.
So there are very few possibilities for the order of $a$. It could be $1,2,p-1$ or the desired order $frac{p-1}{2}$. We can easily rule out the first two possibilities if we avoid $a^2 equiv 1 bmod p$, since with $p$ prime there are exactly two roots $aequiv pm 1 bmod p$ of that equation.
Now pick any other element $a$ of the multiplicative group. If the order $|a|=p-1$, then we could fix things up by choosing $a^2$ modulo $p$.
In fact unless $p=5$ one can also show that $a^2$ has the desired order $frac{p-1}{2}$ even if $a$ already had order $frac{p-1}{2}$. This is because when $p$ is a safe prime greater than $5$, the factor $frac{p-1}{2}$ is coprime to $2$ (odd, so that squaring $a$ of order $frac{p-1}{2}$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $a^2$, with the obvious exceptions ($p=5$ or $a=0,pm 1$).
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1161534%2forder-of-an-element-modulo-safe-prime%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $a$ of $mathbb Z bmod p$. The (multiplicative) order of $a$ must divide the order of the multiplicative group, namely $p-1$.
By assumption (that $p$ is a safe prime) the prime factorization of $p-1$ is $2cdot frac{p-1}{2}$.
So there are very few possibilities for the order of $a$. It could be $1,2,p-1$ or the desired order $frac{p-1}{2}$. We can easily rule out the first two possibilities if we avoid $a^2 equiv 1 bmod p$, since with $p$ prime there are exactly two roots $aequiv pm 1 bmod p$ of that equation.
Now pick any other element $a$ of the multiplicative group. If the order $|a|=p-1$, then we could fix things up by choosing $a^2$ modulo $p$.
In fact unless $p=5$ one can also show that $a^2$ has the desired order $frac{p-1}{2}$ even if $a$ already had order $frac{p-1}{2}$. This is because when $p$ is a safe prime greater than $5$, the factor $frac{p-1}{2}$ is coprime to $2$ (odd, so that squaring $a$ of order $frac{p-1}{2}$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $a^2$, with the obvious exceptions ($p=5$ or $a=0,pm 1$).
$endgroup$
add a comment |
$begingroup$
For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $a$ of $mathbb Z bmod p$. The (multiplicative) order of $a$ must divide the order of the multiplicative group, namely $p-1$.
By assumption (that $p$ is a safe prime) the prime factorization of $p-1$ is $2cdot frac{p-1}{2}$.
So there are very few possibilities for the order of $a$. It could be $1,2,p-1$ or the desired order $frac{p-1}{2}$. We can easily rule out the first two possibilities if we avoid $a^2 equiv 1 bmod p$, since with $p$ prime there are exactly two roots $aequiv pm 1 bmod p$ of that equation.
Now pick any other element $a$ of the multiplicative group. If the order $|a|=p-1$, then we could fix things up by choosing $a^2$ modulo $p$.
In fact unless $p=5$ one can also show that $a^2$ has the desired order $frac{p-1}{2}$ even if $a$ already had order $frac{p-1}{2}$. This is because when $p$ is a safe prime greater than $5$, the factor $frac{p-1}{2}$ is coprime to $2$ (odd, so that squaring $a$ of order $frac{p-1}{2}$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $a^2$, with the obvious exceptions ($p=5$ or $a=0,pm 1$).
$endgroup$
add a comment |
$begingroup$
For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $a$ of $mathbb Z bmod p$. The (multiplicative) order of $a$ must divide the order of the multiplicative group, namely $p-1$.
By assumption (that $p$ is a safe prime) the prime factorization of $p-1$ is $2cdot frac{p-1}{2}$.
So there are very few possibilities for the order of $a$. It could be $1,2,p-1$ or the desired order $frac{p-1}{2}$. We can easily rule out the first two possibilities if we avoid $a^2 equiv 1 bmod p$, since with $p$ prime there are exactly two roots $aequiv pm 1 bmod p$ of that equation.
Now pick any other element $a$ of the multiplicative group. If the order $|a|=p-1$, then we could fix things up by choosing $a^2$ modulo $p$.
In fact unless $p=5$ one can also show that $a^2$ has the desired order $frac{p-1}{2}$ even if $a$ already had order $frac{p-1}{2}$. This is because when $p$ is a safe prime greater than $5$, the factor $frac{p-1}{2}$ is coprime to $2$ (odd, so that squaring $a$ of order $frac{p-1}{2}$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $a^2$, with the obvious exceptions ($p=5$ or $a=0,pm 1$).
$endgroup$
For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $a$ of $mathbb Z bmod p$. The (multiplicative) order of $a$ must divide the order of the multiplicative group, namely $p-1$.
By assumption (that $p$ is a safe prime) the prime factorization of $p-1$ is $2cdot frac{p-1}{2}$.
So there are very few possibilities for the order of $a$. It could be $1,2,p-1$ or the desired order $frac{p-1}{2}$. We can easily rule out the first two possibilities if we avoid $a^2 equiv 1 bmod p$, since with $p$ prime there are exactly two roots $aequiv pm 1 bmod p$ of that equation.
Now pick any other element $a$ of the multiplicative group. If the order $|a|=p-1$, then we could fix things up by choosing $a^2$ modulo $p$.
In fact unless $p=5$ one can also show that $a^2$ has the desired order $frac{p-1}{2}$ even if $a$ already had order $frac{p-1}{2}$. This is because when $p$ is a safe prime greater than $5$, the factor $frac{p-1}{2}$ is coprime to $2$ (odd, so that squaring $a$ of order $frac{p-1}{2}$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $a^2$, with the obvious exceptions ($p=5$ or $a=0,pm 1$).
edited Jan 2 at 0:07
community wiki
2 revs
hardmath
add a comment |
add a comment |
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.
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%2f1161534%2forder-of-an-element-modulo-safe-prime%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
3
$begingroup$
What can you say about the order of $a^2$?
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:13
2
$begingroup$
thanks, now I have to live with the burden that I havent seen this before :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 12:20
2
$begingroup$
If I had a dollar for every time ...
$endgroup$
– Daniel Fischer♦
Feb 23 '15 at 12:22
$begingroup$
Being a poor student I can only contribute with an online hug...but an honest one :)
$endgroup$
– Vinyl_coat_jawa
Feb 23 '15 at 17:36