Euclidean algorithm to solve RR' - NN' = 1. Modular exponentiation with Montgomery algorithm to implement Fermat test in python or Petite Chez scheme

Question

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.

Answer 1

The extended Euclidean algorithm is:

(define (euclid x y)
  (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y))
    (if (zero? w) (values a b g)
      (let ((q (quotient g w)))
        (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w)))))))

Thus, on your example,

> (euclid 79 100)
19
-15
1

You can read more at my blog.