Monday, March 11, 2013

Generalizing cubic Diophantine solution

Going to consider a cubic Diophantine modulo N adapting a prior post.

Given x3 - Dy3 = F I'll try to find modular solutions for x and y modulo N.

First find m, such that m3 = D mod N, so N must have D as a cubic residue.

For example you can simply find an N using N = m3 - 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:

x3 - Dy3 = F mod N, so:

x3 - m3y3 = F mod N

Which is: (x-my)(x2 + mxy + m2y2) = F mod N, and letting r be any residue with an inverse modulo N:

x-my = r mod N and x2 + mxy + m2y2 = Fr-1 mod N, so, x = my+r mod N, allowing me to substitute:

(my+r)2 + m(my+r)y + m2y2 = Fr-1 mod N

and expanding out gives:

m2y2 + 2myr + r2 + m2y2 + rmy + m2y2 = Fr-1 mod N, so:

3m2y2 + 3myr + r2  -  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:

m2y2 + myr + r2 /4 -  r2 /4+( r2  -  Fr-1 )/3 = 0 mod N,

which is: (my+r/2)2  = -(r2 - 4Fr-1)/12  mod N, so:

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