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
No comments:
Post a Comment