here you go, Pat (and anyone else interested)

[tsukikage]

lab 3 details
lab3.scm

[RELEVANT CODE]
;;;; Lab 3 - Due 2/9 In Lab
;;;;
;;;; Filename: lab3.scm
;;;;
;;;; Name(s): Nastassja Riemermann
;;;;
;;;;
;;;; This file is organized as follows. The file is
;;;; broken into parts for each problem. The first part
;;;; is an empty skeleton of the procedures you are
;;;; to right for that problem. After this the test cases
;;;; are defined, followed by a line that should look like
;;;;
;;;; ;(do-tests ...)
;;;;
;;;; Uncomment this line to run the test cases for that problem
;;;; and the display the resulting output. You are encouraged
;;;; to use this mechanism and add additional test cases of your
;;;; own.

(define (reload) ; type (reload) into interpreter to reload this file
(load "lab3.scm"))


;;; Code used for testing - just ignore this!
(define (do-tests n)
(let* ((& string-append)
(println (lambda (x) (display x) (newline)))
;;Eval that works in MIT, PLT, STk, STKlos
(mit-eval (lambda (exp) (eval exp user-initial-environment)))
(eval+ (lambda (exp) ((if (eq? #f ()) mit-eval eval) exp)))
(print-eval (lambda (exp) (println exp) (println (eval+ exp))))
(case-num (number->string n)))
(println (& "\n--- Beging Test Cases for Step " case-num " ---"))
(for-each print-eval (eval+ (string->symbol (& "test-cases-step-" case-num))))
(println (& "--- End Test Cases for Step " case-num " ---"))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; USEFUL CODE FOR TESTING PRIME NUMBERS from text

(define (square x) (* x x))

(define (smallest-divisor n)
(find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
(= (remainder b a) 0))

(define (prime? n)
(= n (smallest-divisor n)))


(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))))

(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(if (= n 1)
#t
(try-it (+ 1 (random (- n 1))))))

(define (fast-prime? n times)
(cond ((= times 0) #t)
((fermat-test n) (fast-prime? n (- times 1)))
(else #f)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; LIBRARY CODE PROVIDED BY Dr. DAN BOLEY
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;; ----------------------------------------------------------
;;;; These functions implement modular inverse - Dan Boley
;;;; ----------------------------------------------------------

(define (modular-inverse a n) ;; compute b s.t. a*b = 1 mod n, if it exists.
(let ((result (egcd n a)))
(if (= (cadr result) 1) ;; check if inverse exists
(modulo (caddr result) n)
#F))) ;; return FALSE if inverse does not exist.

(define (egcd a b) ;; return list (s g t) s.t. a s + b t = g = gcd(a,b)
;; extended GCD
(cond ((or (< a 0) (< b 0)) (error "egcd cannot handle negative args"))
((< a b) (reverse (egcd b a)))
((= b 0) (list 1 a 0))
((= b 1) (list 0 1 1))
(else
(let* ((q (quotient a b))
(r (modulo a b))
(w (egcd b r)))
(list (caddr w)
(cadr w)
(- (car w) (* q (caddr w))))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Relationships for RSA encryption

;; Pick numbers p and q
;; p = A large prime number
;; q = Another large prime number

;; Calculage m and n
;; n = p * q
;; m = (p-1) * (q-1)

;; Pick e - must be between 1 and n, relatively prime to m
;; 1 < e < n
;; gcd(e,m) = 1

;; Compute d - 'multiplicative inverse' of e
;; (d * e) mod m = 1

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Step 4

;; Check to see if the given parameters satisfy the above requirements

(define (valid-for-RSA? p q e d)
(let ((m (* (- p 1) (- q 1))))
(and (prime? p)
(prime? q)
(= (gcd m e) 1)
(= (modulo (* d e) m) 1))))

(define test-cases-step-4
'(
(valid-for-RSA? 61 53 17 2753) ; #t
(valid-for-RSA? 6781 765931 217 276) ; #f
))


; (do-tests 4)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Step 5

(define (find-e p q)
(let ((m (* (- p 1) (- q 1)))
(n (* p q)))
(define (find-e-iter e)
(let ((d (modular-inverse e m)))
(cond ((= e n) #f)
((and (= (gcd e m) 1)
(not (= d #f))) e)
(find-e-iter (+ e 1)))))
(find-e-iter 2)))

(define test-cases-step-5
'(
(find-e 123456789013037 234567890123521) ; 7
(find-e 123456789012419 234567890123471) ; 3
(find-e 789012345123707 678901234512379) ; 5
(find-e 456789012345851 456789012345923) ; 3
(find-e 456789012346049 567890123451671) ; 3
(find-e 567890123452037 567890123452049) ; 3
(find-e 678901234513417 789012345123463) ; 5
(find-e 123456789012419 234567890123521) ; 7
(find-e 123456789012419 234567890123521) ; 7
))

(do-tests 5)
[/RELEVANT CODE]

I'm working on step 5. Step 4 works, at least with respect to the given test cases.

--- Beging Test Cases for Step 5 ---
(find-e 123456789013037 234567890123521)
3
(find-e 123456789012419 234567890123471)
3
(find-e 789012345123707 678901234512379)
3
(find-e 456789012345851 456789012345923)
3
(find-e 456789012346049 567890123451671)
3
(find-e 567890123452037 567890123452049)
3
(find-e 678901234513417 789012345123463)
3
(find-e 123456789012419 234567890123521)
3
(find-e 123456789012419 234567890123521)
3
--- End Test Cases for Step 5 ---

Comments

[budwin.livejournal.com]

functional programming rocks my socks off.

[tsukikage85.livejournal.com]

:-P