Hi hier euer CKC aus frei- und unfrei schwebenden Kaninchencognitionen und einem Omitron.

Wir erklären euch jetzt den einfachen Kern unseres aktuellen Faktorenprogrammes, von dem wir behaupten, dass es mit den Mitteln der RSA Verschlüsselung selbst die einschlägigen Zahlen faktorisiert. Das stimmt bisher immerhin approximativ.

Also das Basisprinzip.

Die Verschlüsselung unterscheidet zwei Zahlen, einmal n und dann phi(n), für die gilt, dass

phi(n)= (p-1)*(q-1)+1  genau dann wenn n = p*q

Wir haben festgestellt (beweisbar durch die Abstände von Zahlen und Quadratzahlen voneinander in den bekannten Reihen, Gauss etc., Beweis noch nicht fertig), dass für n und phi(n) (ohne +1) folgendes gilt:

Wenn n und phi(n) bekannt sind - ohne dass die Faktoren bekannt sein müssen - kennen wir für beide Zahlen auch eine Darstellung als erste Quadratzahl über n und phi(n) (jeweils).

BEISPIELZAHLEN:

n = 9424117 = 313 * 30109 = 3070^2 - 783
phi(n) = 9393696 = 312 * 30108 = 3065^2 - 529

Dann lassen sich die Faktoren über die dritte binomische Formel (also über eine passende Quadratdifferenz) wie folgt berechnen:

3070^2 + 529 (also Quadrat von n plus Rest von phi(n)) = mwa

3065^2 + 783 (d.h. Quadrat von phi(n) plus Rest von n)) = mwb

Mit jeweils getauschtem Rest als Summand definieren wir als Zwischenwert mwa und wmb:

mwa=  9425429 = 9424900 + 529
mwb= 9395008 = 9394225 + 783

Mit der Differenz dieser Werte sind dann die korrekten OBEREN QUADRATE für eine Faktorenberechnung gemäß der dritten binomischen Formel gegeben:

Diff = 9425429 - 9395008 = 30421

Die Differenz rechnen wir plus eins und geteilt durch zwei für n:

30421 + 1 = 30422

30422 / 2 = 15211

Mit dem oberen Quadrat OQ von n = 15211^2 minus n ergibt sich das untere Quadrat und damit die Faktoren:

231374521 - 9424117 = 221950404

bzw 15211^2 - n = 14898^2

mit den Faktoren (15211+14898) * (15211-14898) = 313 * 30109

Ebenso für phi(n)=

231344100 -  9393696 = 221950404

bzw 15210^2 - phi(n) = 14898^2

mit den Faktoren

(15210+14898) * (15210-14898)= 312 * 30108

* Soweit, sogut! *

Das Bug-Programm besteht nun darin, dasselbe (quasi dasselbe) zu berechnen, ohne die untere Zahl bzw. phi(n) zu kennen.

Die Anfangsfaktoren setzen wir aus dem approximierten höheren Quadrat zusammen, im Prinzip durch Addition der Basis mit dem Rest. Dann eine darunterliegende oder um zwei darunterliegende Quadratbasis etc.

Das eigentliche Programm ist noch nicht optimiert, aber wir schaffen für die Zahl 24389869424117 im Moment in fünf (!) Rechenschritten die approximativen Faktoren 13683130 * 1782478. Die richtigen Faktoren sind 24389869424117 = 151 * 751 * 11071 * 19427 = 1671721 * 14589677

(nicht prim in diesem Fall, was keine wesentliche Rolle spielt): Das Programm beginnt bei Faktoren, die derapproximtiven Wurzel ähnlich sind und nähert sich dann der Kombination aus sehr großem und sehr kleinem Faktor (die uninteressanteren, weil allgemein leichter zu finden).

Programmausgabe (gekürzt)

Faktorenprox1: 5255246 4641052
Faktorenprox 2: 6892220 3538754
Faktorenprox3: 9545662 2555074
Faktorenprox4: 13683130 1782478

