Quelltext der Seite Probedivision

{{Belege fehlen}}

Die '''Probedivision''' ist ein [[Algorithmus]] aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] der [[Zahlentheorie]]. Der Algorithmus ermittelt einen [[Teilbarkeit#Einfache Folgerungen|nichttrivialen Teiler]] einer positiven [[Ganze Zahl|ganzen Zahl]], wenn einer existiert. Findet er keinen solchen Teiler, so ist die vorgegebene Zahl eine [[Primzahl]]. Die Probedivision ist somit sowohl ein [[Faktorisierungsverfahren]] als auch ein [[Primzahltest]]. Führt man die Probedivision weiter, nachdem ein nichttrivialer Teiler gefunden wurde, so kann man letztendlich die [[Primfaktorzerlegung]] einer [[natürliche Zahl|natürlichen Zahl]] ermitteln. In der Regel benutzt man dieses Verfahren nur als Faktorisierungsverfahren, um [[Primzahl|Primfaktoren]] bis zu einer gewissen [[Beschränkte Menge|Schranke]] zu finden. Man spricht dann von ''unvollständiger Probedivision''.

== Funktionsweise ==
Bei der Probedivision werden die Faktoren einer Zahl <math>n</math> gesucht, indem man <math>n</math> der Reihe nach durch jede Primzahl <math>p</math>, bei der 2 beginnend, [[Division (Mathematik)|dividiert]] und dadurch überprüft, ob <math>p</math> ein Faktor von <math>n</math> ist. Wenn ja, ersetzt man <math>n</math> durch die Zahl <math>n/p</math> und dividiert diese erneut durch <math>p</math>. Wenn nein, geht man zur nächstgrößeren Primzahl <math>p</math> über. Dies macht man solange, bis <math>p</math> größer als die [[Quadratwurzel]] von ''n'' geworden ist. Die verbleibende Zahl ''n'' ist dann entweder 1 oder eine Primzahl und damit der letzte Faktor der gegebenen Zahl, da <math>n</math> zum einen durch keine Zahl kleiner oder gleich <math>\sqrt n</math> teilbar ist (diese wurden schon abdividiert) und zum anderen das Produkt zweier Zahlen größer <math>\sqrt n</math> auch größer als <math>n</math> selbst ist.<ref>{{Literatur |Autor=Johannes Buchmann |Titel=Einführung in die Kryptographie |Verlag=Springer-Verlag |Datum=2016-04-19 |ISBN=978-3-642-39775-2 |Seiten=155f |Online=https://www.google.de/books/edition/Einf%C3%BChrung_in_die_Kryptographie/xZEFDAAAQBAJ?hl=de&gbpv=1&dq=Probedivision&pg=PA156&printsec=frontcover |Abruf=2025-03-14}}</ref>

Im Falle der unvollständigen Probedivision verfährt man genauso, nur mit dem Unterschied, dass man bereits bei einer vorgegebenen Schranke ''S'' aufhört. Der verbleibende Faktor muss in diesem Fall nicht mehr unbedingt ein Primfaktor sein.

== Beispiel ==
Um die Zahl 1746 zu faktorisieren, teilt man diese zuerst durch 2 und erhält 873. Ein weiteres Mal lässt sich diese Zahl nicht durch 2 teilen. Somit geht man über zur 3. Durch diese kann man wieder teilen und bekommt 291. Diese Zahl lässt sich nochmal durch 3 teilen und man bekommt 97, die nicht mehr durch 3 teilbar ist. Danach versucht man noch erfolglos durch die Zahlen 5 und 7 zu teilen. Die nächste Primzahl 11 ist aber schon größer als die Wurzel aus 97, weshalb man an dieser Stelle abbricht und die Primfaktorzerlegung angeben kann: 1746&nbsp;=&nbsp;2·3<sup>2</sup>·97.

== Varianten ==
Für die Probedivision benötigt man eine Liste mit kleinen Primzahlen, die man gewöhnlich über das [[Sieb des Eratosthenes]] erzeugt. Dies ist insbesondere dann praktisch, wenn man mehrere etwa gleich große Zahlen faktorisieren möchte. Einige Varianten der Probedivision kommen ohne diese Liste aus.

Eine Möglichkeit ist es, nicht nur mit den Primzahlen eine Probedivision durchzuführen, sondern mit allen Zahlen (außer der 1). Das Ergebnis ist das gleiche, aber es werden überflüssige Divisionen durchgeführt.

Einige dieser überflüssigen Divisionen kann man vermeiden, wenn man nur noch mit der 2 und den ungeraden Zahlen eine Probedivision durchführt.

Diese Idee lässt sich noch weiter verallgemeinern, indem man sich auf alle Zahlen, die [[Kongruenz (Zahlentheorie)|kongruent]] 1 oder 5 modulo 6, oder alle Zahlen die kongruent 1, 7, 11, 13, 17, 19, 23 oder 29 modulo 30 sind, beschränkt. Im ersten Fall muss man noch zusätzlich die Zahlen 2 und 3 probieren, im zweiten Fall die Zahlen 2, 3 und 5.

Nimmt man allgemein die ersten n Primzahlen (p<SUB>i</SUB>), so lässt sich mit 
:<math>\prod_{i=1}^n (p_i-1)</math>
ein Intervall von 
:<math>\prod_{i=1}^n p_i</math>
Zahlen durchsuchen. Für die ersten 4 Primzahlen (2, 3, 5, 7) bedeutet das, dass (2-1)·(3-1)·(5-1)·(7-1) = 48 Tests ausreichen, um ein Intervall mit 2·3·5·7 = 210 Teilern abzuarbeiten.

Der Vorteil liegt darin, dass ein solches Programm ohne große Primzahltabellen auskommt. Da in einem Intervall von 210 Zahlen die Abstände der notwendigen Teiler fest sind, genügt eine Tabelle von 48 kleinen Zahlen, das Inkrement für den nächsten Teiler zu berechnen.

== Implementierungsdetails ==
Möchte man die Probedivision in einem [[Computerprogramm]] benutzen, so wird man aus Speicherplatzgründen die Liste der Primzahlen entweder als [[Bit]]-[[Array (Datentyp)|Array]] speichern oder alternativ dazu immer die Hälfte der [[Subtraktion|Differenz]] dieser Primzahl zur vorhergehenden Primzahl. In letzterem Fall benötigt man für jede Primzahl bis 1.872.851.947 nur ein [[Byte]] Speicherplatz (pro Primzahl).

Anstatt zu überprüfen, ob ''p'' größer als die Wurzel aus ''n'' ist, testet man ob ''p''<sup>2</sup> größer als ''n'' ist, da dies schneller geht.

Im Falle der Variante, bei der nur noch Zahlen probiert werden, die kongruent 1 oder 5 modulo 6 sind, kann man diese Zahlen effizient durchlaufen, indem man abwechselnd 2 und 4 zur vorherigen Zahl addiert.

== Laufzeit ==
Die Probedivision benötigt im schlimmsten Fall etwa <math>2\tfrac{\sqrt{n}}{\ln n}</math> Divisionen. In den Varianten, die ohne eine Primzahlliste auskommen, ist die Anzahl der Divisionen im schlechtesten Fall <math>c\sqrt{n}</math>, wobei die Konstante ''c'' vom Verfahren abhängt.

Die mittlere Laufzeit liegt in der gleichen Größenordnung wie beim schlechtesten Fall.

== Einsatzbereiche ==
Die unvollständige Probedivision wird oftmals benutzt, um einen ersten Überblick über die Faktorisierung einer Zahl zu gewinnen. Erst wenn diese nicht in der Lage ist, die Zahl vollständig zu faktorisieren, geht man über zu komplexeren Faktorisierungsverfahren.

Außerdem wird die Probedivision oftmals als Teilschritt in komplexeren Faktorisierungsverfahren benötigt.

== Einzelnachweise ==
<references />

[[Kategorie:Faktorisierungsverfahren]]