Test mit zufälligen Primzahlen (zum Aufwärmen)

Zuerst bauen wir die konzeptionelle Mechanik für diese neuen Arten von Zufallsalgorithmen auf, die eine Eingabe N akzeptieren. Wenn N Primzahl ist, wird unser Algorithmus mit hundertprozentiger Sicherheit eine Primzahl ausgeben. Er wird es nie als zusammengesetzte Zahl bezeichnen. Wenn N jedoch zusammengesetzt ist, gibt es eine winzige Fehlerwahrscheinlichkeit E, dass diese als Primzahl bezeichnet wird. Andernfalls besteht eine Wahrscheinlichkeit von eins minus diesem winzigen Fehler, dass es korrekt als zusammengesetzt identifiziert wird. Wir fangen ganz einfach an. Aus einem Universum von Ganzzahlen bis zu einer bestimmten Grenze nehmen wir eine Zahl und nennen diese Ganzzahl N. Wir geben N in unsere Maschine ein. Zuvor haben wir bei unseren Probedivisionsmethoden im Grunde alle Werte von eins bis zur Quadratwurzel von N durchlaufen lassen und getestet, ob diese Zahl N teilt. Im Idealfall wollten wir nur Primzahlen prüfen, um Zeit zu sparen. Wenn ja, A teilt also N, dann wissen wir, dass N eine zusammengesetzte Zahl ist, weil wir einen zusammengesetzten Zeugen gefunden haben. Wenn nicht, sind wir uns nicht sicher. Also gehen wir zurück, inkrementieren A und testen erneut. Sobald wir alle möglichen Tests ausgeschöpft haben, können wir sagen, dass N Primzahl ist, wenn wir keine Teiler gefunden haben. Jetzt seien wir mal faul. Was ist, wenn wir einfach ein paar zufällige Ganzzahlen auswählen und ein paar Teilbarkeitstests durchführen, die man als zufällige Fragen betrachten kann? Wir wissen, dass eine Zahl N, wenn sie zusammengesetzt ist, einige verstreute Teiler haben muss. Mindestens hat es einen einzigen Teiler. Einige zusammengesetzte Zahlen haben viele Teiler. Wie auch immer, wir wählen eine zufällige Ganzzahl A zwischen eins und der Quadratwurzel von N. Das war's. Dann überprüfen wir einfach, ob A durch N teilbar ist. Wie zuvor, wenn A N teilt, wissen wir sicher, dass N zusammengesetzt ist. Wir haben einen Zeugen gefunden. Wenn nicht, haben wir nicht viel gelernt, außer dass es eine Primzahl sein könnte. Um sicher zu sein, könnten wir noch ein paar zufällige As generieren und weiter testen. Vielleicht könnten wir nach hundert oder tausend Iterationen aufhören und mit einer gewissen Sicherheit sagen, dass es wahrscheinlich eine Primzahl ist. Sagen wir zum Beispiel mit 99,9 prozentiger Wahrscheinlichkeit. Dies ähnelt dem Beispiel-Spiel zur bedingten Wahrscheinlichkeit. In der einfachsten Version versuchten wir zu erraten, ob eine Münze fair ist oder ob es eine Münze mit zwei Köpfen ist. In diesem Fall ist Zahl wie das Finden eines Teilers. Es ist ein Beweis einer fairen Münze. Kopf ist der Fall, in dem wir möchten, dass die Person erneut wirft und iteriert. In diesem Fall sind wir nach etwa 5 Kopf-Würfen zu mehr als 90 Prozent sicher, also könnten wir aufhören und sagen: "Wir denken, die Münze hat zwei Köpfe." Hier habe ich ein Programm eingerichtet, das unsere alten Probedivisionsmethoden mit diesem neuen Zufallsteilungstest vergleicht. Ich verwende den aktuellen Geschwindigkeitsführer der Probedivision, ein Programm von Dino. Ich habe den Link in der Kopfzeile des Programms gepostet. Zu Beginn beachte die variable Anzahl der Versuche. Das ist die Anzahl der Zufallsversuche. Wir beginnen bei einer kleinen Anzahl, wie zum Beispiel drei. Beachte: Auch bei kleinen Eingaben mit Primzahlen wird der Zufalls-Teilungs-Algorithmus immer eine Primzahl ausgeben. Wenn die Eingabe zusammengesetzt ist, sehen wir, dass die Zufallsdivision Fehler machen kann und es fälschlicherweise als Primzahl identifiziert. Wir können dies jedoch beheben, indem wir die Anzahl der Versuche erhöhen und die Wahrscheinlichkeit eines Fehlers abnimmt. Wir sehen jetzt, dass die Ausgaben mehr oder weniger übereinstimmen. Wenn ich größere Eingaben teste, steigt die Fehlerquote wieder. Ich muss die Anzahl der Zufallstests entsprechend erhöhen. Wenn ich das tue, stimmen die Ausgaben sehr gut überein. Sie scheinen identisch zu sein. Bei einer riesigen Eingabegröße benötige ich Tausende von Zufallstests, damit dies genau ist. Wir haben die Anzahl der benötigten Schritte tatsächlich nicht verbessert. Unsere Methode der Probeteilung scheint besser zu sein. Dies liegt daran, dass die Fehlerquote des Divisionstests sehr hoch ist. Aber wir sind nahe dran. Wir haben die richtige Idee. Wir müssen einen anderen Test anwenden. Wir brauchen eine Gleichung, die schnell zu berechnen ist. Eine, mit der wir beweisen können, dass eine Zahl zusammengesetzt ist. Sie muss nicht nur die eingegebene ganze Zahl N akzeptieren, sondern auch eine zufällige ganze Zahl A und einen Zufallstest durchführen. Und zwar auf die gleiche Art und Weise.