Daten1.3: f1n, f2n, zup, diffzup,  proxzup, restzup  13683130 1782478 24389878196140 8772023 4938611 413181

faktdiff, vf 11900652 6773

Über die Differenz der Faktoren voneinander (11900652) und die Anfangsdifferenz des Produkts der Schätzungen zu n (der zu analysierenden Zahl), 6773, lässt sich dann der richtige Faktor weiter annähern. Zudem kann man im Prinzip eine Funktion über die apprximierte Faktorenentwicklung erstellen und damit die Abweichung von der zu faktorisierenden Zahl einschränken. Die brauchbaren Faktoren sind in der Regel nach wenigen Schritten erreicht. Des Weiteren gibt es die Möglichkeit, das Produkt ziffernweise zu berechnen, sobald man eine gute Annäherung hat, wie hier (ähnlich wie bei unserer Radiziermaschine radicae). Dazu mehr, wenn das entsprechende Pythonchen und ein passendes Scratchinchen auf der Welt sind.

13683130 + 906547 = 14589677
13683130 + 133*6773   + 5738
13683130 + 900809 + 5738 = 14589677

1782478 - 110757  = 1671721  
1782478 - 16* 6773 - 2389   = 1671721

Noch viel Spaß euch in Sonne und Schatten (auch wir montieren bald endlich unsere balkonsolarscheibe, leider ist ein Zwischenschalter von den Terrassenmäusen entführt worden? bzw. auf jeden Fall weg.).

Juche,

CKC

Teil 1 geht ungefähr so:

Für die zu approximierenden Faktoren von n wird die Basis zum Rest einmal addiert (f1), einmal subtrahiert (f2).

Mit diesen heuristischen Faktoren wird phi(n) berechnet standardmäßig als fi-1, f2-1

Aus deren Produkt wird dann erneut die approximative Basis nachberechnet und der Rest.

Mit diesen beiden Zahlen und ihren Strukturen kann dann der Basentausch und die Berechnung der Differenz, deren "Verteilung" auf das obere Quadrat von n und phi(n) vorgenommen werden wie beschrieben.

Die Weiterentwicklung addiert jeweils die Differenz auf die Faktorendifferenz und berechnet dann die Quadrate neu und die Faktoren wie zuvor aus der Kreuzsumme der Basen und deren Differenz.

TEIL 2

Die approximierten Faktoren lassen sich weiter annähern mit Hilfe von n modulo eines der approximierten Faktoren.

Dabei kann es sinnvoll sein, mit der Wahl der Basen (ob die Anfangsprox oder die zum entwickelten Faktor gehörende Quadratbasis) zu experimentieren.

Bei der Zahl 316895705332325 z.B. gab es ein gutes Ergebnis mit der Anfangsbasis und der Differenz des n-modulo des ersten Faktors plus 2*die Anfangsbasis, im hier verwendeten Beispiel war es am besten, die schon gute Approximation mit der deutlich höheren Basis zu verwenden und nur mehrfach das modulo des kleineren Faktors auf die Quadratbasis zu addieren.

Das Ergebnis ist nicht exakt, aber annähernd proportional in Bezug auf die Faktoren, sodass es danach und in angemessener Berechnungszeit auch bei größeren Zahlen sinnvoll ist, entweder ziffernweise  abzuschließen oder einfach über einige digits einen der Faktoren plusminus zu testen.

 Für die weitere Approximation eignen sich am besten die Faktoren mit dem kleinsten modulo und/oder der kleinsten Differenz der Faktoren, insbesondere da ja eigentlich ein n analysiert werden soll, das nur zwei prime Faktoren hat (also/und relativ mittlere Stellenzahl)

Beispielzahl: 316895705332325

Daten1.3: f1n, f2n, zup, diffzup,  proxzup, restzup  25550176 12402878 316895715806528 10474203 17801565 642697
faktdiff, vf 13147298 2468

