Simpler modular form for BQD Iterator

Was surprised to discover that considering x² - Dy² = F mod N, is also the path to a simpler form for my BQD Iterator.

Key is the factorization available from:

x² - Dy² = x² - m²y² = (x-my)(x+my) = F mod N

Where, for some residue r, x + my = r mod N, and x - my = Fr^-1 mod N

And I can iterate to get: x + Dy + m(x + y) = r' mod N

Then x + my + Dy + mx = x + my + m(my+x) = r + mr = r(m+1) = r' mod N

And have the result then: r' = r(m+1) mod N

Then with k iterations, have for kth iteration: r_k = r(m+1)^k mod N

So can use r to iterate modularly with a very simple result.

Where intrigues me is VASTLY simpler than what can get with the explicit form.


James Harris