Editing Integer factorization (section)

=== Schnorr–Seysen–Lenstra algorithm ===
Given an integer {{mvar|n}} that will be factored, where {{mvar|n}} is an odd positive integer greater than a certain constant. In this factoring algorithm the discriminant {{math|Δ}} is chosen as a multiple of {{mvar|n}}, {{math|1=Δ = −''dn''}}, where {{mvar|d}} is some positive multiplier. The algorithm expects that for one {{mvar|d}} there exist enough [[smooth number|smooth]] forms in {{math|''G''<sub>Δ</sub>}}. Lenstra and Pomerance show that the choice of {{mvar|d}} can be restricted to a small set to guarantee the smoothness result.

Denote by {{math|''P''<sub>Δ</sub>}} the set of all primes {{mvar|q}} with [[Kronecker symbol]] {{math|{{pars|s=150%|{{sfrac|Δ|''q''}}}} {{=}} 1}}. By constructing a set of [[Generating set of a group|generators]] of {{math|''G''<sub>Δ</sub>}} and prime forms {{math|''f''<sub>''q''</sub>}} of {{math|''G''<sub>Δ</sub>}} with {{mvar|q}} in {{math|''P''<sub>Δ</sub>}} a sequence of relations between the set of generators and {{math|''f''<sub>''q''</sub>}} are produced.
The size of {{mvar|q}} can be bounded by {{math|''c''<sub>0</sub>(log{{abs|Δ}})<sup>2</sup>}} for some constant {{math|''c''<sub>0</sub>}}.

The relation that will be used is a relation between the product of powers that is equal to the [[group (mathematics)|neutral element]] of {{math|''G''<sub>Δ</sub>}}. These relations will be used to construct a so-called ambiguous form of {{math|''G''<sub>Δ</sub>}}, which is an element of {{math|''G''<sub>Δ</sub>}} of order dividing 2. By calculating the corresponding factorization of {{math|Δ}} and by taking a [[Greatest common divisor|gcd]], this ambiguous form provides the complete prime factorization of {{mvar|n}}. This algorithm has these main steps:

Let {{mvar|n}} be the number to be factored.
{{ordered list
| Let {{math|Δ}} be a negative integer with {{math|1=Δ = −''dn''}}, where {{mvar|d}} is a multiplier and {{math|Δ}} is the negative discriminant of some quadratic form.
| Take the {{mvar|t}} first primes {{math|''p''<sub>1</sub> {{=}} 2, ''p''<sub>2</sub> {{=}} 3, ''p''<sub>3</sub> {{=}} 5, ..., ''p''<sub>''t''</sub>}}, for some {{math|''t'' ∈ '''N'''}}.
| Let {{math|''f''<sub>''q''</sub>}} be a random prime form of {{math|''G''<sub>Δ</sub>}} with {{math|{{pars|s=150%|{{sfrac|Δ|''q''}}}} {{=}} 1}}.
| Find a generating set {{mvar|X}} of {{math|''G''<sub>Δ</sub>}}.
| Collect a sequence of relations between set {{mvar|X}} and {{math|{{mset|''f''<sub>''q''</sub> : ''q'' ∈ ''P''<sub>Δ</sub>}}}} satisfying:
: <math>\left(\prod_{x \in X_{}} x^{r(x)}\right).\left(\prod_{q \in P_\Delta} f^{t(q)}_{q}\right) = 1.</math>
| Construct an ambiguous form {{math|(''a'', ''b'', ''c'')}} that is an element {{math|''f'' ∈ ''G''<sub>Δ</sub>}} of order dividing 2 to obtain a coprime factorization of the largest odd divisor of {{math|Δ}} in which {{math|1=Δ = −4''ac''}} or {{math|1=Δ = ''a''(''a'' − 4''c'')}} or {{math|1=Δ = (''b'' − 2''a'')(''b'' + 2''a'')}}.
| If the ambiguous form provides a factorization of {{mvar|n}} then stop, otherwise find another ambiguous form until the factorization of {{mvar|n}} is found. In order to prevent useless ambiguous forms from generating, build up the [[Sylow theorems|2-Sylow]] group {{math|Sll<sub>2</sub>(Δ)}} of {{math|''G''(Δ)}}.
}}
To obtain an algorithm for factoring any positive integer, it is necessary to add a few steps to this algorithm such as trial division, and the [[Adleman–Pomerance–Rumely primality test|Jacobi sum test]].