If one coordinate of the point is given how to find another coordinate?
Show older comments
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
Robert U
on 7 Oct 2022
Hi Noor Fatima,
I do not think the formula you are using represents the original task/question. Please, post the original question. If you have troubles to perform the calculations with Matlab, I recommend to have a look at the language fundamentals: https://de.mathworks.com/help/matlab/language-fundamentals.html.
Kind regards,
Robert
Noor Fatima
on 7 Oct 2022
Walter Roberson
on 7 Oct 2022
Edited: Walter Roberson
on 7 Oct 2022
3 mod 4 case applies
Noor Fatima
on 7 Oct 2022
Accepted Answer
More Answers (1)
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)
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)
Note that p is a prime of the form 4*k+3.
mod(p,4)
In that case, a simple, direct solution exists as:
x = powermod(sym(rhs),(p+1)/4,p)
Is this a valid solution?
mod(x^2,p) == rhs
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
on 9 Oct 2022
Categories
Find more on Mathematics 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!