Iterative example with my modular inverse method

My way to calculate the modular inverse at least gives a smaller modulus with another inverse to calculate and realized might help to show an iterative example.

Will start with the system which I will copy from my reference post, and then will explain lots, where am not doing so much shown calculation as is tedious. So very wordy post I warn. Less with shown work. Interested readers are invited to work through themselves as I think greatly helps understanding to fill in what I'm leaving out.

Also lets me explain some things a bit differently. Here is the system:

 r^-1 = (n-1)(r + 2my₀) - 2md mod N

Where y₀ is chosen as is m, with m not equal to r, and n and d are to be determined. They are found from:

2mdF₀ = [F₀(n-1) - 1](r + 2my₀) mod N

and

F₀ = r(r+2my₀) mod N

---------------------------------------------------

Copied from my post: Modular Inverse Innovation

It is also derived there.

Importantly you have variables that follow from: x² - m²y² = F

And you're solving for n and d, with other variables picked. Where I've tended to pick m such that m² is greater than N, though is NOT clear if that is necessary. Is a new area I just found.

I do know that m should not equal r though. So let's try it all with N = 851 = 23(37).

I tend to let y₀ = 1, where that is just for easy. Later research may indicate other more useful values. And will let m = 31, as that squared is greater than N and I like primes. Not necessary for m to be prime though.

Oh, and let's let r = 97. I like using primes because things won't work if r shares factors with N, of course as then the modular inverse does not exist! So helps me just using primes often.

Now can calculate F₀, which is: 97(97+2(31)) mod 851.

So F₀ = 105 mod 851.

Plugging everything in and reducing things and simplifying, I get:

298d = 325n - 166 mod 851

So now to solve for n can just find: 325n - 166 = 0 mod 298

That is: 27n = 166 mod 298, so now I need the modular inverse...oh wait. I notice that 298 - 166 has 3 as a factor, so can get:

9n = -44 mod 298

Oh, then I got clever. If we let n = 2z, then: 9z = -22 mod 149, as can divide 2 across everything.

So now finally, can look for modular inverse of 9, modulo 149. It works. Not in the mood to put all that here though. But just use the system already given and this time it just gives the answer without further iteration needed. Turns out 9^-1 = 116 mod 149. Where just get the answer that time without needing to iterate further.

Will leave as an exercise for the reader to get to: n = -38 mod 851, d = -42 mod 851

(I think.)

Where since is modular algebra those aren't the only ones that will work. But I liked them because they're small. Also shows you can use negative as well as positive, of course.

Then r^-1 = -39(159) - 62(-42) mod 851

And r^-1 = 658 mod 851. And 97(658) = 1 mod 851 as required.

I think that's all ok, as to how it works. Copying from notes so may be minor errors here or there.

Main point is: you definitely get to a smaller modulus as went from 851 to 149. And also can just iterate with THIS method, so it will solve for the modular inverse.

Lots of research room though for best techniques.

And I noted some open questions, like what is best choice for m? Or y₀? And does it matter to work more to pick a smaller F₀? I just went with whatever. You can fiddle with things to make coefficients of n and d as small as possible, I'd think!

So much room for further research.


James Harris