Hacker Read top | best | new | newcomments | leaders | about | bookmarklet login
Ask HN: How can I check if a large number is prime? (b'') similar stories update story
1 points by Kibae | karma 270 | avg karma 4.29 2023-01-31 01:19:26 | hide | past | favorite | 5 comments

I was looking at a list of prime numbers in binary format and I noticed a pattern, where if 2^n - 1, a Mersenne Prime, is in the list, then (2^(n+1) - 2^(n) - 1) is also in the list.

I looked at the list of Mersenne Primes on Wikipedia and checked the primality of (2^43112610 - 2^43112609 - 1) on Wolfram Alpha, but to test for any results larger than that, the results are inconclusive.

The largest discovered prime number is a Mersenne Prime (2^82589933 - 1), so I'm wondering how I can go about testing (2^82589934 - 2^82589933 - 1).



view as:

> I was looking at a list of prime numbers in binary format and I noticed a pattern, where if 2^n - 1, a Mersenne Prime, is in the list, then (2^(n+1) - 2^(n) - 1) is also in the list.

That’s because both are equal. We have

  2^(n+1) = 2 × 2^(n) = 2^(n) + 2^(n)
so

  2^(n+1) - 2^(n) - 1
  = 2^(n) + 2^(n) - 2^(n) - 1
  = 2^(n) - 1

Oh my goodness, you're right...

Haven't kept up with cryptography research but I think msieve is still the current state of the art integer factorization software that's open source


Legal | privacy