bereits berechnete approximative Faktoren: 2555 der Faktoren0176 * 1240287

Zur weiteren Verfeinerung der Faktorenapproximation kann man also wie folgt vorgehen:

Grundlegend ist die Verteilung der Differenzen zum jeweiligen Quadrat in der Quadratreihe.

Basis 17801565, 17801563

Bereits mit dem Programm approximierter Faktor:

35603131

 …....................24486231 (356... - 11116900) minus 2! (?)

 11116900 Rest z1

 35603127 Quadratschnitt(e :)) statt Gesamtsumme (eigentlich Bezugswert des Rests)

 …....................356..- 217... = 13859716.

 21743411 Rest z2:  zu 356.. = 13859716 

 35603123

 [bsp unmögliche Summen 24486231- 21743411]

 aber! :

 24486233 + 13859716 = 38345941 .. -1 / 2 = 19172975 basis q?

 38345941 lässt sich auch berechnen über den modulo von f1:

 17801565 (Basis) - 15075973 (mod f1) =  2725592

 Und 2*17801565 + 2725592 = 38328722 = 19164361 als neue approximative Basis

19164361^2 = 367272732538321 -  z1 = 50377027205996 =  7097677^2 (ca!)

 19164361 + 7097677 = 26262038

19164361 - 7097677 = 12066684

 Also als geschätzte Faktoren ca 26262038 * 12066684            

             richtig sind die Faktoren 26293871 * 12052075  = 316895705332325

DIE BEISPIELZAHL  24389869424117 von oben:

Bei der oben in "Fall 1" und "Fall 2" schon vorgestellten Zahl ist schon eine gute Approximation erreicht, also kann man versuchen, mit der erreichten Basisschätzung zu arbeiten. Die Vergrößerung sollte dann aber geringer sein, also der modulo vom kleineren Faktor, der dann schrittweise vervielfacht werden kann:

f1n, f2n, f2nd, f1f2nv, f1nmod 13683130 1782478 1782477.358916929 1 (f1nmod:) 4911107
diffz1qu 8772023

n (bzw z1):  24389869424117
Daten1.1: f1, f2, z1, z1test,  diffz1, prox1, rest1  4941642 4935580 24389869424117 24389869422360 1757 4938611 9185204

f2mod zuz1 = 140367

Basis 7732804, 7732803

7732804 - 4911107 = 2821697 "Überschuss" oder das modulo selbst . Der Wert erwies sich als zu hoch bei Verwendung der bereits augmentierten Quadratbasen.

Alternativ funktionierte es, das modulo des kleineren Faktors f2 selbst (vervielfacht) auf einen Quadratzahlreihenschritt zu addieren:

Den Wert addiert man zum Doppelten der ersten Proxbasis (quasi einem Schritt in der Quadratzahlenreihe):

140367 + 2*  7732804 = 15605975 (+1) * (+1 eigentlich als Äquivalenz zum Wert links)

Das Ergebnis teilt man durch 2 für das obere Quadrat:

15605976/2 = 7802988

7802988^2 - n =    6041254^2

Faktoren also mit der 3. binomischen Formel = 6041254+7802988 = 13844242 * 1761734

Da sich richtige Entwicklungen hier bei bekannten Faktoren ablesen lassen (oder durch den Verlauf des Abstands zu z1 natürlich)

und sich hier zeigen, wird das modulo für weitere Näherungsschritte vervielfacht. Da die Faktoren bekannt sind, lässt sich die Vervielfachung hier berechnen:

(8130699 - 7732804) *2 = 795790 / 140367 = 5,669 Vervielfachungsfaktor des modulo

842202 + 2*7732804 = 16307810

8153905^2 - n = 42096297324908 = 6488165^2

Damit die Faktoren:  14642070 * 1665740 geproxt

Korrekte Faktoren sind  14589677 * 1671721 = 24389869424117