A1(new residue-class-ring 11)B1(new elliptic-curve @b5 @b9)A30B3(new residue-class @a!1! @a3)A41B4(new residue-class @a!1! @a4)A52C4(make-point @b1 @b4 @b6)B5(new residue-class @a!1! @a5)A63B6(new residue-class @a!1! @a6)A74B7(new residue-class @a!1! @a7)A85C7(make-point @b1 @b7 @b13)B8(new residue-class @a!1! @a8)A96C8(make-point @b1 @b8 @b6)B9(new residue-class @a!1! @a9)A107B10(new residue-class @a!1! @a10)A118B11(new residue-class @a!1! @a11)A129B12(new residue-class @a!1! @a12)A1310B13(new residue-class @a!1! @a13)C14(apply + @c3:c13)#| elliptic curve |# (defclass elliptic-curve ()) (defmethod initialize ((this elliptic-curve) (a residue-class) (b residue-class)) (and (same-ring? a b) (not (zero? (+ (* (new residue-class (get-ring a) 4) a a a) (* (new residue-class (get-ring b) 27) b b))))) (progn (.= this a a) (.= this b b) (.= this infinite-point (new infinite-point this)) (freeze this))) (defmethod get-infinite-point ((this elliptic-curve)) t (. this infinite-point)) (defmethod make-point ((this elliptic-curve) (x residue-class) (y residue-class)) t (new finite-point this x y)) (defmethod add-points ((this elliptic-curve) (x1 residue-class) (y1 residue-class) (x2 residue-class) (y2 residue-class)) (not (and (= x1 x2) (= y1 (- (new residue-class (get-ring y2) 0) y2)))) (let ((m (if (= x1 x2) (/ (+ (* (new residue-class (get-ring x1) 3) x1 x1) (. this a)) (+ y1 y1)) (/ (- y2 y1) (- x2 x1))))) (let ((x3 (- (* m m) x1 x2))) (let ((y3 (- (* (- x1 x3) m) y1))) (make-point this x3 y3))))) #| point on elliptic curve or point at infinity |# (deftrait point ()) (defclass finite-point (point)) (defclass infinite-point (point)) (defmethod initialize ((this finite-point) (curve elliptic-curve) (x residue-class) (y residue-class)) (with-slots-read-only (a b) curve (= (* y y) (+ (* x x x) (* a x) b))) (progn (.= this curve curve) (.= this x x) (.= this y y) (freeze this)))) (defmethod initialize ((this infinite-point) (curve elliptic-curve)) t (progn (.= this curve curve) (freeze this))) (defmethod get-curve ((this point)) t (. this curve)) (defmethod same-curve? ((point-1 point) (point-2 point)) t (= (get-curve point-1) (get-curve point-2))) (defmethod add ((point-1 infinite-point) (point-2 point)) (same-curve? point-1 point-2) point-2) (defmethod add ((point-1 point) (point-2 infinite-point)) (same-curve? point-1 point-2) point-1) (defmethod add ((point-1 finite-point) (point-2 finite-point)) (same-curve? point-1 point-2) (let ((curve (get-curve point-1)) (x1 (. point-1 x)) (y1 (. point-1 y)) (x2 (. point-2 x)) (y2 (. point-2 y))) (if (or (and (= x1 x2) (zero? y1) (zero? y2)) (and (= x1 x2) (not (= y1 y2)))) (get-infinite-point curve) (add-points curve x1 y1 x2 y2))))residue-class4local:residue-classKlassen und Methoden für Restklassenringeresidue-class-ring residue-class initialize get-modulus get-ring same-ring? get-value zero? add sub times quotient(defstruct residue-class-ring (modulus) (and (integer? modulus) (greater? modulus 1))) (defmethod get-modulus ((this residue-class-ring)) t (. this modulus)) #| residue class |# (defclass residue-class ()) (defmethod initialize ((this residue-class) (ring residue-class-ring) value) (integer? value) (progn (.= this ring ring) (.= this value (with-slots-read-only (modulus) ring (if (< value 0) (let ((pos-value (+ modulus (rem value modulus)))) (if (= pos-value modulus) 0 pos-value)) (rem value modulus)))) (freeze this))) (defmethod get-ring ((this residue-class)) t (. this ring)) (defmethod get-value ((this residue-class)) t (. this value)) (defmethod same-ring? ((this residue-class) (that residue-class)) t (= (get-ring this) (get-ring that))) (defmethod add ((this residue-class) (that residue-class)) (same-ring? this that) (new residue-class (get-ring this) (+ (get-value this) (get-value that)))) (defmethod sub ((this residue-class) (that residue-class)) (same-ring? this that) (new residue-class (get-ring this) (- (get-value this) (get-value that)))) (defmethod times ((this residue-class) (that residue-class)) (same-ring? this that) (new residue-class (get-ring this) (* (get-value this) (get-value that)))) (defmethod quotient ((this residue-class) (that residue-class)) (same-ring? this that) (new residue-class (get-ring this) (* (get-value this) (catch-and-apply nil (lambda (name value) (throw (quote no-multiplicative-inverse) (get-value that))) (modinv (get-value that) (get-modulus (get-ring this))))))) (defmethod zero? ((this residue-class)) t (zero? (get-value this))) #| unit test |# (assert "4 + 6 = 3 modulo 7" (let ((ring (new residue-class-ring 7))) (= (get-value (+ (new residue-class ring 4) (new residue-class ring 6))) 3))) (assert "1 - 5 = 3 modulo 7" (let ((ring (new residue-class-ring 7))) (= (get-value (- (new residue-class ring 1) (new residue-class ring 5))) 3))) (assert "2 * 4 = 1 modulo 7" (let ((ring (new residue-class-ring 7))) (= (get-value (* (new residue-class ring 2) (new residue-class ring 4))) 1))) (assert "1 / 4 = 2 modulo 7" (let ((ring (new residue-class-ring 7))) (= (get-value (/ (new residue-class ring 1) (new residue-class ring 4))) 2)))elliptic-curveEine elliptische Kurve E(A, B) mit 4 A³ + 27 B² != 0 ist eine Kurve in der Ebene. Sie enthält die Punkte (x y), die die Bedingung y² = x³ + A x + B erfüllen. Instanzen der Klasse elliptic-curve speichern die Parameter a und b der Kurve und eine Instanz des Punktes in der Unendlichkeit. Die Instanzen der Klassen point, finite-point und infinite-point repräsentieren Punkte, entweder auf der Kurve oder den unendlich fernen Punkt. Der Initialisierer für Punkte prüft, ob die Koordinaten des Punkts zur Kurve passen. Die Methode add addiert zwei Punkte.elliptic-curve point initialize make-point add1001100100000110010011111111110011011011011010000010010001011