Algebraic-group factorisation algorithm

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Algebraic-group factorisation uses special algebraic structures modulo N to help factor N. The idea is to work in a group where the arithmetic encodes the unknown prime factors of N. By the Chinese remainder theorem, arithmetic modulo N corresponds to arithmetic in the reduced groups that come from each prime factor. The goal is to find an element that is not the identity modulo N, but becomes the identity modulo one factor. Such a “one-sided” identity lets us extract a nontrivial factor of N.

How the method works
- Pick any element x in the group modulo N. Build a large multiple A·x, where A is designed to be smooth (made from small prime powers).
- If the order of at least one reduced group divides A, but not all do, this reveals a factor of N. The factor comes from computing a gcd with N.
- A is built as a product of small primes up to a limit B1. You multiply x by these primes step by step and check after each step whether a one-sided identity has appeared.
- There’s a two-stage approach. First, you multiply by all small primes up to B1. Then you look at larger primes between B1 and a bigger limit B2. This lets the order be a product of a large prime and a B1-smooth part, which helps detection.

Two-stage improvements and fast multiplication
- A difference-based method can speed up multiplying by many small numbers, by using differences between consecutive primes.
- A two-step procedure often multiplies x by all primes up to B1 first, then handles primes between B1 and B2. This trades a tighter smoothness requirement for a larger but sparser factor.
- There are refinements such as Montgomery’s prime pairing and the Brent–Suyama extension. A more efficient second stage uses fast Fourier transforms (FFT) for polynomial-style multiplication, which speeds up many group calculations.

Which groups are used
- Multiplicative group modulo N: one-sided identities lead to the p−1 method.
- Multiplicative group of a quadratic extension: one-sided identities lead to the p+1 method. Finding such a quadratic extension involves choosing a parameter and may require trying random values until a non-residue is found.
- Elliptic curves: one-sided identities show up as a failure to invert during point addition. This is the elliptic-curve method (ECM), supported by the Hasse bound on the number of points on an elliptic curve modulo p.
- In practice, the GMP-ECM package implements all three approaches (p−1, p+1, and elliptic curves) and includes efficient two-stage routines and a fast exponentiation algorithm.

Other algebraic groups
- Some proposed ideas use higher-genus curves or Jacobians, but they are usually not practical due to stricter smoothness requirements. They can be interesting in theory, but rarely beat the standard methods.

Complexity and practical notes
- The naive first stage costs roughly proportional to B1 times a factor that depends on the size of N; the prime-powers-only first stage is a bit cheaper in practice.
- The second stage complexity depends on the difference B2 − B1. A standard (difference-based) second stage is linear in B2 − B1, while a polynomial-based second stage can be faster in some regimes, using FFT methods. There’s a trade-off between memory and speed: more memory allows pushing B2 higher and solving more with the same work.
- The choice of B1 and B2, and the stage type, is tuned for the size and structure of N, to maximize the chance of finding a factor quickly.

In short, algebraic-group factorisation is a practical, multi-stage approach to integer factorisation that uses smoothly built group orders and clever stage-two techniques to efficiently expose nontrivial factors of N. It remains one of the key methods used in modern factoring software.