blob: 5d80e6c4a6cf881af469353ba0a75b708363b37b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#lang racket
(define cardinality 487) ; must be prime
(define (extended-euclid a b)
(define (euloop r s t)
(if (= 0 (second r))
(list r s t)
(let ((q (quotient (first r) (second r))))
(euloop (list (second r) (- (first r) (* q (second r))))
(list (second s) (- (first s) (* q (second s))))
(list (second t) (- (first t) (* q (second t))))))))
(match (euloop (list a b) (list 1 0) (list 0 1))
((list r s t)
(list (first r) (first s) (first t)))))
(define (inverse n)
(match (extended-euclid n cardinality)
((list gdc x y)
(modulo x cardinality))))
(define (add . args)
(modulo (apply + args) cardinality))
(define (sub . args)
(modulo (apply - args) cardinality))
(define (mul . args)
(modulo (apply * args) cardinality))
(define (div a b)
(mul a (inverse b)))
(provide cardinality
(rename-out (add +)
(sub -)
(mul *)
(div /)))
|
