WEL

cOMe

to

Rab
bIT'S
BuRRoWdiG#Ged byCHAoS BunNY Club*CKC

Faktorisierung mit der dritten binomischen Formel


Jede Zahl kann man als Differenz von Quadraten darstellen. Hier interessant sind nur die ungeraden Zahlen und ungerade Faktoren. Man addiert zu der Zahl selbst 1 und teilt sie durch zwei, subtrahiert dann wieder 1 – den kleineren (trivialen) Faktor der untersuchten Zahl: (15 + 1 ) : 2 = 8, 8 - 1 = 7

Für die beiden Teile der Zahl gilt, dass sie Basen von Quadraten sind, deren Differenz der Zahl entspricht: 8^2 – 7^2 = 15.

Beweisen kann man diesen Sachverhalt mit der dritten binomischen Formel:
a^2 – b^2 = (a-b)*(a+b)

In diesem Fall entspricht das
(8-7) * (8 + 7).

Das wiederum ist

1 * 15

Das bedeutet, wenn man die beiden ‚Hälften‘ addiert, erhält man die Zahl selbst als Faktor, wenn man sie subtrahiert, die 1. Dieses Prinzip gilt auch für Primzahlen, nur lässt es sich bei Primzahlen nicht für weitere Faktoren nutzen.

Dieser leicht konstruierbare triviale Fall einer Faktorisierung gilt also für alle ungeraden Zahlen, Primzahlen eingeschlossen: Die Differenz der Quadratbasen ergibt 1, die Summe die Zahl, die geteilt werden soll (hier 15). Das Wesentliche für nicht-prime Zahlen ist nun:

Zahlen, die nicht prim sind, haben noch weitere Quadratpaare, deren Differenz über die dritte binomische Formel die Faktoren berechenbar macht.
Sobald man das Quadratpaar kennt, sind die Faktoren sehr leicht auszurechnen.

Dies kann man sich für die Faktorisierung von großen Zahlen zunutze machen.

Mit etwas Pech können die Quadratdifferenzen aber sehr viel größer sein als die Zahl selbst.

„Pech“ ist nicht das richtige Wort, denn die schwierigen und unkomplizierten Fälle lassen sich immerhin gut unterscheiden.

Der Idealfall:

Die Faktoren sind Zwillingsprimzahlen.

Eines der Quadrate liegt dann direkt über der Zahl, die man faktorisieren möchte. Dies ist z.B. der Fall bei dem bereits vorgestellten Beispiel 15: 15 ist teilbar durch 3 und 5. 3 und 5 sind Zwillingsprimzahlen.

Welchen Quadraten entsprechen diese Faktoren?

Üblicherweise betrachtet man die Teiler – wenn man sie bereits kennt – addiert sie und teilt sie durch 2 (wie bei einer Durchschnittsberechnung):
3 + 5 = 8 , 8 : 2 = 4
4 ist die obere Quadratbasis und liegt zwischen den Faktoren 3 und 5. Diese ergeben sich durch Addieren und Subtrahieren von 1.

Entsprechend ist 1 die untere Quadratbasis, im Sonderfall gleich dem Quadrat. Wenn 1 die untere Basis ist, sind die Faktoren immer Zwillingsprimzahlen,

da sie sich dann nur um einen Zweierschritt unterscheiden - egal wie groß sie selbst sind.

Es lohnt sich also immer, wie schon Blaise Pascal erkannt hat, ein Mathematiker des 17. Jahrhunderts, zu prüfen, ob vielleicht eine Quadratzahl

direkt über der Zahl liegt, die analysiert werden soll.

Allerdings ist das tatsächlich ziemlich selten ;)

Aber auch wenn die Faktoren keine Zwillingszahlen sind, lassen sie sich diesem Prinzip folgend mit einem Python-Programm finden. Schwierig wird es , wenn sie weit auseinanderliegen. Denn bei Faktoren sehr unterschiedlicher Größe entscheidet der größere Faktor über die Stelligkeit der Zahlen, die untersucht werden müssen. Die Faktoren 3 und 164321 führen zu den Quadratbasen 82162^2 - 82159^2. Da wäre es dann schon einfacher, die Quersumme auszurechnen. Also je näher an der Quadratwurzel die Faktoren sind, umso besser, bzw. umso lohnenswerter ist das 'binomische Programm'.

Das hier entwickelte Programmset besteht aus drei Teilen:

Zuerst werden Quadrate in eine Datei geschrieben, die größer als die zu faktorisierende Zahl sind.
Dann wird die Zahl von diesen Quadraten abgezogen.

Zuletzt werden diese Differenzen daraufhin untersucht, ob sie quadratisch sind. Ist das der Fall, gilt mit der dritten binomischen Formel:

A^2 - zu faktorisierende Zahl = B^2 =>

(A-B) und (A+B) sind die Faktoren, in die die zu faktorisierende Zahl sich zerlegen lässt.

Um dies Prinzip auf möglichst beliebig große und mehrfach teilbare Zahlen auszuweiten, wurde Python eingesetzt.
Das Faktorisierungsprogramm sollte einfach kontrollierbar sein und optimal effizient, also:

- die Ergebnisse mehrfach nutzbar, gespeichert

- Zahlenloops so kurz wie möglich

- möglichst kleine Mengen/Anwendungsbereiche der Loops

Es stellte sich heraus, dass Python Datendateien mit extrem großem Volumen mühelos lesen kann!

Das entwickelte Programmset arbeitet daher mit entsprechenden Datenspeichern:

1 - Zuerst wird eine Datei mit Quadraten der passenden Größe gefüllt (wie erläutert, so groß, dass man die zu faktorisierende Zahl abziehen kann).

2 - Dann erstellt ein Programm eine Liste von Differenzen, indem es die zu analysierende Zahl von den Quadraten aus der Liste abzieht und die Differenzen in eine neue Datei schreibt.

3 - Der schwierigste Prozess am Schluss: Die Differenzen werden einzeln daraufhin geprüft, ob sie quadratisch sind.


Zum Test, ob es sich bei den Differenzen um Quadratzahlen handelt, wird eine Loop-Variable (p) quadriert und so lange erhöht,

bis sie gleich oder größer als die Differenz ist, die das Programm aus der Differenzendatei ausliest.

Ist das Quadrat der Basis p größer, wählt das Programm die nächste Differenz aus der Liste. Die Quadrate auf Basis p müssen so nur einmal hochgezogen werden - bei schnell an die 50 Milliarden Differenzen, die ein entsprechendes Programm prüfen muss, ist das die Mindestbedingung an Effizienz. Die Python-Loops erfordern einiges Herumexperimentieren, aber nachdem einmal klar war, wie "break" in Python funktioniert, haben wir nun ein einigermaßen schnelles Prozedere. Für ca 45 Millionen 16_stelliger Differenzen braucht das Programm aktuell ca 15 Minuten. Wichtig für die Effizient ist auch, dass die Anfangs- und Endwerte von P zuvor aus der Differenzenliste ausgelesen werden.

Die Anfangs- und Endwerte lassen sich in den Programmdateien anpassen, sodass bei zu großem Datenvolumen einfach schrittweise geprüft werden kann. Die Programme wurden ohne Eingabe-Schnick-Schnack gestaltet, die Zahlen werden in die Dateien eingetragen.

Natürlich kann man alle drei Teilprogramme zu Funktionen umwandeln und in einem Programm zusammenfassen, das dann gegebenenfalls auch die zu analysierenden Zahlen sowie obere und untere Grenzen der Listen ober die Konsole abfragt, also die Anpassungen

selbst vornimmt und nur das Ergebnis in der "Fund"-Datei sichtbar macht.

Für die Interpretation von Python (Python3) verwenden wir unseren eigenen ckc-cypher-gt Server (auf Ubuntu 18.4) über Putty und Webmin.


Mit dem Programm ist es soeben gelungen, die Zahl 17947171289504809 als unteres Quadrat zur Faktorisierung der Zahl 9303833637413847 zu bestimmen.

Zwar ist 9303833637413847 an sich nicht schwer zu teilen (z.B. durch 3 teilbar) aber es sollten "blind" zwei große Faktoren gefunden werden, ein primer Faktor mit neun Stellen und der nicht-prime, dazugehörige Faktor.
Diese ergeben sich mit dem Fund 17947171289504809 des Programms über dessen Wurzel:


17947171289504809 = 133967053^2:


Es gilt: 133967053^2 + 9303833637413847 = 27251004926918656 = 165078784^2

Also sind die Faktoren von 9303833637413847 = (165078784 - 133967053) * (165078784 + 133967053)


299045837 * 31111731 = 9303833637413847

Die problemlos ausgelesenen Dateien mit Quadraten und Differenzen haben jeweils eine Größe von einem Gigabyte.
Das Programm hat eine 17-stellige Anzahl von ebenso-stelligen Zahlen daraufhin geprüft, ob sie quadratisch sind und die einzige Quadratzahl in der Menge gefunden.


Zeitaufwand dafür in etwa 15 Minuten.

CURRENT CONTENT (AKTUELLES THEMA)

* SCHLANGEN! Python als Faktorisiermaschine *

* Further Files *


index.ckc


1

5 !

mehr über Zahlenschlangen (dt.)

GTScratchN'Hop