Cryptography: Solve $x^2 equiv 331 pmod385$ using modular arithmetic
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
How can I find (3) congruence equations to solve
$$x^2equiv331pmod385$$
using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to produce the solutions to $x^2equiv331pmod385$
Solution
$$385=5cdot7cdot11$$
$$beginalign
x^2&equiv1pmod5\
x^2&equiv2pmod7\
x^2&equiv1pmod11\[10pt]
x&equiv1,4pmod5\
x&equiv3,4pmod7\
x&equiv1,10pmod11\
endalign$$
$$beginalign
M1implies&385/5=77\
&77-1pmod5=3pmod5\[5pt]
M2implies&385/7=55\
&55-1pmod7=6pmod7\[5pt]
M2implies&385/11=35\
&35-1pmod11=6pmod11\[5pt]
endalign$$
$$a=1,4;quad b=3,4;quad c=1,10$$
$$beginalign
x&equiv acdot77cdot3+bcdot5cdot6+ccdot35cdot6\
&equiv231a+330b+210c
endalign$$
Therefore
Congruence of 8 cases
elementary-number-theory modular-arithmetic cryptography legendre-symbol
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
asked Oct 19 '15 at 23:13
nversusp
83
add a comment |Â
up vote
0
down vote
favorite
How can I find (3) congruence equations to solve
$$x^2equiv331pmod385$$
using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to produce the solutions to $x^2equiv331pmod385$
Solution
$$385=5cdot7cdot11$$
$$beginalign
x^2&equiv1pmod5\
x^2&equiv2pmod7\
x^2&equiv1pmod11\[10pt]
x&equiv1,4pmod5\
x&equiv3,4pmod7\
x&equiv1,10pmod11\
endalign$$
$$beginalign
M1implies&385/5=77\
&77-1pmod5=3pmod5\[5pt]
M2implies&385/7=55\
&55-1pmod7=6pmod7\[5pt]
M2implies&385/11=35\
&35-1pmod11=6pmod11\[5pt]
endalign$$
$$a=1,4;quad b=3,4;quad c=1,10$$
$$beginalign
x&equiv acdot77cdot3+bcdot5cdot6+ccdot35cdot6\
&equiv231a+330b+210c
endalign$$
Therefore
Congruence of 8 cases
elementary-number-theory modular-arithmetic cryptography legendre-symbol
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
asked Oct 19 '15 at 23:13
nversusp
83
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
How can I find (3) congruence equations to solve
$$x^2equiv331pmod385$$
using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to produce the solutions to $x^2equiv331pmod385$
Solution
$$385=5cdot7cdot11$$
$$beginalign
x^2&equiv1pmod5\
x^2&equiv2pmod7\
x^2&equiv1pmod11\[10pt]
x&equiv1,4pmod5\
x&equiv3,4pmod7\
x&equiv1,10pmod11\
endalign$$
$$beginalign
M1implies&385/5=77\
&77-1pmod5=3pmod5\[5pt]
M2implies&385/7=55\
&55-1pmod7=6pmod7\[5pt]
M2implies&385/11=35\
&35-1pmod11=6pmod11\[5pt]
endalign$$
$$a=1,4;quad b=3,4;quad c=1,10$$
$$beginalign
x&equiv acdot77cdot3+bcdot5cdot6+ccdot35cdot6\
&equiv231a+330b+210c
endalign$$
Therefore
Congruence of 8 cases
elementary-number-theory modular-arithmetic cryptography legendre-symbol
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
asked Oct 19 '15 at 23:13
nversusp
83
How can I find (3) congruence equations to solve
$$x^2equiv331pmod385$$
using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to produce the solutions to $x^2equiv331pmod385$
Solution
$$385=5cdot7cdot11$$
$$beginalign
x^2&equiv1pmod5\
x^2&equiv2pmod7\
x^2&equiv1pmod11\[10pt]
x&equiv1,4pmod5\
x&equiv3,4pmod7\
x&equiv1,10pmod11\
endalign$$
$$beginalign
M1implies&385/5=77\
&77-1pmod5=3pmod5\[5pt]
M2implies&385/7=55\
&55-1pmod7=6pmod7\[5pt]
M2implies&385/11=35\
&35-1pmod11=6pmod11\[5pt]
endalign$$
$$a=1,4;quad b=3,4;quad c=1,10$$
$$beginalign
x&equiv acdot77cdot3+bcdot5cdot6+ccdot35cdot6\
&equiv231a+330b+210c
endalign$$
Therefore
Congruence of 8 cases
elementary-number-theory modular-arithmetic cryptography legendre-symbol
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
asked Oct 19 '15 at 23:13
nversusp
83
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
edited Aug 12 at 8:17
Martin Sleziak
43.6k6113259
43.6k6113259
asked Oct 19 '15 at 23:13
nversusp
83
asked Oct 19 '15 at 23:13
nversusp
83
asked Oct 19 '15 at 23:13
nversusp
83
83
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
accepted
$385=5cdot 7cdot 11$
$$beginalign&x^2equiv 1pmod5\ &x^2equiv 2pmod7\ &x^2equiv 1pmod11endalign$$
$$iff beginalign&xequiv 1,4pmod5\ &xequiv 3,4pmod7\ &xequiv 1,10pmod11endalign$$
Now check $8$ cases and use Chinese Remainder Theorem for each case.
answered Oct 19 '15 at 23:19
user236182
11.8k11234
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.2+7 =9 and sqrt is 32+7+7=16 and sqrt is 4
– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
 |Â
