Given x

^{3}- Dy

^{3}= F I'll try to find modular solutions for x and y modulo N.

First find m, such that m

^{3}= D mod N, so N must have D as a cubic residue.

For example you can simply find an N using N = m

^{3}- D, which is cool so we can simply pick m and force N versus going the other way, figuring things out. So now I have:

x

^{3}- Dy

^{3}= F mod N, so:

x

^{3}- m

^{3}y

^{3}= F mod N

Which is: (x-my)(x

^{2}+ mxy + m

^{2}y

^{2}) = F mod N, and letting r be any residue with an inverse modulo N:

x-my = r mod N and x

^{2}+ mxy + m

^{2}y

^{2}= Fr

^{-1}mod N, so, x = my+r mod N, allowing me to substitute:

(my+r)

^{2}+ m(my+r)y + m

^{2}y

^{2}= Fr

^{-1}mod N

and expanding out gives:

m

^{2}y

^{2}+ 2myr + r

^{2}+ m

^{2}y

^{2}+ rmy + m

^{2}y

^{2}= Fr

^{-1}mod N, so:

3m

^{2}y

^{2}+ 3myr + r

^{2}- Fr

^{-1}= 0 mod N, and I'll use fractions--though it can be done without them--to make things easier for me and complete the square:

m

^{2}y

^{2}+ myr + r

^{2}/4 - r

^{2}/4+( r

^{2}- Fr

^{-1})/3 = 0 mod N,

which is: (my+r/2)

^{2}= -(r

^{2}- 4Fr

^{-1})/12 mod N, so:

3(2my+r)

^{2}= 4Fr

^{-1 }- r

^{2}mod N

Which was easy enough.

Interesting. So you can solve for x and y modulo N, if D is a cubic residue modulo N, F is a cubic residue modulo D if a certain quadratic residue exists, and m has a modular inverse modulo N.

This particular approach could also work for the quartic case, easily enough. But I think that's it though I'm not sure.

James Harris

## No comments:

Post a Comment