cyclotomy
Cyclotomy is a name used for a method of primality proving begun around 1981 when H. W. Lenstra combined the Jacobi Sum methods of Adleman, Rumely, and Pomerance (the APR-test), with the classical primality tests. It was first implemented by W. Bosma and M. van der Hulst in 1989. Currently cyclotomy (along with other variants of the APR test) and ECPP are the standard methods for general primality proving of integers with 1000+ digits.
The classical tests all require auxilary factoring. In particular they require that we be able to factor n2-1 enough that the factored part is about the cube root of n. This is easy for primes like the Mersenne primes, Woodall primes, Fermat primes,... but not for general primes. Cyclotomy extends these classic test to all the factors of any of the numbers
nk-1 with k < (log n)log log log n.
(In this sense Cyclotomy is neoclassical.) The product of these factors must be at least n1/3 for the test to work.
It is always possible to find the necessary factors. In fact it has been shown that there is always an integer k with
k < (log n)log log log n
for which the factors q dividing nk-1 with q-1 dividing k, have a product at least the size of the square root of n. Usually k is around 100,000,000 for numbers n with about 3,000 digits.
See Also: ECPP
Related pages (outside of this work)