| has gloss | deu: Die Faktorisierungsmethode von Lehman ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, insbesondere der algorithmischen Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven ganzen Zahl wenn einer existiert. Findet er keinen solchen Teiler, dann ist die vorgegebene Zahl eine Primzahl. Die Faktorisierungsmethode von Lehman ist somit sowohl ein Faktorisierungsverfahren, als auch ein Primzahltest. Sie wurde im Jahr 1974 von Russell Sherman Lehman in einer Arbeit mit dem Titel „Factoring Large Integers“ veröffentlicht. Sowohl zur Faktorisierung als auch zur Überprüfung der Primzahleigenschaft gibt es bessere Verfahren. Die Faktorisierungsmethode von Lehman war jedoch der erste deterministische Algorithmus, der vollständig analysiert werden konnte und der asymptotisch schneller als die Probedivision war. |