(2my+r)

^{2}= 3

^{-1}(4Fr

^{-1 }- r

^{2}) mod N

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

where m

^{3}= D mod N, and:

x

^{3}- Dy

^{3}= F, and r = x - my mod N.

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

(2my+r)

^{2}= (4Fr

^{-1 }- r

^{2})/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 }- r

^{2}) 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