# Optimal Mersenne Primes Search Using Modular Groups

**URL:** <https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207>\
**Category:** Offtopic\
**Created:** [October 11, 2026, 7:46pm UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207 "2026-10-11T19:46:49Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\
**Post date:** [October 11, 2026, 7:46pm UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/1 "2026-10-11T19:46:49Z")

</div>

I just released this paper (extracted from a larger journal article slated for Dec 2026) which uses Crystal code to show how to sequentially generate Mersenne Primes without computing 2^p - 1.

The code is the single core version. I haven’t had a chance yet to do the multi-core parallel version.

As these numbers become humongously large, it would require special software to generate and check 100s of digits values.

It would be nice if there could be some Crystal hooks into such existing software, to be able to write and run complete MPGS searches with it. So if anyone knows how to do that, or feels inspired to try, let me know.

[https://www.academia.edu/178745494/Optimal\_Mersenne\_Primes\_Search\_Using\_Modular\_Groups](https://www.academia.edu/178745494/Optimal_Mersenne_Primes_Search_Using_Modular_Groups)

---

<div class="post-metadata">

**Author:** ![kojix2](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/kojix2/32/1583_2.png) [@kojix2](https://forum.crystal-lang.org/u/kojix2)\
**Post date:** [October 12, 2026, 2:02am UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/2 "2026-10-12T02:02:37Z")

</div>

I realize you probably don’t want this, but it’s still better than no one replying at all.  
So, I’m acting as [a meat proxy](https://gruhn.me/blog/2026-08-03/) 🍖 here and posting the results of ChatGPT’s review so that visitors to this page can read them.

> ### Claims of the paper
> 
> - The paper proposes generating Mersenne prime candidates using the exponent `m` of a known Mersenne prime, updating `m` whenever a new one is found.
> - It claims that avoiding prime exponent enumeration and reducing candidate density makes the method faster than GIMPS.
> 
> ### Algebraic relationship
> 
> - The formula is `G_m(k) = 2^m * (3k+1) - 1`. For odd `m` and odd `q > m`, `G_m(k) = 2^q-1` requires `k = (2^(q-m)-1)/3`.
> - [OEIS A002450](https://oeis.org/A002450) gives `a_j = (4^j-1)/3` (`j >= 1`), producing `1,5,21,85,...`.
> - Since `G_m(a_j) = 2^(m+2j)-1`, this is equivalent to enumerating odd exponents `m+2,m+4,...`. The identity also holds for composite Mersenne numbers and does not establish primality.
> 
> ### Prior work
> 
> - For `m = 3`, the values of `k` producing Mersenne primes through `24k+7` appear in [OEIS A124477](https://oeis.org/A124477) (Artur Jasinski, 2006), matching the paper’s table.
> - The general formula and the procedure for updating `m` also appear in the [author’s earlier paper](https://vixra.org/pdf/2006.0054v1.pdf) (revised 2019, published 2020).
> 
> ### Computational complexity
> 
> - The paper’s `k += 2` implementation requires `(2^(q-m)+2)/6` iterations to reach exponent `q`, growing exponentially with `q-m`.
> - From `m = 31` to `q = 61`, this requires **178,956,971 iterations** , compared with only **7 prime exponents** in the same range.
> - The [author’s 2024 implementation](https://forum.crystal-lang.org/t/optimized-mersenne-prime-search/7371) uses `k_next = 4*k+1`, reducing this to 15 iterations, or 7 candidates requiring primality testing after filtering prime exponents.
> - Direct enumeration of prime exponents produces the same 7 candidates. [GIMPS](https://www.mersenne.org/various/works.php) additionally uses factorization methods, PRP tests, and Lucas–Lehmer tests.
> - Therefore, reducing candidate density among all integers does not, by itself, demonstrate a computational advantage over existing methods.

I don’t understand any of the mathematical content. I simply invested in tokens and managed the direction of the answers through chat 🫠

---

<div class="post-metadata">

**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\
**Post date:** [October 12, 2026, 4:00am UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/3 "2026-10-12T04:00:05Z")

</div>

That’s really interesting AI “commentary” . It would be really interesting if it could design an optimized distribute GIMPS like network (in whatever language(s)).

The main benefits of this method are:

1. You don’t have to generate and verify a list of sequential candidate primes to use as p values, which is a resource intensive undertaking of itself, thus freeing up the work|time used to first find them, e.g. the memory needed to hold the primes list of ever increasing candidate primes values.

2. Only one generator form is needed, which uses a single starting known prime p value. The k values can be generated|tested in parallel, making it amenable to massive multi core systems like GPUs, HPCs, etc

3. The process not only finds Mersenne Primes, but other large residue primes between the consecutive Mp values. Thus the first prime found with this process greater than the current largest Mp will be the next largest known prime, but likely not an Mp.

4. With additional research, it’s highly likely a way to reduce the number ranges for the k values can be found to narrow the search scope, thus increasing the search speed.

The GIMPS software uses specialized apps that can compute and do primality test on these large integer numbers. I’m not aware of anything in the Crystal ecosystem equivalent to them, though over time, maybe there would be interest to provide some of them.

One of the beautiful advantages of Crystal language wise is, it’s soooo easy to at least prototype working software (as shown in the paper) to demonstrate it’s validity for small values. It then merely becomes scaling it up to perform with very large numbers.

---

<div class="post-metadata">

**Author:** ![weirdbricks](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/weirdbricks/32/1741_2.png) [@weirdbricks](https://forum.crystal-lang.org/u/weirdbricks)\
**Post date:** [October 12, 2026, 5:57am UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/4 "2026-10-12T05:57:35Z")

</div>

The math is far beyond my understanding but I’m stoked that you’re using Crystal to do this work!

---

<div class="post-metadata">

**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\
**Post date:** [October 12, 2026, 6:15pm UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/5 "2026-10-12T18:15:18Z")

</div>

Ok, major upgrade.

I figured out how to do away with using|iterating over k values. I explain the process in the updated paper, which has this updated, orders-of-magnitude faster code.

```auto
require "big"
require "primes-utils" # provides ‘prime?'

def mpg(p, m) mp = (1.to_big_i << (p + m)) - 1 end

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

loop do
  mp = mpg(p, m)
  if mp.prime?
    p = (Math.log(mp + 1)/Math.log(2)).to_u64
    pp [p, m, mp]
    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

```

It now produces _ **scarily** _🫣 fast times.

```auto
➜ ./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

Starting search for next Mp with known p = 607
Unhandled exception: Arithmetic overflow (OverflowError)
  from /home/jzakiya/crystal/share/crystal/src/crystal/system/unix/time.cr:44:35 in '__crystal_main'
  from /home/jzakiya/crystal/share/crystal/src/crystal/at_exit_handlers.cr:21:26 in 'main'
  from /home/jzakiya/crystal/share/crystal/src/crystal/system/unix/main.cr:10:3 in 'main'
  from /lib/x86_64-linux-gnu/libc.so.6 in '??'
  from /lib/x86_64-linux-gnu/libc.so.6 in '__libc_start_main'
  from ./mpgs1 in '_start'
  from ???
➜ mps 

```

You see it only stopped because of the limitations of the software to continue processing the large numbers using p = 607. So now the algorithm|code is no longer time limited, but is software limited. If that can be resolved in Crystal I can find a new largest Mp by next week, since it’s now so fast. 😄

---

<div class="post-metadata">

**Author:** ![ComputerMage](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/computermage/32/719_2.png) [@ComputerMage](https://forum.crystal-lang.org/u/ComputerMage)\
**Post date:** [October 12, 2026, 11:01pm UTC](https://forum.crystal-lang.org/t/optimal-mersenne-primes-search-using-modular-groups/9207/6 "2026-10-12T23:01:03Z")

</div>

Hi Jabari,

I decided to help you a little and to improve the performance for your Crystal version.

I (together with my GPT 5.1 Sol + Luna agents) built a faster version of Mersenne Primes Search.  
It can be found at [GitHub - skuznetsov/mersenne-crystal-lab: Reproducible Crystal CPU/Metal experiments for Mersenne small-factor screening, with matched GMP baselines. · GitHub](https://github.com/skuznetsov/mersenne-crystal-lab)  
It has CPU, Metal and CUDA versions. CPU and Metal versions were validated, CUDA has to be validated on Nvidia video cards.

CPU speed is **1.49** times faster than your last version you just posted.

More details can be found @ [mersenne-crystal-lab/reply.md at main · skuznetsov/mersenne-crystal-lab · GitHub](https://github.com/skuznetsov/mersenne-crystal-lab/blob/main/reply.md)