Lehman's factoring method

The factorization of Lehman is an algorithm from the mathematical sub-area of the theory of numbers , in particular the algorithmic number theory . The algorithm finds a nontrivial divisor of a positive integer , if one exists. If he does not find such a divisor, then the given number is a prime number . Lehman's factoring method is thus both a factorization method and a prime number test . It was published in 1974 by Russell Sherman Lehman in a paper entitled "Factoring Large Integers". There are better methods for both factoring and checking the prime property . However, Lehman's factoring method was the first deterministic algorithm that could be fully analyzed and that was asymptotically faster than the trial division .

algorithm

The algorithm first performs an incomplete trial division up to the limit . If it has no divisors less than , then it is the product of a maximum of two prime numbers. In this case, the set of Lehman listed below is used by by numbers , and how to search in the set. ${\displaystyle {\sqrt[{3}]{n}}}$ ${\displaystyle n}$ ${\displaystyle {\sqrt[{3}]{n}}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle k}$

1  Führe Probedivision bis  ${\displaystyle {\sqrt[{3}]{n}}}$ aus und beende falls ein Teiler gefunden wurde.
2  von k  ${\displaystyle \leftarrow }$ 1 bis  ${\displaystyle \lfloor {\sqrt[{3}]{n}}\rfloor }$
3      von x  ${\displaystyle \leftarrow }$  ${\displaystyle \lceil {\sqrt {4kn}}\rceil }$ bis  ${\displaystyle \lfloor {\sqrt {4kn}}+{\frac {\sqrt[{6}]{n}}{4{\sqrt {k}}}}\rfloor }$
4           y'  ${\displaystyle \leftarrow }$  ${\displaystyle x^{2}-4kn}$
5           wenn y' Quadratzahl ist
5               dann ist  ${\displaystyle \operatorname {ggT} (x+{\sqrt {y'}},n)}$ echter Teiler von n.
6  Falls kein Teiler gefunden wurde, ist n eine Primzahl.

If you have a lot of numbers to factorize, you can avoid calculating the roots when determining the boundaries of the inner loop over x . If you first run through numbers k with many small prime factors (e.g. k = 2 * 3 * i ), the numbers generated are often square numbers. With these improvements, this algorithm for inputs n with around 50 bits is one of the fastest known factoring algorithms.

functionality

The algorithm is based on a theorem published by Lehman along with the factoring method. In essence, the theorem describes how to factor a number that is the product of two prime numbers.

Lehman's theorem
If an odd natural number, and prime numbers and with , there are natural numbers and with the following properties: ${\displaystyle n=pq}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle 1\leq r<{\sqrt {n}}}$ ${\displaystyle {\sqrt {\frac {n}{r+1}}}<p\leq {\sqrt {n}}}$ ${\displaystyle x,y}$ ${\displaystyle k}$

${\displaystyle x^{2}-y^{2}=4kn}$

${\displaystyle x\equiv k+1\ {\pmod {2}}}$

${\displaystyle x\equiv k+n\ {\pmod {4}}}$if odd ${\displaystyle k}$

${\displaystyle {\sqrt {4kn}}\leq x\leq {\sqrt {4kn}}+{\frac {1}{4(r+1)}}{\sqrt {\frac {n}{k}}}}$

If there is a prime number, there are and there are not. ${\displaystyle n}$ ${\displaystyle x,y}$ ${\displaystyle k}$

The optimal choice of is . ${\displaystyle r}$ ${\displaystyle r=O(n^{1/3})}$

running time

Lehman's method takes many steps. Lehman itself comes to a term of in the article mentioned below . But he assumes that you can calculate the square root of a number in constant time, which is rather unrealistic. ${\displaystyle O(n^{1/3}\log \log n)}$ ${\displaystyle O(n^{1/3})}$

swell

• Richard Crandall , Carl Pomerance : Prime Numbers. A Computational Perspective. 2nd Edition. Springer-Verlag, New York 2005, ISBN 0-387-25282-7 , pp. 193-194.

Implementations

• Here you can find a quick Java implementation of the Lehman algorithm.

Individual evidence

1. ^ Russell Sherman Lehman : Factoring Large Integers. In: Mathematics of Computation. 28, 1974, pp. 637-646