More on finding quadratic residues with modular inverse

Last month started pondering if one could find quadratic residues using the modular inverse.

Copying much from my post last month will update also as answer a question raised then.

Focused on x² - Dy² = F, where for some integer N, will be true that D is a quadratic residue, such that D = m² mod N, for some m.

Which means have a useful factorization available:

x² - Dy² = x² - m²y² = (x-my)(x+my) = F mod N

Where then, for some residue r, x + my = r mod N, and x - my = Fr^-1 mod N

Can solve for x, as: 2x = r + Fr^-1 mod N, and 2my =  r - Fr^-1 mod N

If I simply pick r, then get its modular inverse, and set F, then I have set x.

Get to set some variables, like simply set F = 1 mod N and will set y, and then find D, from:

D = (x² - 1)y^-2 mod N.

Noticed before that WILL work, but also wondered if could use BQD Iterator, to possibly get different values for m, and realized that MIGHT change r, but how to know?

From the start: 2x = r + Fr^-1 mod N

The BQD Iterator will give next: 2(x+Dy) = r + F(-D+1)r^-1 mod N

So can just solve. Then r = 2(x+Dy) + F(D - 1)r^-1 mod N, so:

2x = 2(x+Dy) + F(D - 1)r^-1 + Fr^-1 mod N = 2x + 2Dy + FDr^-1 - Fr^-1 + Fr^-1 mod N, so:

0 = 2Dy + FDr^-1 mod N

Assuming D is coprime to N, which is odd, have then: y = -F(2r)^-1 mod N

Which surprised me. But y is free here so can be easily set. Guess you get one iteration then per try?

For example, again let N = 119, and again start with easy with let r = 2 mod 119. Then also r^-1 = 60 mod 119.

So: 2x = 2 + 60 = 62 mod 119, and x = 31 mod 119.

Now there is a change from before as y = -4^-1 mod 119 = 89 mod 119

And 2m(89) = 2 - 60 = -58 mod 119, so: 59m = 61 mod 119, so: m = 116 mod 119

And D = (31² - 1)(16) mod 119 =  9 mod 119

And yeah 116² = 9 mod 119, as required.

Now though can iterate with the BQD Iterator, knowing have same r, which then is way to handle that particular thing.

So next value for x is: 31 + 2(89) mod 119 = 90, and next y is: 31+89 mod 119 = 1 mod 119.

Then 2m' = 2 - 60(-9 +1) mod 119 = 2 - 60(-8) mod 119 = 6 mod 119, so: m' = 3 mod 119

Which is just the negative of the first one. But at least it worked! Cool. There may be potential here. But now I wonder: will it always simply negate?


James Harris