summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJuan Manuel Tomás <jtomas1815@gmail.com>2022-08-13 02:14:43 -0300
committerJuan Manuel Tomás <jtomas1815@gmail.com>2022-08-13 02:14:43 -0300
commit817415a43c977bfc90abec58c9bbec348d98b9a6 (patch)
treef978ff18fdf3b75ecb34e7d8962fc0b91d181963
downloadelliptic-817415a43c977bfc90abec58c9bbec348d98b9a6.tar.gz
elliptic-817415a43c977bfc90abec58c9bbec348d98b9a6.zip
Initial CommitHEADmain
-rw-r--r--.gitignore1
-rw-r--r--main.rkt44
-rw-r--r--modulo-arithmetic.rkt38
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