Algebraic-group factorization algorithm

Algebraic-group factorization 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.

Algebraic-group factorization 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. 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/N\mathbb Z [ \sqrt t] is actually a quadratic extension of \mathbb Z/N\mathbb Z without knowing the factorisation of N. 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 non-residue fairly quickly. If t is 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 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 naive first stage uses O(B_1 \log (B_1) M(\log (N))) bit operations, while the prime-powers-only first stage takes O(B_1 M(\log (N))) , with N being the number-to-be-factored and M(x) denoting the cost of multiplying two x-bit integers (practically M(\log (N)) = O(N \log (N) \log \log (N)) using FFT-based methods). The standard (difference-based) second stage uses O((B_2 - B_1) M (\log (N)) ) bit operations. The polynomial-based second stage uses O(\sqrt{B_2- B_1} \log (B_2- B_1) M(\log (N))) bit operations (the B_1 term can be discarded assuming B_2 >> B_1 , which is often the case). Varying the size of the convolution gives a trade-off between memory and space: for each doubling of memory usage, double the amount of advancement in B_2 can be made for the same amount of computation. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375465264 under CC BY-SA 4.0; modifications have been made.