Mersenne Prime - Factorization of Mersenne Numbers

Factorization of Mersenne Numbers

The factorization of a prime number is by definition the number itself. This section is about composite numbers. Mersenne numbers are very good test cases for the special number field sieve algorithm, so often the largest number factorized with this algorithm has been a Mersenne number. As of August 2012, 21061 − 1 is the record-holder, using the special number field sieve. See integer factorization records for links to more information. The special number field sieve can factorize numbers with more than one large factor. If a number has only one very large factor then other algorithms can factorize larger numbers by first finding small factors and then making a primality test on the cofactor. As of December 2011, the composite Mersenne number with largest proven prime factors is 226903 − 1 = 1113285395642134415541632833178044793 × p, where p has 8063 digits and was proven prime with ECPP. The largest factorization with probable prime factors allowed is 21168183 − 1 = 54763676838381762583 × q, where q is a 351639-digit probable prime.