The 22 million digit number and the amazing maths behind primes

PhysOrg ^ | 1/21/16 | Steve Humble

[zeugma]

HA! you lucky bastard. (nerd envy rears it’s ugly head)

There is actually a way to show what the statistical average distribution of primes is in a range of numbers. I think wikipedia has good information about it. The bigger the number, the less primes are around it, generally speaking though.

[2 Kool 2 Be 4-Gotten]

I don’t think so!

22,000,000 the number is small by cryptography standards.

22,000,000 digits i.e. 10 raised to the 22,000,000 power? Not small.

[2 Kool 2 Be 4-Gotten]

Damn!

[CodeToad]

Small, very small.

[AdmSmith]

Fortunately, no full factorization is needed, just a small test factorization up to about 40 000, then the Pollard's (P-1) method and finally Lucas-Lehmer Primality Testing. It is explained here http://www.mersenne.org/various/math.php

But, it is truly amazing.

[zeugma]

it helps quite a bit from what I understand, that Mersenne numbers are of a specialized form. Apparently there are ways of testing primality that don’t involve brute-force factoring of the number. I don’t know if all of those tests are always applicable to any large suspected prime, or if they are only useful for numbers of the specified form. i.e., (2^x)-1

The maths are a bit beyond me on this.