Euclid's formula states that all perfect numbers can be written as (2^p - 1)*(2^(p - 1)), where 2^p - 1 is a prime number.
Thus, a list of perfect numbers gives all the primes of the form 2^p - 1, which are also called Mersenne primes.
The gaps between Mersenne primes are large, which is helpful in the search for cryptographically useful prime numbers.
A program to find large primes would have the following steps:
1. Evaluate 2^p - 1 for value p
2. Check if the last digit of the result of step 1 is 1, 3, 7, or 9
3. If step 2 is passed, evaluate (2^p - 1)*(2^(p - 1))
4. Check to see if the result of step 3 is a perfect number
5. If the result of step 4 is a perfect number, 2^p - 1 is a Mersenne prime
All the numbers given by Euclid's formula are even, thus the factorization of any perfect number is much easier to compute than the integer factorization problem. The test for whether a number is perfect is also much easier than trial division of a suspected prime.
Example: if p = 5, we get
2^5 - 1 = 31
(31)*(2^(5 - 1)) = 31*16 = 496
The factors of 496 are 248, 124, 62, 31, 16, 8, 4, 2, and 1, with 31 and 2 being the prime factors.
The sum of all the factors of 496 is: 248 + 124 + 62 + 31 + 16 + 8 + 4 + 2 + 1 = 496
Thus, 496 is a perfect number and 31 is prime.
A key step in the program would be recognize the first odd number and then go to the next power of 2 lower.
No comments:
Post a Comment