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

4 views (last 30 days)
Noor Fatima on 7 Oct 2022
Commented: Walter Roberson on 11 Oct 2022
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.
Noor Fatima on 7 Oct 2022
@Walter Roberson Thank you, but is there any builtin function in Matlab for that?

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
##### 2 CommentsShowHide 1 older comment
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

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.
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.

### Categories

Find more on Number Theory in Help Center and File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by