sicp exercise 1.25

;  Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod.
;  After all, she says, since we already know how to compute exponentials, we could have simply written
;
;     (define (expmod base exp m)
;         (remainder (fast-expt base exp) m))
;
;  Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

; Answer: She is ofcourse wrong. We are not calculating exponentials, we want to calculate the mod
; of a^n by reducing it in terms of mod of a^(n/2).

; Here i want to present my derivation for the procedure expmod

;----------------------------------------------------------------
;
;   Question: find a^n mod m
;
;   Answer:
;          let us begin by finding x*y mod n
;          reduce x*y mod n in simpler terms
;          assume x,y > n , we can write x and y as follows
;          x = Xn + a,   where a < n
;          y = Yn + b,   where b < n
;
;          then x*y = XY*n^2 + (aY + bX)n + ab
;
;          then,
;
;          x*y mod n is equiv to  a*b mod n because other terms have a n factor
;
;          if y=x then,
;
;          x^2 mod n is equiv to  a^2 mod n
;
;          similarily,
;
;          x^m mod n is equiv to  a^m mod n is equiv to  ((a^m/2 mod n)^2  mod n)
;
;   (define (square num) (* num num))
;
;   (define (expmod base exp m)
;       (cond ((= exp 0) 1)
;             ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
;             (else (remainder (* base (expmod base (- exp 1) m)) m))))
;
;   (display (expmod 6 7 7))(newline)
;
;----------------------------------------------------------------