Another modular inverse example

Will use my method for calculating the modular inverse and put method at end with link to main post on it.

Will find modular inverse of 41 mod 111. Part of the reason picked is 111 = 3(37) as wanted to check with composites presuming primes would be easier cases.

So r = 41 mod 111, using y₀ = 1, as usual, and m = 11, so D = 10 and N = 111.

F₀ = 41(41 + 2(11)) mod 111 = 41(63) = 30 mod 111

22(30)d = [30(n-1) - 1](41 + 2(11)) mod 111 = [30n - 30 -1](63) = 3n - 66 mod 111

105d = 3n - 66 mod 111

And 3 is a factor can divide through where importantly have to divide the modulus.

35d = n - 22 mod 37, and have a solution with d = 1, and n = 57 mod 37 = 20 mod 37

And turns out that n = 57 mod 111, is what will work next.

r^-1 = (57 - 1)(41 + 2(11)) - 2(11)(1) mod 111 = 56(63) - 22 = 65 mod 111

41(65) = 1 mod 111

And learned the hard way when tried n  = 20, and nothing worked, so of course I panicked, until realized equations were working ok. And had to add the modulus once to get to the correct answer modulo 111.

There are things I do just checking things. Like I just tend to pick m² greater than N for historical reasons. Is necessary? Or even helpful? Does it matter at all? I don't know. And there are possibly easy potential optimizations. An immediate idea is, trying three different values for y₀ and picking smallest results for an iterative case. With my small test examples that hasn't been needed, as usually been easy. But have done an iterative example where didn't show all the work. Would think would be more demonstrative with it, but maybe am too emotional about it.

Like I like to say, emotion and math do not go well together. It's just one of the coolest things ever, and I discovered it? Yup. Hard to process. Seems perfect for computer age too. As an algorithm is nothing hard for a computer. For smaller examples can look more tedious than Euclidean method for a human.

Next will put system and link to main modular inverse post.

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.


James Harris