User:ElisabetFatimatulVeronika/Running time for factoring integer

Heuristic running time

In number theory, there are many integer factoring algorithms that heuristically have expected running time

$L_{n}\left[1/2,1+o(1)\right]=e^{(1+o(1))(\log n)^{\frac {1}{2}}(\log \log n)^{\frac {1}{2}}}$

in o and L-notation. Some examples of those algorithms are elliptic curve and quadratic sieve method. Another such algorithm is the class group relations method proposed by Seysen-Lenstra that is proved under of the Generalized Riemann Hypothesis (GRH) assumption.

Rigorous running time

The Schnorr-Lenstra probabilistic algorithm that had been proved by Lenstra and Pomerance has rigorously expected running time $L_{n}\left[1/2,1+o(1)\right]$ by replacing GRH assumption with the use of multipliers. The algorithm uses class group of positive binary quadratic form of discriminant Δ denoted by G_Δ. G_Δ is the set of triple of integers (a, b, c) in which those integers are relative prime.

Algorithm

Consider an integer (n) that will be factorized, where n is an odd positive integer greater than a certain constant. In this factoring algorithm, the use of multiplier is explicated by choosing any positive integer d bounded by n so that Δ= -dn. It guaranties that there exist enough smooth forms in G_Δ. By constructing a set of generators G_Δ and prime forms f_q of G_Δ with $\left({\frac {\Delta }{q}}\right)=1$, the sequence of relations between the set of generators and f_q are produced. The relation that will be used is a relation between the product of powers that is equal to the element neutral of G_Δ. These relations will be employed to construct an ambiguous form of G_Δ, which is an element of G_Δ of order dividing 2. By calculating the corresponding factorization of Δ and by taking a gcd, this ambiguous form raise the complete prime factorization of n. This Schnorr-Lenstra algorithm has these main steps:

Let n be the number to be factored

1. Let Δ be a negative integer with Δ = -dn which d is a multiplier and Δ is the negative discriminant of some quadratic form.
2. Take t first primes; p₁ = 2, p₂ = 3, ..., p_t, for some t ∈ N.
3. Let f_q be a random prime form of G_Δ with $({\frac {\Delta }{q}})=1$.
4. Find a generating set x of G_Δ
5. Collect a sequence of relations between set x and {f_q : q ∈ Q} satisfying:$(\prod _{x\in X}x^{r(x)})$.$(\prod _{q\in Q}f_{q}^{t(q)})=1_{\Delta }$
6. Construct an ambiguous form (a, b, c) which is an element f ∈ G_Δ of order dividing 2 to raise a coprime factorization of the largest odd divisor of Δ in which Δ = -4a.c or a(a - 4c) or (b - 2a).(b + 2a)
7. If the ambiguous form raises a factorization of n then stop, otherwise find another ambiguous form until factorization of n is found. In order to prevent that useless ambiguous forms are generated, build up the 2-Sylow group S₂(Δ) of G(Δ).

To obtain an algorithm for factoring any positive integer, it is needed to add a few steps to this algorithm such as trial division, Jacobi sum test.

Expected running time

This factoring algorithm has chance to be failure or success such in choosing a random number generator. If the chosen number generator gives failure result then this algorithm is repeated by choosing another generator until getting success. Therefore the running time of this algorithm depends on whether this algorithm success or fail. However, in long run period this factoring algorithm takes expected running time at most $L_{n}\left[1/2,1+o(1)\right]$.