Reply to post: Some background

Give a boffin a Xeon and a big GPU, get a new big prime number

GrumpenKraut Silver badge

Some background

Finding huge Mersenne primes is (comparatively) easy because there is the Lucas-Lehmer primality test.

For numbers of the form C^N+1 where C is factored (here: 919444 = 2 * 2 * 53 * 4337 and N=2^20) one can try to find a primitive root (of the multiplicative group). In other words, Pratt's primality certificate is doable.

For "random" numbers of this size (random meaning not of some rather special form) proving primality is way out. Still a huge number "surviving" several rounds of the Rabin-Miller (compositeness!) test can safely be assumed to be prime.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2019