Initial CommitHEADmain

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