Faktorisieren mit elliptischen Kurven
Nach dem Satz von Hasse hat eine elliptische Kurve Ep(A, B) über dem Restklassenring Z/pZ für Primzahlen p (der Restklassenring ist dann ein Primkörper) zwischen p + 1 - 2 √p und p + 1 + 2 √p verschiedene Punkte. Die Zahl der verschiedenen Punkte nennt man Ordnung der Gruppe (Ep(A, B), +).
Aus dem Satz von Lagrange angewendet auf (Ep(A, B), +) folgt, dass wenn die k-fache Addition eines Punkts P != O das neutrale Element O ergibt, also k P = O ist, dann müssen k und die Ordnung der Gruppe einen größten gemeinsamen Teiler ungleich 1 haben. Dieser gemeinsame Teiler ist die Ordnung des Punkts, d.h. das kleinste x für das x P = O ist.
Angenommen, die zu faktorisierende Zahl n ist das Produkt zweier Primzahlen f und g. Die Addition von Punkten erfüllt für die Kurve En(A, B) dann nicht die Gruppeneigenschaften, weil der Restklassenring Z/nZ für zusammengesetzte n kein Körper ist. Das liegt unter anderem daran, dass die Vielfachen von f und g kein multiplikatives Inverses in Z/nZ haben.
Für die kleineren Kurven Ef(A, B) und Eg(A, B) erfüllt die Addition aber die Gruppeneigenschaften, da f und g nach der oben genannten Voraussetzung Primzahlen und Z/fZ und Z/gZ Körper sind.
Eine Addition von Punkten P und Q auf En(A, B) entspricht zwei simultanen Additionen auf Ef(A, B) und Eg(A, B), das ist eine Folgerung des chinesischen Restsatzes und der Voraussetzung n = f g.
Wenn in Ef(A, B) die wiederholte Addition k P = O ergibt, in Eg(A, B) aber k P != O gilt, dann ist k P für En(A, B) nicht definiert und aus dem auftretenden Fehler (das multiplikative Inverse von x2 - x1 modulo n kann nicht bestimmt werden) kann ein Faktor von n extrahiert werden.
Um diese Situation zu provozieren, wählt man k als Produkt kleiner Primzahlen. Es besteht dann die begründete Hoffnung, dass k und die Ordnung von (Ef(A, B), +) einen gemeinsamen Teiler haben (dann kann k P = O sein bezüglich Ef, siehe oben) und k und die Ordnung von (Eg(A, B), +) nicht (dann ist k P != O bezüglich Eg) oder umgekehrt.
Basierend auf dem Code für Restklassenringe und elliptische Kurven ergibt sich folgende Implementierung des beschriebenen Verfahrens.
Für kleine Faktoren wird eine Zerlegung durch Testdivisionen versucht. Die Funktion trial-division-search-factors liefert die passenden Faktoren.
(setq *small-primes*
(quote
(2 3 5 7 11 13 17 19
23 29 31 37 41 43 47
53 59 61 67 71 73 79
83 89 97)))
(defproc trial-division-search-factors (n)
(select-if
(lambda (p) (integer? (/ n p)))
*small-primes*))
Die Funktion random-multiplier errechnet ein Produkt zufälliger kleiner Primzahlen. Es werden dabei deutlich mehr als log(log(n)) Primzahlen verwendet, weil nach dem Hardy–Ramanujan Theorem die Anzahl ω(n) verschiedener Primfaktoren einer Zahl n in diese Größenordnung fällt.
(defproc binary-logarithm (n)
(if
(< n 2)
1
(+ 1 (binary-logarithm (floor (/ n 2))))))
(defproc newton-root (n e a)
(let
((b (- a (floor (/ (- (expt a e) n) (* e (expt a (- e 1))))))))
(if
(= a b)
a
(newton-root n e b))))
(defproc non-zero-random (n)
(+ 1 (random (- n 1))))
(defproc random-multiplier (n)
(let
((lblb (binary-logarithm (binary-logarithm n))))
(let
((r (newton-root n lblb 1))
(m 1))
(dotimes (i (* 9 lblb) m)
(setq m (lcm m (non-zero-random r)))))))
Die Funktion make-random-point erzeugt einen zufälligen Punkt auf einer zufälligen elliptischen Kurve modulo n.
(defproc make-random-point (n)
(let
((ring (new residue-class-ring n)))
(let
((a (new residue-class ring (non-zero-random n)))
(x (new residue-class ring (non-zero-random n)))
(y (new residue-class ring (non-zero-random n))))
(let
((curve (new elliptic-curve a (- (* y y) (* x x x) (* a x)))))
(make-point curve x y)))))
Die Funktion elliptic-curve-search-factor addiert einen zufälligen Punkt einer zufälligen Kurve so oft, wie ein zufälliger Multiplikator das angibt. Das Resultat der Funktion ist entweder ein gefundener Faktor oder nil. Ein gefundener Faktor muss nicht notwendigerweise eine Primzahl sein.
(defmethod repeated-addition (k (p finite-point) s)
(and
(integer? k)
(>= k 0))
(cond
((= k 0)
s)
((odd? k)
(repeated-addition (/ (- k 1) 2) (+ p p) (+ s p)))
(t
(repeated-addition (/ k 2) (+ p p) s))))
(defmethod repeated-addition (k (p infinite-point) s)
t
s)
(defmethod repeated-addition (k (p point))
(and
(integer? k)
(>= k 0))
(repeated-addition k p (get-infinite-point (get-curve p))))
(defproc elliptic-curve-search-factor (product)
(let
((multiplier (random-multiplier product))
(curve-count 0))
(loop
(let
((point (make-random-point product)))
(catch-and-apply
(quote no-multiplicative-inverse)
(lambda (name value) (return (gcd value product)))
(repeated-addition multiplier point)))
(setq curve-count (+ curve-count 1))
(when (greater? curve-count 18)
(return nil)))))
Die Funktion elliptic-curve-factor-generator wiederholt das Verfahren, bis ein Faktor gefunden wird - dieser wird an einen Kanal übergeben - oder der Kanal geschlossen ist.
(defproc elliptic-curve-factor-generator (channel product)
(loop
(when (closed-channel? channel)
(return nil))
(awhen (elliptic-curve-search-factor product)
(send-on-channel channel it nil)
(return nil))))
Die Funktion elliptic-curve-find-factor startet mehrere Threads, in denen gleichzeitig nach einem Faktor gesucht wird. Danach wartet sie auf den Empfang eines Faktors auf dem Kanal. Nach dem Empfang wird der Kanal geschlossen.
(defproc elliptic-curve-find-factor (product)
(let
((channel (make-channel 0)))
(progn
(dotimes (i *thread-count*)
(go (elliptic-curve-factor-generator channel product)))
(ensure
(receive-from-channels (list channel) nil)
(close-channel channel)))))
Die Funktion factorize zerlegt eine Zahl in Primfaktoren. Diese werden als Liste geliefert. Es werden vier Fälle unterschieden:
- die Zahl ist kleiner als 2, dann gibt es keine Primfaktoren,
- die Zahl ist eine Primzahl, der einzige Faktor ist die Zahl selbst,
- es werden Faktoren anhand der Testdivisionen gefunden, diese gehen in das Resultat ein, der Quotient der Zahl und der gefundenen Faktoren wird rekursiv weiter zerlegt,
- es wird ein Faktor anhand von elliptischen Kurven gefunden, dieser und der verbleibende Quotient werden rekursiv zerlegt.
(defproc factorize (number)
(if
(< number 2)
nil
(if
(prime? number)
(list number)
(aif
(trial-division-search-factors number)
(append it (factorize (/ number (apply * it))))
(let
((factor (elliptic-curve-find-factor number)))
(append
(factorize factor)
(factorize (/ number factor))))))))
Quelle
H. W. Lenstra Jr.
"Factoring integers with elliptic curves"
Annals of Mathematics 126 (1987)
Seiten 649ff
Links
https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization
https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves
https://en.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
http://www.encyclopediaofmath.org/index.php/Hardy-Ramanujan_theorem
https://www.wolframalpha.com/input/?i=Factorize%5B340282366920938463463374607431768211455%5D
Aus dem Satz von Lagrange angewendet auf (Ep(A, B), +) folgt, dass wenn die k-fache Addition eines Punkts P != O das neutrale Element O ergibt, also k P = O ist, dann müssen k und die Ordnung der Gruppe einen größten gemeinsamen Teiler ungleich 1 haben. Dieser gemeinsame Teiler ist die Ordnung des Punkts, d.h. das kleinste x für das x P = O ist.
Angenommen, die zu faktorisierende Zahl n ist das Produkt zweier Primzahlen f und g. Die Addition von Punkten erfüllt für die Kurve En(A, B) dann nicht die Gruppeneigenschaften, weil der Restklassenring Z/nZ für zusammengesetzte n kein Körper ist. Das liegt unter anderem daran, dass die Vielfachen von f und g kein multiplikatives Inverses in Z/nZ haben.
Für die kleineren Kurven Ef(A, B) und Eg(A, B) erfüllt die Addition aber die Gruppeneigenschaften, da f und g nach der oben genannten Voraussetzung Primzahlen und Z/fZ und Z/gZ Körper sind.
Eine Addition von Punkten P und Q auf En(A, B) entspricht zwei simultanen Additionen auf Ef(A, B) und Eg(A, B), das ist eine Folgerung des chinesischen Restsatzes und der Voraussetzung n = f g.
Wenn in Ef(A, B) die wiederholte Addition k P = O ergibt, in Eg(A, B) aber k P != O gilt, dann ist k P für En(A, B) nicht definiert und aus dem auftretenden Fehler (das multiplikative Inverse von x2 - x1 modulo n kann nicht bestimmt werden) kann ein Faktor von n extrahiert werden.
Um diese Situation zu provozieren, wählt man k als Produkt kleiner Primzahlen. Es besteht dann die begründete Hoffnung, dass k und die Ordnung von (Ef(A, B), +) einen gemeinsamen Teiler haben (dann kann k P = O sein bezüglich Ef, siehe oben) und k und die Ordnung von (Eg(A, B), +) nicht (dann ist k P != O bezüglich Eg) oder umgekehrt.
Basierend auf dem Code für Restklassenringe und elliptische Kurven ergibt sich folgende Implementierung des beschriebenen Verfahrens.
Für kleine Faktoren wird eine Zerlegung durch Testdivisionen versucht. Die Funktion trial-division-search-factors liefert die passenden Faktoren.
(setq *small-primes*
(quote
(2 3 5 7 11 13 17 19
23 29 31 37 41 43 47
53 59 61 67 71 73 79
83 89 97)))
(defproc trial-division-search-factors (n)
(select-if
(lambda (p) (integer? (/ n p)))
*small-primes*))
Die Funktion random-multiplier errechnet ein Produkt zufälliger kleiner Primzahlen. Es werden dabei deutlich mehr als log(log(n)) Primzahlen verwendet, weil nach dem Hardy–Ramanujan Theorem die Anzahl ω(n) verschiedener Primfaktoren einer Zahl n in diese Größenordnung fällt.
(defproc binary-logarithm (n)
(if
(< n 2)
1
(+ 1 (binary-logarithm (floor (/ n 2))))))
(defproc newton-root (n e a)
(let
((b (- a (floor (/ (- (expt a e) n) (* e (expt a (- e 1))))))))
(if
(= a b)
a
(newton-root n e b))))
(defproc non-zero-random (n)
(+ 1 (random (- n 1))))
(defproc random-multiplier (n)
(let
((lblb (binary-logarithm (binary-logarithm n))))
(let
((r (newton-root n lblb 1))
(m 1))
(dotimes (i (* 9 lblb) m)
(setq m (lcm m (non-zero-random r)))))))
Die Funktion make-random-point erzeugt einen zufälligen Punkt auf einer zufälligen elliptischen Kurve modulo n.
(defproc make-random-point (n)
(let
((ring (new residue-class-ring n)))
(let
((a (new residue-class ring (non-zero-random n)))
(x (new residue-class ring (non-zero-random n)))
(y (new residue-class ring (non-zero-random n))))
(let
((curve (new elliptic-curve a (- (* y y) (* x x x) (* a x)))))
(make-point curve x y)))))
Die Funktion elliptic-curve-search-factor addiert einen zufälligen Punkt einer zufälligen Kurve so oft, wie ein zufälliger Multiplikator das angibt. Das Resultat der Funktion ist entweder ein gefundener Faktor oder nil. Ein gefundener Faktor muss nicht notwendigerweise eine Primzahl sein.
(defmethod repeated-addition (k (p finite-point) s)
(and
(integer? k)
(>= k 0))
(cond
((= k 0)
s)
((odd? k)
(repeated-addition (/ (- k 1) 2) (+ p p) (+ s p)))
(t
(repeated-addition (/ k 2) (+ p p) s))))
(defmethod repeated-addition (k (p infinite-point) s)
t
s)
(defmethod repeated-addition (k (p point))
(and
(integer? k)
(>= k 0))
(repeated-addition k p (get-infinite-point (get-curve p))))
(defproc elliptic-curve-search-factor (product)
(let
((multiplier (random-multiplier product))
(curve-count 0))
(loop
(let
((point (make-random-point product)))
(catch-and-apply
(quote no-multiplicative-inverse)
(lambda (name value) (return (gcd value product)))
(repeated-addition multiplier point)))
(setq curve-count (+ curve-count 1))
(when (greater? curve-count 18)
(return nil)))))
Die Funktion elliptic-curve-factor-generator wiederholt das Verfahren, bis ein Faktor gefunden wird - dieser wird an einen Kanal übergeben - oder der Kanal geschlossen ist.
(defproc elliptic-curve-factor-generator (channel product)
(loop
(when (closed-channel? channel)
(return nil))
(awhen (elliptic-curve-search-factor product)
(send-on-channel channel it nil)
(return nil))))
Die Funktion elliptic-curve-find-factor startet mehrere Threads, in denen gleichzeitig nach einem Faktor gesucht wird. Danach wartet sie auf den Empfang eines Faktors auf dem Kanal. Nach dem Empfang wird der Kanal geschlossen.
(defproc elliptic-curve-find-factor (product)
(let
((channel (make-channel 0)))
(progn
(dotimes (i *thread-count*)
(go (elliptic-curve-factor-generator channel product)))
(ensure
(receive-from-channels (list channel) nil)
(close-channel channel)))))
Die Funktion factorize zerlegt eine Zahl in Primfaktoren. Diese werden als Liste geliefert. Es werden vier Fälle unterschieden:
- die Zahl ist kleiner als 2, dann gibt es keine Primfaktoren,
- die Zahl ist eine Primzahl, der einzige Faktor ist die Zahl selbst,
- es werden Faktoren anhand der Testdivisionen gefunden, diese gehen in das Resultat ein, der Quotient der Zahl und der gefundenen Faktoren wird rekursiv weiter zerlegt,
- es wird ein Faktor anhand von elliptischen Kurven gefunden, dieser und der verbleibende Quotient werden rekursiv zerlegt.
(defproc factorize (number)
(if
(< number 2)
nil
(if
(prime? number)
(list number)
(aif
(trial-division-search-factors number)
(append it (factorize (/ number (apply * it))))
(let
((factor (elliptic-curve-find-factor number)))
(append
(factorize factor)
(factorize (/ number factor))))))))
Quelle
H. W. Lenstra Jr.
"Factoring integers with elliptic curves"
Annals of Mathematics 126 (1987)
Seiten 649ff
Links
https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization
https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves
https://en.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
http://www.encyclopediaofmath.org/index.php/Hardy-Ramanujan_theorem
https://www.wolframalpha.com/input/?i=Factorize%5B340282366920938463463374607431768211455%5D