If one coordinate of the point is given how to find another coordinate?
1 次查看(过去 30 天)
显示 更早的评论
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.
采纳的回答
Walter Roberson
2022-10-7
Symbolic Toolbox, obscure function that is no longer documented
format long g
a = 9361;
m = 36683;
b2 = a^3 + 23698* a + 9684
b = feval(symengine, 'numlib::sqrtmodp', b2, m)
%verify
mod(b^2, m) - mod(b2, m)
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 个评论
Walter Roberson
2022-10-11
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
b2 = a^3 + 23698* a + 9684
b = feval(symengine, 'numlib::sqrtmodp', b2, m)
%verify
mod(b^2, m) - mod(b2, m)
更多回答(1 个)
John D'Errico
2022-10-7
编辑:John D'Errico
2022-10-7
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!