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

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 个评论
显示无隐藏无

Noor Fatima 2022-10-9

@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 2022-10-11

在 MATLAB Online 中打开

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

请先登录，再进行评论。

Answer 2

John D'Errico 2022-10-7

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1819325-if-one-coordinate-of-the-point-is-given-how-to-find-another-coordinate#answer_1069155

编辑：John D'Errico 2022-10-7

在 MATLAB Online 中打开

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:

https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm

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.