If one coordinate of the point is given how to find another coordinate?

4 views (last 30 days)
if a = 9361;
How to find b such that
b^2 = (9361)^3 + 23698* 9361 + 9684 (mod 36683)
I have tried the following
b^2 = mod((9361)^3 + 23698* 9361 + 9684 , 36683);
% To check if it is quadratic residue
mod(b^2,1)==0
The answer is 24669, but I'm not getting what should I do after the above steps.
  4 Comments

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 7 Oct 2022
Symbolic Toolbox, obscure function that is no longer documented
format long g
a = 9361;
m = 36683;
b2 = a^3 + 23698* a + 9684
b2 =
820510559543
b = feval(symengine, 'numlib::sqrtmodp', b2, m)
b = 
8366
%verify
mod(b^2, m) - mod(b2, m)
ans = 
0
If your values exceed flintmax then you have to take more care in calculating them in the first place; https://www.mathworks.com/matlabcentral/answers/489379-square-roots-mod-p-also-mupad-functionality#answer_400010
  2 Comments
Walter Roberson
Walter Roberson on 11 Oct 2022
It is limited to odd primes (that is, it does not handle 2), but it is not limited to 4k+3
format long g
a = 9361;
m = 36697;
mod(m,4) %verify that it is 4k+1 not 4k+3
ans =
1
b2 = a^3 + 23698* a + 9684
b2 =
820510559543
b = feval(symengine, 'numlib::sqrtmodp', b2, m)
b = 
3494
%verify
mod(b^2, m) - mod(b2, m)
ans = 
0

Sign in to comment.

More Answers (1)

John D'Errico
John D'Errico on 7 Oct 2022
Edited: John D'Errico on 7 Oct 2022
This reduces to the so called modular square root problem. That is, solve for x, such that
mod(x^2,p) == r
where p and r are given values. The solution can be gained from the Shanks-Tonelli algorithm, here:
A problem is this is more difficult if p is composite.
isprime(36683)
ans = logical
1
But here, p is indeed prime, so a solution may exist. That is not always true, as you seem to understand. Your problem is to solve for b, such that:
b^2 = (9361)^3 + 23698* 9361 + 9684 (mod 36683)
First, expand the right hand side, as
p = 36683;
rhs = mod((9361)^3 + 23698* 9361 + 9684,p)
rhs = 35475
Note that p is a prime of the form 4*k+3.
mod(p,4)
ans = 3
In that case, a simple, direct solution exists as:
x = powermod(sym(rhs),(p+1)/4,p)
x = 
8366
Is this a valid solution?
mod(x^2,p) == rhs
ans = 
Yes. Only in the case where p is a prime of the form 4*k+1 do you need to dive into Shanks-Tonelli. As I recall, it is not that difficult to write. I've got the code somewhere, but it is implemented using my VPI toolbox. I might have written a version that works under sym. Not sure about that. Anyway, this is irrelevant, as long as p is a prime of the form 4*k+3.
Again, if p is composite, things get messier yet.
  1 Comment
Noor Fatima
Noor Fatima on 9 Oct 2022
@John D'Errico thank you very much for your valuable comments. It works fine.
And according to my question, your code works perfectly fine.
But now stuck with pimes which are not 3 under modulo 4.
Anyways thanks a lot.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by