3 ms·

> The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU. How does this work? You just try to divide by every possible numbe

> The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU. How does this work? You just try to divide by every possible number and ensure the result isn't an integer?

ajuc 11y ago
You only need to divide by prime numbers up to ceil(sqrt(your_number)). They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).
- kale 11y ago
  That would still take an eternity. They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor). If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time. Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.
- skj 11y ago
  Or any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
- spdionis 11y ago
  This are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes
saganus 11y ago
I believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number. There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number. [0] https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test
dmunoz 11y ago
They use the Lucas–Lehmer primality test [0], along with trial factoring candidate numbers up to a given bit depth to sift out some composites from the prime candidates quicker than a full LL test. [0] https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

> The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU. How does this work? You just try to divide by every possible number and ensure the result isn't an integer?

ajuc 11y ago

You only need to divide by prime numbers up to ceil(sqrt(your_number)). They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).

kale 11y ago
That would still take an eternity. They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor). If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time. Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.
skj 11y ago
Or any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
spdionis 11y ago
This are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes

saganus 11y ago

I believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number. There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number. [0] https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test

dmunoz 11y ago

They use the Lucas–Lehmer primality test [0], along with trial factoring candidate numbers up to a given bit depth to sift out some composites from the prime candidates quicker than a full LL test. [0] https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...