diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | main.rkt | 44 | ||||
| -rw-r--r-- | modulo-arithmetic.rkt | 38 |
3 files changed, 83 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..e3ca647 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +compiled diff --git a/main.rkt b/main.rkt new file mode 100644 index 0000000..845bd18 --- /dev/null +++ b/main.rkt @@ -0,0 +1,44 @@ +#lang racket + +(require "modulo-arithmetic.rkt") + +;; 4a^3 + 27b^2 != 0 +(define a 2) +(define b 3) + +(define (point-in-curve lst) + (define x (car lst)) + (define y (cadr lst)) + (= (* y y) (+ (* x x x) (* x a) b))) + +(define (add p q) + (cond ((not (point-in-curve p)) + q) + ((not (point-in-curve q)) + p) + (else + (define xp (first p)) + (define xq (first q)) + (define yp (second p)) + (define yq (second q)) + (let* ((m (if (equal? p q) + (/ (+ (* 3 xp xp) a) + (* 2 yp)) + (/ (- yp yq) + (- xp xq)))) + (xr (- (* m m) xp xq)) + (yr (+ yp (* m (- xr xp))))) + (list xr (- yr)))))) + +(define (mul n p) + (cond ((= n 0) + (list 0 0)) + ((= n 1) + p) + (else + (add p (mul (sub1 n) p))))) + +(define curve-points (filter point-in-curve + (cartesian-product (range cardinality) + (range cardinality)))) + 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 |