Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Algebraic-group factorisation algorithm
open-in-new
<p>Algebraic-group factorisation algorithms are algorithms for <a href="/facts/Integer_factorization/EjMCTz2t">factoring an integer</a> <i>N</i> by working in an <a href="/facts/Algebraic_group/DDtBCIvh">algebraic group</a> defined <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> <i>N</i> whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors <i>p</i>1, <i>p</i>2, ... By the <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a>, arithmetic modulo <i>N</i> corresponds to arithmetic in all the reduced groups simultaneously. </p><p>The aim is to find an element which is not the identity of the group modulo <i>N</i>, but is the identity modulo one of the factors, so a method for recognising such <i>one-sided identities</i> is required. In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged. Once the algorithm finds a one-sided identity all future terms will also be one-sided identities, so checking periodically suffices. </p><p>Computation proceeds by picking an arbitrary element <i>x</i> of the group modulo <i>N</i> and computing a large and <a href="/facts/Smooth_number/pC6DVLJW">smooth</a> multiple <i>Ax</i> of it; if the order of at least one but not all of the reduced groups is a divisor of A, this yields a factorisation. It need not be a prime factorisation, as the element might be an identity in more than one of the reduced groups. </p><p>Generally, A is taken as a product of the primes below some limit K, and <i>Ax</i> is computed by successive multiplication of <i>x</i> by these primes; after each multiplication, or every few multiplications, the check is made for a one-sided identity. </p>