show 4 more comments
up vote
0
down vote
Hint. $385 = 5 times 7 times 11$. And if $x^2 equiv 331 pmod385$, then
$$
x^2 equiv 1 pmod5
$$
$$
x^2 equiv ,,? pmod7
$$
$$
x^2 equiv ,,? pmod11
$$
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it bex ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)
– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
$385=5cdot 7cdot 11$
$$beginalign&x^2equiv 1pmod5\ &x^2equiv 2pmod7\ &x^2equiv 1pmod11endalign$$
$$iff beginalign&xequiv 1,4pmod5\ &xequiv 3,4pmod7\ &xequiv 1,10pmod11endalign$$
Now check $8$ cases and use Chinese Remainder Theorem for each case.
answered Oct 19 '15 at 23:19
user236182
11.8k11234
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.2+7 =9 and sqrt is 32+7+7=16 and sqrt is 4
– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
 |Â
show 4 more comments
up vote
0
down vote
accepted
$385=5cdot 7cdot 11$
$$beginalign&x^2equiv 1pmod5\ &x^2equiv 2pmod7\ &x^2equiv 1pmod11endalign$$
$$iff beginalign&xequiv 1,4pmod5\ &xequiv 3,4pmod7\ &xequiv 1,10pmod11endalign$$
Now check $8$ cases and use Chinese Remainder Theorem for each case.
answered Oct 19 '15 at 23:19
user236182
11.8k11234
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.2+7 =9 and sqrt is 32+7+7=16 and sqrt is 4
– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
 |Â
show 4 more comments
up vote
0
down vote
accepted
up vote
0
down vote
accepted
$385=5cdot 7cdot 11$
$$beginalign&x^2equiv 1pmod5\ &x^2equiv 2pmod7\ &x^2equiv 1pmod11endalign$$
$$iff beginalign&xequiv 1,4pmod5\ &xequiv 3,4pmod7\ &xequiv 1,10pmod11endalign$$
Now check $8$ cases and use Chinese Remainder Theorem for each case.
answered Oct 19 '15 at 23:19
user236182
11.8k11234
$385=5cdot 7cdot 11$
$$beginalign&x^2equiv 1pmod5\ &x^2equiv 2pmod7\ &x^2equiv 1pmod11endalign$$
$$iff beginalign&xequiv 1,4pmod5\ &xequiv 3,4pmod7\ &xequiv 1,10pmod11endalign$$
Now check $8$ cases and use Chinese Remainder Theorem for each case.
answered Oct 19 '15 at 23:19
user236182
11.8k11234
answered Oct 19 '15 at 23:19
user236182
11.8k11234
answered Oct 19 '15 at 23:19
user236182
11.8k11234
answered Oct 19 '15 at 23:19
user236182
11.8k11234
11.8k11234
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.2+7 =9 and sqrt is 32+7+7=16 and sqrt is 4
– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
 |Â
show 4 more comments
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.2+7 =9 and sqrt is 32+7+7=16 and sqrt is 4
– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
Won't it be x≡2,5(mod7)
– nversusp
Oct 19 '15 at 23:32
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
No. If $x equiv 2, 5 pmod7$, then $x^2 equiv 4 pmod7$.
– Brian Tung
Oct 19 '15 at 23:45
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
@BrianTung How do you actually get 3,4. Can you explain please?
– nversusp
Oct 19 '15 at 23:51
Nevermind, understood.
2+7 =9 and sqrt is 3 2+7+7=16 and sqrt is 4– nversusp
Oct 19 '15 at 23:55
Nevermind, understood.
2+7 =9 and sqrt is 3 2+7+7=16 and sqrt is 4– nversusp
Oct 19 '15 at 23:55
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
@user236182 can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
 |Â
show 4 more comments
up vote
0
down vote
Hint. $385 = 5 times 7 times 11$. And if $x^2 equiv 331 pmod385$, then
$$
x^2 equiv 1 pmod5
$$
$$
x^2 equiv ,,? pmod7
$$
$$
x^2 equiv ,,? pmod11
$$
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it bex ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)
– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
add a comment |Â
up vote
0
down vote
Hint. $385 = 5 times 7 times 11$. And if $x^2 equiv 331 pmod385$, then
$$
x^2 equiv 1 pmod5
$$
$$
x^2 equiv ,,? pmod7
$$
$$
x^2 equiv ,,? pmod11
$$
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it bex ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)
– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Hint. $385 = 5 times 7 times 11$. And if $x^2 equiv 331 pmod385$, then
$$
x^2 equiv 1 pmod5
$$
$$
x^2 equiv ,,? pmod7
$$
$$
x^2 equiv ,,? pmod11
$$
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
Hint. $385 = 5 times 7 times 11$. And if $x^2 equiv 331 pmod385$, then
$$
x^2 equiv 1 pmod5
$$
$$
x^2 equiv ,,? pmod7
$$
$$
x^2 equiv ,,? pmod11
$$
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
answered Oct 19 '15 at 23:17
Brian Tung
25.3k32453
25.3k32453
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it bex ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)
– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
add a comment |Â
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it bex ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)
– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I understand that is 2 & 1. But How do I prove congruence?
– nversusp
Oct 19 '15 at 23:34
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
I would really appreciate your help?
– nversusp
Oct 19 '15 at 23:41
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
Look at @user236182's answer, which takes the solution a little further.
– Brian Tung
Oct 19 '15 at 23:42
I did. Won't it be
x ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)– nversusp
Oct 19 '15 at 23:44
I did. Won't it be
x ≡ 2,5 (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10)– nversusp
Oct 19 '15 at 23:44
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
can you please verify my solution. I have added it into the questions itself.
– nversusp
Oct 20 '15 at 0:19
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1488294%2fcryptography-solve-x2-equiv-331-pmod385-using-modular-arithmetic%23new-answer', 'question_page');
);
Post as a guest
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
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
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
