diff options
Diffstat (limited to 'modulo-arithmetic.rkt')
| -rw-r--r-- | modulo-arithmetic.rkt | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/modulo-arithmetic.rkt b/modulo-arithmetic.rkt new file mode 100644 index 0000000..5d80e6c --- /dev/null +++ b/modulo-arithmetic.rkt @@ -0,0 +1,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 /)))
\ No newline at end of file |