News for hackers. Stuff that matters.
Re:2^74207281-1 is Prime by haberman on Tuesday January 19, 2016 @01:30PM (#10932737)
> 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?

Re:2^74207281-1 is Prime by dmunoz on Tuesday January 19, 2016 @02:04PM (#10933028)
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...

Re:2^74207281-1 is Prime by ajuc on Tuesday January 19, 2016 @01:40PM (#10932824)
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).

Re:2^74207281-1 is Prime by kale on Tuesday January 19, 2016 @02:24PM (#10933209)
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.

Re:2^74207281-1 is Prime by skj on Tuesday January 19, 2016 @02:56PM (#10933467)
Or any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
Re:2^74207281-1 is Prime by spdionis on Tuesday January 19, 2016 @03:48PM (#10933880)
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
Re:2^74207281-1 is Prime by saganus on Tuesday January 19, 2016 @01:42PM (#10932844)
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