Lab 6: 6a, 6b, 7

[BertLisser]

6a(<-10)
Nice clear presentation.
6b

isMersennePrime :: (Integer -> IO Bool) -> Integer -> IO Bool
isMersennePrime f n =
  do
    isP <- f 2
    isMp <- f (2 ^ n - 1)
return (isP && isMp)

I don't understand isP <- f 2

findMersennePrimesMR 1 primes

You have luck with parameter 1. Sometimes it detects pseudoprimes.
6b(<-8)

7 (<-10)

[schneider-simon]

Hello Bert,

thank you for your feedback.

You are indeed right that isP is a bit strange since it is a typing error isP <- f 2 instead of isP <- f n. However, this does not play a role since n is always a prime number, because of findMersennePrimesMR 1 primes.

Concerning the low value for k: We explicitly chose a small value for k to improve our performance. We talked about this in our discussion - all outputted numbers are always pseudoprimes, no matter how large k is.

The "Great Internet Mersenne Prime Search" uses the same approach - they try to identify candidates with a very unsafe algorithm (similar to MR with a low k) and then validate if the candidate really is a prime number. Prof. Curtis Cooper (creator of the GIMP project) explains this approach in this interview we watched before the implementation: https://www.youtube.com/watch?v=q5ozBnrd5Zc

Our goal was to find the largest Mersenne prime possible with limited resources and time. It is always necessary to validate large primes found with a non-reliable algorithm like MR - no matter if k = 100 or k = 1.

See in Exercise6b.hs:

Please note:
The outputted numbers are values for the exponent p in 2 ^ p - 1 = mp
AND the exponents are only pseudo-Mersenne prime since p is a prime but
2 ^ p - 1 was checked with the miller-rabbit algorithm (produces false positives)
After finding a pseudo-Mersenne prime, it has to be checked for validity!

--> Its computational wise faster to use the miller rabbit algorithm to find
mersenne prime candidates than using a "safe" approach.

Comparing the list with https://primes.utm.edu/mersenne/ shows that the numbers
found are actually Mersenne primes.

Maybe you could take our discussion into consideration. I would not use a larger k if I had to reimplement the Mersenne prime search again.