Wie man eine Zahl in Primfaktoren zerlegt

Eine empirische Notiz

Grundlagen

Die Zahl 25773 kann man sich vorstellen als repräsentiert mit Hilfe einiger einander kreuzender Linien. Die Schnittpunkte dieser Linien untereinander repräsentieren dabei die Ziffern der Zahl.

Eine 2 in diesem Sinne ist so etwas

Hier kreuzen zwei parallele Linien eine dritte Linie. Es gibt zwei Schnittpunkte. Diese liest man als "2".

Die 5 baut man so ein:

Man zählt die Schnittpunkte längs der gedachten Diagonalen (angedeutet durch die kleinen Pfeile) und finden 4 + 1 = 5 Schnittpunkte, im o. g. Sinne also die Repräsentation der Ziffer 5. [Wollte man die Lage der hinzugefügten Linien (blau) austauschen, bekäme man oben zwei Schnittpunkte und unten einen, hätte also eine 3 statt einer 5 - so ginge es also nicht.]

Weiter mit der 7:

Die Diagonale, auf der die Anzahl der Schnittpunkte die Zahl 7 ergeben soll, ist schon mit zwei Schnittpunkten (blau) besetzt. Man fügt oben drei Linien hinzu und unten eine und erhalten so unsere 7 Schnittpunkte für die Ziffer 7.

Wollte man Linien in anderer Weise hinzufügen, käme man mit den nächsten Ziffern nicht weiter. Dadurch wird man sogleich auf einen Fehler aufmerksam und man findet schnell die richtige Variante. Man liest die Anzahlen der Schnittpunkte als 2, 5, 7, 7, 3 bzw. 25773.

Es ergibt sich ein Gitter mit dieser Struktur:

Nun liest man die Linien gruppenweise und nach ihrer Ausrichtung als Ziffern. Man bekommt für die Anzahlen der Linien in den Gruppen, die von links unten nach rechts oben gehen 1, 2, 1 und für die Linien, die von links oben nach rechts unten gehen 2 1 3 (v.l.n.r.). Liest man dies nun als Zahlen, so erhält man 121 und 213.

213 x 121 = 25773.

Die Zahl 25773 ist also in Faktoren zerlegt. Weder 121 noch 213 sind Primzahlen. Also wendet man das gezeigte Verfahren auf die beiden Faktoren 121 und 213 an.

121 zerlegt man so:

Gelesen wie oben, ergibt das die Faktoren 11 und 11.

11 x 11 = 121.

213 wird so zerlegt:

Beim Versuch, die Zahl 213 ebenso darzustellen, könnte man mit der Ziffer 2 beginnen. Das führt aber für die nachfolgenden Ziffern zu Schwierigkeiten (wie oben angedeutet). Man beginnt statt dessen mit der Ziffernfolge 21, liest sie als 21 und repräsentiert sie so:

So kann man mit einer weiteren Linie die Sache zu Ende bringen. Die Ziffern 2, 1 und 3 sind abgebildet. Zählt man nun die Linien, findet man 7 und 1 für die Linien von links oben nach rechts unten und 3 für die Linien von links unten nach rechts oben. Als Faktoren gelesen, sind das dann 71 und 3. 71 x 3 = 213.

Damit ist 25773 zerlegt in 3 x 11 x 11 x 71 = 25773.

Wenn man versucht, größere Zahlen zu zerlegen, wird man auf mehrstellige Schnittpunktzahlen treffen, die dann entsprechend zu zerlegen sind. Die Größe des Linien-Gatters (im Beispiel zunächst 3 x 3 Gruppen, dann weniger bei den ermittelten Faktoren) wächst etwa quadratisch und dementsprechend auch die Zahl der Arbeitsschritte des Verfahrens.

Benötigt man mit einem Computer für eine fünfstellige Zahl wie im Beispiel zur Zerlegung in Primfaktoren vielleicht 1/1000s, so wird es bei einer entsprechenden zehnstelligen Zahl etwa vier Mal so lange dauern. Eine solche Zahl mit 5000 statt 5 Stellen erfordert dann etwa 1.000 x 1.000 = 1.000.000 Mal soviel Zeit - also eine gute Viertelstunde, grob geschätzt. Primfaktorenzerlegung als App auf dem Telefon erscheint da vorstellbar. Die Schwierigkeit der Primfaktorenzerlegung ist Teil der Zuverlässigkeit populärer asymmetrischer Verschlüsselungsverfahren.