Optimal Mersenne Primes Search Using Modular Groups (in Fortran?)

Uncategorized
1

I just released a paper on how to optimally find Mersenne Primes, those of form 2^p - 1.
It’s mathematically super simple, and easy to implement in software.
The paper provides Crystal code for a single core implementation as a proof of concept.

I know Fortran is heavily used in HPC applications, and has decades of proven software for it. I would like to know if the Fortran ecosystem, especially for HPC type application, has the software apps to perform the large number math, and create a distributed network, to perform a GIMPS like search, or is able to hook into the GIMPS apps and use them to do the math, storage, etc, to implement my method?

Thanks.

https://www.academia.edu/178745494/Optimal_Mersenne_Primes_Search_Using_Modular_Groups

1 Like
2

There are some, but you would have to create your own. Which you can now do thanks to AI.

P.S. Is there another way to download your paper? I can’t easily download it.

3

Click the link, then select 'PDF Only" and hit the Download button.

Let me know if you still have problems downloading it.

4

I was able to download the paper, but it took me a bit of clicking, as it was not entirely obvious what was the “button” to only download that paper. Nothing to do with your work, just the curious style of “Academy”. Anyway, you might be interested in the Euler conjecture tutorial, as there a similar number-theoretical approach is taken - Euler Sum of Powers Conjecture: Tutorial.

I have not yet read the paper, but I can imagine that large integers are required. There are various libraries to deal with them in Fortran. One is fmzm, see Arbitrary/multiple precision libraries.

2 Likes
5

I just update the paper|code. It’s now orders-of-magnitude faster, which is explained in the paper.

Here the output. It only stopped because the software couldn’t process larger numbers.

➜ mps ./mpgs
Starting search for next Mp with known p = 3

5, 2, 31

Elapsed time = 00:00:00.000057178

Starting search for next Mp with known p = 5

7, 2, 127

Elapsed time = 00:00:00.000024556

Starting search for next Mp with known p = 7

13, 6, 8191

Elapsed time = 00:00:00.000020819

Starting search for next Mp with known p = 13

17, 4, 131071

Elapsed time = 00:00:00.000026760

Starting search for next Mp with known p = 17

19, 2, 524287

Elapsed time = 00:00:00.000022142

Starting search for next Mp with known p = 19

31, 12, 2147483647

Elapsed time = 00:00:00.000028463

Starting search for next Mp with known p = 31

61, 30, 2305843009213693951

Elapsed time = 00:00:00.000046226

Starting search for next Mp with known p = 61

89, 28, 618970019642690137449562111

Elapsed time = 00:00:00.000059962

Starting search for next Mp with known p = 89

107, 18, 162259276829213363391578010288127

Elapsed time = 00:00:00.000050865

Starting search for next Mp with known p = 107

127, 20, 170141183460469231731687303715884105727

Elapsed time = 00:00:00.000048701

Starting search for next Mp with known p = 127

521, 394, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

Elapsed time = 00:00:00.002608888

Starting search for next Mp with known p = 521

607, 86, 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

Elapsed time = 00:00:00.002203116

6

I updated the code to make it substantially faster. Only prime values of (p + m) are needed. Here’s the modified code to do that. It also keeps the count of the (p + m) primes up to a new Mp. This substantially decreases the search times, and is functionally equivalent to GIMPS, by using just candidates primes to test with, only here we don’t need to create an external list of them.

Here’s the updated code.

p  = ARGV.size > 0 ? (ARGV[0].to_u64 underscore: true) : 3u64
m  = 2u64
tm = Time.instant
primes_tested = 0     # number of primes tested to new Mp
puts "Starting search for next Mp with known p = #{p}"

loop do
  until (p + m).prime?; m += 2 end
  primes_tested += 1
  mp = (1.to_big_i << (p + m)) - 1
  if mp.prime?
    p = p + m
    pp [p, m, primes_tested]
    puts "Elapsed time = #{Time.instant - tm }"
    puts "\nStarting search for next Mp with known p = #{p}\n"
    m  = 2u64
    tm = Time.instant
  else
    m += 2
  end
end

Here’s a comparison of the performance increase compared to the prior version. For large Mp values, the times are cut in more than half, which grows larger as the Mp increase.

Starting search for next Mp with known p = 21701
[23209, 1508]
Elapsed time = 00:05:10.791830961


Starting search for next Mp with known p = 21701
[23209, 1508, 1365]
Elapsed time = 00:02:18.762170756
7

After thinking awhile, I devised a general strategy to do a better than brute force search. It now can use substantially fewer primes than used by GIMPS, which performs a brute force search
by trying every prime between Mp values until a new one is found.

Here are some examples doing brute force searches with the old code|method.

Starting search for next Mp with known p = 9941
[11213, 1272, 131]
Elapsed time = 00:00:17.960902970

Starting search for next Mp with known p = 11213
[19937, 8724, 897]
Elapsed time = 00:05:25.091900197

Starting search for next Mp with known p = 19937
[21701, 1764, 181]
Elapsed time = 00:02:12.907546172

Starting search for next Mp with known p = 21701
[23209, 1508, 156]
Elapsed time = 00:02:18.347536111

Same examples doing better than brute force searches.


Starting search for next Mp with known p = 9941
[11213, 1272, 4]
Elapsed time = 00:00:01.329979669

Starting search for next Mp with known p = 11213
[19937, 8724, 327]
Elapsed time = 00:02:17.546680749

Starting search for next Mp with known p = 19937
[21701, 1764, 23]
Elapsed time = 00:00:21.953398179

Starting search for next Mp with known p = 21701
[23209, 1508, 15]
Elapsed time = 00:00:18.666892607

The details are in the updated paper available at the links, dated Oct 15, 2026