Probedivision

Die Probedivision ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven 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ürlichen Zahl ermitteln. In der Regel benutzt man dieses Verfahren nur als Faktorisierungsverfahren, um Primfaktoren bis zu einer gewissen Schranke zu finden. Man spricht dann von unvollständiger Probedivision.

Funktionsweise

Bei der Probedivision werden die Faktoren einer Zahl $n$ gesucht, indem man $n$ der Reihe nach durch jede Primzahl $p$, bei der 2 beginnend, dividiert und dadurch überprüft, ob $p$ ein Faktor von $n$ ist. Wenn ja, ersetzt man $n$ durch die Zahl $n/p$ und dividiert diese erneut durch $p$. Wenn nein, geht man zur nächstgrößeren Primzahl $p$ über. Dies macht man solange, bis $p$ 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 $n$ zum einen durch keine Zahl kleiner oder gleich ${\sqrt {n}}$ teilbar ist (diese wurden schon abdividiert) und zum anderen das Produkt zweier Zahlen größer ${\sqrt {n}}$ auch größer als $n$ selbst ist.

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 = 2·3²·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 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_i), so lässt sich mit

$\prod _{i=1}^{n}(p_{i}-1)$

ein Intervall von

$\prod _{i=1}^{n}p_{i}$

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 speichern oder alternativ dazu immer die Hälfte der 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² 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 $2{\tfrac {\sqrt {n}}{\ln n}}$ Divisionen. In den Varianten, die ohne eine Primzahlliste auskommen, ist die Anzahl der Divisionen im schlechtesten Fall $c{\sqrt {n}}$, 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.