Tuesday, June 17, 2014

Quadratic residue structure

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

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

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

where m3 = D mod N, and:

 x3 - Dy3 = F, and r = x - my mod N.

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

(2my+r)2  = (4Fr-1 - r2 )/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)2  = 3-1(28r-1 - r2 ) 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
Post a Comment