Quadratic residue structure

You can focus on my cubic residue work in the opposite direction to see quadratic residue structure:

(2my+r)²  = 3^-1(4Fr^-1 - r² ) mod N

if 3 is coprime to N, r is any residue modulo N for which its modular inverse exists,

where m³ = D mod N, and:

 x³ - Dy³ = F, and r = x - my mod N.

If 3 is not coprime to N then you'd simply have:

(2my+r)²  = (4Fr^-1 - r² )/3 mod N

For example, let m=1 and D=1. And let x=2, and y = 1. Then F = 7. And we're set for any N. To use the first let's let N not have 3 as a factor then:

(r+2)²  = 3^-1(28r^-1 - r² ) mod N, and r = 1 mod N

Which works.

The result comes from solving the cubic modulo N, and I realized you could also look in a different direction.


James Harris