Integer factorization: Difference between revisions

Revision as of 07:37, 27 May 2024

Revision as of 10:57, 27 May 2024

Line 142:

=== Schnorr–Seysen–Lenstra algorithm ===

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

Denote by {{math|''P''_Δ}} the set of all primes {{mathmvar|''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''_Δ}} and prime forms {{math|''f''_''q''}} of {{math|''G''_Δ}} with {{mathmvar|''q''}} in {{math|''P''_Δ}} a sequence of relations between the set of generators and {{math|''f''_''q''}} are produced.

The size of {{mathmvar|''q''}} can be bounded by {{math|''c''₀(log{{abs|Δ}})²}} for some constant {{math|''c''₀}}.

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''_Δ}}. These relations will be used to construct a so-called ambiguous form of {{math|''G''_Δ}}, which is an element of {{math|''G''_Δ}} 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 {{mathmvar|''n''}}. This algorithm has these main steps:

Let {{mathmvar|''n''}} be the number to be factored.

{{ordered list

| Let {{math|Δ}} be a negative integer with {{math|1=Δ = −''dn''}}, where {{mathmvar|''d''}} is a multiplier and {{math|Δ}} is the negative discriminant of some quadratic form.

| Take the {{mathmvar|''t''}} first primes {{math|''p''₁ {{=}} 2, ''p''₂ {{=}} 3, ''p''₃ {{=}} 5, ..., ''p''_''t''}}, for some {{math|''t'' ∈ '''N'''}}.

| Let {{math|''f''_''q''}} be a random prime form of {{math|''G''_Δ}} with {{math|({{pars|s=150%|{{sfrac|Δ|''q''}})}} {{=}} 1}}.

| Find a generating set {{mathmvar|''X''}} of {{math|''G''_Δ}}.

| Collect a sequence of relations between set {{mathmvar|''X''}} and {{math|{{mset|''f''_''q'' : ''q'' ∈ ''P''_Δ}}}} 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''_Δ}} 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 {{mathmvar|''n''}} then stop, otherwise find another ambiguous form until the factorization of {{mathmvar|''n''}} is found. In order to prevent useless ambiguous forms from generating, build up the [[Sylow theorems|2-Sylow]] group {{math|Sll₂(Δ)}} 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]].