This is as a personal challenge in my introductory programming class taught using Scheme, but I would be equally happy with Python examples.
I've already implemented the binary method of modular exponentiation in scheme as follows:
(define (pow base expo modu) (if (zero? expo) 1 (if (even? expo) (mod (expt (pow base (/ expo 2) modu) 2) modu) (mod (* base (pow base (sub1 expo) modu)) modu))))
This is necessary as Chez Scheme doesn't have any implementation similar to python's pow (base expo modu).
Now I am trying to implement the Montgomery method of solving modular multiplication. As an example, I have:
Trying to solve: (a * b) % N N = 79 a = 61 b = 5 R = 100 a' = (61 * 100) % 79 = 17 b' = (5 * 100) % 79 = 26 RR' - NN' = 1
I'm trying to understand how to solve RR' - NN' = 1. I realize that the answer to R' should be 64 and N' should be 81, but don't understand how to use the Euclidean Algorithm to get this answer.