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

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.

[Robert U]

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]

@Robert U Thank you for your comment.

Basically, it is a curve b^2 = a^3 + 23698* a + 9684 (mod 36683).

Now I'm interested to find b when input a is given.

[Walter Roberson]

https://www.rieselprime.de/ziki/Modular_square_root

3 mod 4 case applies

[Noor Fatima]

@Walter Roberson Thank you, but is there any builtin function in Matlab for that?

Answer 1

[Walter Roberson]

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

[Noor Fatima]

@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]

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]

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.

[Noor Fatima]

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