To recap, I found that given x

^{3}- Dy

^{3}= 1, I could solve for y with:

3(2y+r)

^{2}= 4r

^{-1 }- r

^{2}mod D-1

where x = y+r mod D-1, and r is a residue which has a modular inverse modulo D-1.

So I'll arbitrarily use a situation where I have a solution, which is D=26, as x=3, y=1 works.

Then: 3(2y+r)

^{2}= 4r

^{-1 }- r

^{2}mod 25, and I'll try r=1, so (2y+1)

^{2}= 1 mod 25.

Which gives 2y + 1 = 1 or -1 mod 25. So y = 0 or -1 mod 25, which works trivially.

Moving to r=2.

3(2y+2)

^{2}= 4(13)

^{ }- (2)

^{2}mod 25 = 23 mod 25, so (2y+2)

^{2}= 16 mod 25.

Which gives two solutions. One is 2y + 2 = 4 mod 25, so y = 1 mod 25.

For the other 2y = -4 mod 25, so y = 22 mod 25, then x = 24 mod 25.

And (24)

^{3}- 26(22)

^{3}= -263024 = 1 - (10521)(25) = 1 mod 25 as required.

James Harris

## No comments:

Post a Comment