Algebraic-group factorisation algorithm

Algebraic-group factorisation algorithm

Algebraic-group factorisation algorithms are algorithms for factoring an integer "N" by working in an algebraic group defined modulo "N" 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 "p"1, "p"2, ... By the Chinese remainder theorem, arithmetic modulo "N" corresponds to arithmetic in all the reduced groups simultaneously.

The aim is to find an element which is not the identity of the group modulo "N", but is the identity modulo one of the factors, so a method for recognising such "one-sided identities" 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.

Computation proceeds by picking an arbitrary element "x" of the group modulo "N" and computing a large and smooth multiple "Ax" 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.

Generally, A is taken as a product of the primes below some limit K, and "Ax" is computed by successive multiplication of "x" by these primes; after each multiplication, or every few multiplications, the check is made for a one-sided identity.

The two-step procedure

It is often possible to multiply a group element by several small integers more quickly than by their product, generally by difference-based methods; one calculates differences between consecutive primes and adds consecutively by the d_i r. This means that a two-step procedure becomes sensible, first computing "Ax" by multiplying "x" by all the primes below a limit B1, and then examining "p Ax" for all the primes between B1 and a larger limit B2.

Methods corresponding to particular algebraic groups

If the algebraic group is the multiplicative group mod "N", the one-sided identities are recognised by computing greatest common divisors with "N", and the result is the "p" − 1 method.

If the algebraic group is the multiplicative group of a quadratic extension of "N", the result is the "p" + 1 method; the calculation involves pairs of numbers modulo "N". It is not possible to tell whether mathbb Z/nmathbb Z [ sqrt t] is actually a quadratic extension of "N" without knowing the factorisation. This requires knowing whether "t" is a quadratic residue modulo "N", and there are no known methods for doing this without knowledge of the factorisation. However, provided "N" does not have a very large number of factors, in which case another method should be used first, picking random "t" (or rather picking "A" with "t" = "A"2 − 4) will accidentally hit a quadratic residue fairly quickly. If "t" is not a quadratic residue, the p+1 method degenerates to a slower form of the "p" − 1 method.

If the algebraic group is an elliptic curve, the one-sided identities can be recognised by failure of inversion in the elliptic-curve point addition procedure, and the result is the elliptic curve method; Hasse's theorem states that the number of points on an elliptic curve modulo "p" is always within 2 sqrt p of "p".

All three of the above algebraic groups are used by the [http://gforge.inria.fr/projects/ecm/ GMP-ECM] package, which includes efficient implementations of the two-stage procedure, and an implementation of the PRAC group-exponentiation algorithm which is rather more efficient than the standard binary exponentiation approach.

The use of other algebraic groups—higher-order extensions of "N" or groups corresponding to algebraic curves of higher genus—is occasionally proposed, but almost always impractical. These methods end up with smoothness constraints on numbers of the order of "p""d" for some "d" > 1, which are much less likely to be smooth than numbers of the order of "p".


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pollard's p - 1 algorithm — Pollard s p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest …   Wikipedia

  • Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Splitting of prime ideals in Galois extensions — In mathematics, the interplay between the Galois group G of a Galois extension L of a number field K, and the way the prime ideals P of the ring of integers OK factorise as products of prime ideals of OL, provides one of the richest parts of… …   Wikipedia

  • Courbe elliptique — Une sélection de courbes cubiques réelles définies par l équation y2 = x3 + ax + b.. La région montrée est [ − 3,3]2. La courbe pour a = b = 0 n est pas elliptique. En mathématiques, une courbe elliptique est un …   Wikipédia en Français

  • Factorization — This article is about the mathematical concept. For other uses, see Factor and Integer factorization. A visual illustration of the polynomial x2 + cx + d = (x + a)(x + b) where… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”