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

5 Ansichten (letzte 30 Tage)
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 Kommentare
Noor Fatima
Noor Fatima am 7 Okt. 2022
@Walter Roberson Thank you, but is there any builtin function in Matlab for that?

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Walter Roberson
Walter Roberson am 7 Okt. 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 Kommentare
Noor Fatima
Noor Fatima am 9 Okt. 2022
@Walter Roberson Thank you very much.
According to my question it works perfectly fine.
But may i request that it does not work for any prime?
Is the above limited for only m congruent to 3 modulo 4?
Walter Roberson
Walter Roberson am 11 Okt. 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

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (1)

John D'Errico
John D'Errico am 7 Okt. 2022
Bearbeitet: John D'Errico am 7 Okt. 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 Kommentar
Noor Fatima
Noor Fatima am 9 Okt. 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.

Melden Sie sich an, um zu kommentieren.

Kategorien

Mehr zu Matrix Indexing finden Sie in Help Center und File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by