# Optimal Mersenne Primes Search Using Modular Groups (in Rust?) **URL:** \ **Category:** uncategorized\ **Created:** [October 11, 2026, 8:42pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969 "2026-10-11T20:42:01Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![jzakiya](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jzakiya/32/5396_2.png) [@jzakiya](https://users.rust-lang.org/u/jzakiya)\ **Post date:** [October 11, 2026, 8:42pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/1 "2026-10-11T20:42:01Z")
I just released a paper on how to optimally find Mersenne Primes of form 2^p - 1. It's mathematically super simple, and easy to implement in software. The paper provides proof of concept Crystal code for a single core implementation. Currently the GIMPS project generates them by directly computing|testing 2^p -1 by directly using candidate values of p, which my method eliminates having to do. But they already have the software to generate and do the primality tests on those large values, which are 100s of digits long. My question: does the Rust ecosystem have the ability to perform this large number math natively, or able to took into the GIMPS apps and use them to do the math, storage, etc? It would be interesting to have an optimized Rustified version of GIMPS, since it's taking over the world in so many other areas. 😊 [https://www.academia.edu/178745494/Optimal\_Mersenne\_Primes\_Search\_Using\_Modular\_Groups](https://www.academia.edu/178745494/Optimal_Mersenne_Primes_Search_Using_Modular_Groups) ---
**Author:** ![simonbuchan](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/simonbuchan/32/19939_2.png) [@simonbuchan](https://users.rust-lang.org/u/simonbuchan)\ **Post date:** [October 11, 2026, 8:54pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/2 "2026-10-11T20:54:39Z")
> [@jzakiya](#): > > My question: does the Rust ecosystem have the ability to perform this large number math natively You'd have to be a bit more specific about "natively" I guess, but it does provide large number primitives like [carrying\_mul](https://doc.rust-lang.org/stable/std/primitive.u64.html#method.carrying_mul) that LLVM should handle fine without ASM. There's also, of course, plenty of big integer crates like [num-bigint — Rust math library // Lib.rs](https://lib.rs/crates/num-bigint) You shouldn't have any trouble implementing this in Rust, in short. ---
**Author:** ![jzakiya](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jzakiya/32/5396_2.png) [@jzakiya](https://users.rust-lang.org/u/jzakiya)\ **Post date:** [October 12, 2026, 6:59pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/3 "2026-10-12T18:59:17Z")
Thanks. I posted the update paper|code (available at the link) It's now orders-of-magnitude faster. I've posted its output, which only stops because the software couldn't continue to process those larger numbers. But if that is fixed, then anyone on their laptop can generate as many Mp as their hearts|time allows. ```rust ➜ 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 ``` ---
**Author:** ![jzakiya](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jzakiya/32/5396_2.png) [@jzakiya](https://users.rust-lang.org/u/jzakiya)\ **Post date:** [October 13, 2026, 4:16pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/4 "2026-10-13T16:16:57Z")
FYI. Updated paper with this code change to make it faster. ```rust old: p = (Math.log(mp + 1)/Math.log(2)).to_u64 new: p = p + m ``` I'm really busy right now, have some deadlines to meet. It would really be nice if someone would do a Rust version, even if just single core. Someone already emailed me their Pari implementation, with times. Here's output from my single core Crystal version generated this morning, starting from p = 3. ```rust Starting search for next Mp with known p = 21701 [23209, 1508, 402874115778988778181873329071591767722438506891622420041029963578694595240887400867639861461466537103833299413586592359075505942560215384203202392505282949645966546812986702462936795598139258862134305524073117514011710850957577155764134526698071154024866570291655743611106521552616792435986397703408624275326274514077603381064824129105663607213717473307176156322769664543742767983969318459384059938379878060275572931297882085263728828117679720478536475397347975085800596808241438126653968141997207758226940295714228111203845566219741262180987691210467038513314695804493896376930579454464107580662751095564143792253350149446963327062164865068284526946953787948865977316436004163037670156288981621675415729125137439286714883498899856647713325489027165934178641826671600314908207707581913028677627336873027019891101782199420387568674902708563560335665422249993344641004256625323906242830818468942899074234949993913859729756509148940793762235052397899476747243354482142341818566675079971966290454555100106794831122873316939190687807078076069507534444543783013175183099338301868495249460351437732629139146367120478550987016051281632788132605645720897509405100164087829546634973283901954415020317318121023343421442100924240630449162568320542266025029163898709299519931364601129148550918588500543071567482692038979207121165184595857972650794067721766663304877552877530735512541831254657221163688520010481326670262947292075214957731951219393131136071700066722769000670606191390991061973242967512911264351947043296980084166552860987471716618776310267311799281849825634572094586351568980001270007699500229311699965157159517665682831428949194388823813435669597457534867460620737424901559011466473739067552420314197465985734592045469444007987504268282567422361912607903782885199294253733275346340104383835614315889419535761215302433931746650845594336694703703807737307164962815978286100833828641206436538659807846921750141914508632328601539864514384665868751711078980714897238167180581728616753062507511747249245808005997622111641863200180907569048105964570792432318670249656718941478701386677886972338475477550756278048908745855857140396160840915640000152942757067579080105948100791236006113816027294954023517657545229368410211569897436302803253236256834802174708129208380881582322497874260497465180326565377356632463319881488797716878813402070865003833358109311401638399789940308755319571548916779442616446407624398435974737254859567216330307251241356103982692307671884438420399664712045747717349853326279186496926627476702835365616635120395298094996813494640292537645025964806763617960757534317599906545186285779936362239640963157278962749735238734018031963137162294519353089671616839856140612934423376292800357002337948291195231891916319254587638023719991739894135357667509038890693762240291980336551006243082475037374270454634055589954829529267653294431255919681866264708150515182120867007206266224413578578766316288292200080204069908595880864904593530195791992836066271397322016336401432076989173442258953647032430558877151892524852554146167146883853769910561246320694705512457088921711978644056703135770947386634729787650241736975543224255147223770741629765650171444541115341186577164267009666521778404007908942572204437357536447013202320449087374359119884688896570653153635965699349888166816675325403419739923012069285047750708058098369546148066530512705922505763339363973448743551275283628656834670402770338901203538825863885273372725296802331175711226954450363493355782396416901236554095224408448515154810718941778144253019735772286555494888482992676834736600663066924318505506867453994455209613903356661381551303170707697066559694566821068447680650509746035384405738968952295270831628476713602096813200521662297702228641383037720127445077295416522867251086259308924256949130546482529205107067023263892250887651080363021211434271433397608989308330364300732585576535892044008832875413115983363441152995391893368657891779064964168643604233277423002160282408650562356013737533053786211598736805557064344886640795852215801092988641923941455936928232399558235098270821534926531103513400970081240298921105811469814438250610289016969531556231773644918713398451013610901563088260312670567852392406888546913219408585158313060052720828019956940355099824708223899549815719733824216351158321846675607771810334138571606559041577651060598586410945242414351010571013653342029095141793703879402055123962938698179828584589043431623461565217092474712504108095507185137084361406290374948975337884073889633379670194520143162505535982480557240745650789504233993776048710965080738857416484988531003380895803114702386171393470918048735414818380392458071193268641579841938267935481009786061474906992721678353184487194850249990636982112425783667423987765795687026140087895862977235482997376826723315374113237914901333805371711741433497851736832069992653855870002553569186840659098607217033947804144416745928019424098692156435119983976508231816318389379221957628808432933260158025696921301498898560750488043621000694853960738388398663132023687388772635827865444684904043842288121464832536246661065981285950218766526563040447477195329513732641090495498177569836233890464798843005307726003216676981448433911814358187830997562426197639363770484733809493659989183378814319610238163619306208581346901169487332307324999289816374403929506251166966203697910688044201904373375047065577539903412318702343216051705155579477611929334487133386363680801795105965377097317217740629067636115194380331872850516648735434607676631522745733922691440568189717446200213790341992006002410924699429964335507377264900571748863080009435280275806683231919932634328199443166043464046805502904952823468304240431789051431145750174780573029159376608897423116657754646993377252058996584317021186517859545402948554640815812580111812135719244094927777605138918240574534813561862500330654244571788812378520927064783435122985854726038472730062101845156241692016024941211265239314166182038758409312685384765540405212510964896838371037304156419933879530352086544022535109789602027747223650858853482671648101755365481354228091863805011621578883875669404903355089888549376208723682090564341102930475228163313059215959271226081949848477889353337470684677801928746328252980236259643089082064765819268977684271297091434221420402203204816051843790924312901306330991292496802744363898396613407782196679612383549415610569783891526919396336077461916416010666683822481030966646694241533372863428935782537171867644640829719942202233252584945211114561669570501261079454174419086577258210544440106662438203017786099053725933264345420108025868071488561671372008089600018372791881207012696110945775614694650737518542322556296640977293935894214414869438855358753606003397001637907083353780707434779613877126249098033493565718268305571578182703693122089543445743786026405786163677453587602709733484635893390989079294709002676276094965852942303062635499907856117575009515746557862539764756574427752110896827606786025282039152876055050854511817293890036743355523779264511] Elapsed time = 00:05:10.116752597 ``` ---
**Author:** ![06chaynes](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/06chaynes/32/12512_2.png) [@06chaynes](https://users.rust-lang.org/u/06chaynes)\ **Post date:** [October 13, 2026, 5:40pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/5 "2026-10-13T17:40:23Z")
Rust code aside, it seems there is a larger issue with the generator itself, in that it walks odd exponents in order without any skips. Nothing in turn is filtered out because the set already matches what is expected given the walk logic (essentially a noop). Then the check it calls a "primality test" only confirms the number's shape, which every candidate passes (the code does still run a real primality test, so the outputs are fine). So I would think it can't be faster than GIMPS: it tests every odd exponent rather than just primes, with no trial-factoring pre-filter. I'm an idiot though tbf, just seems a new way to find primes super fast is almost like a cold fusion thing. ```rust 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) # build 2^(p+m) - 1 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 # walk m = 2, 4, 6, 8, ... end end ``` 1. `m = 2u64` (start at 2) 2. `mpg(p, m) = (1 << (p + m)) - 1` (exponent is p + m) 3. `m += 2` (step up 2) Since p is an odd prime and m is even, p + m is odd. So that's why I say it walks every odd number (above p) without skips, at least it reads that way to me. ---
**Author:** ![jzakiya](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jzakiya/32/5396_2.png) [@jzakiya](https://users.rust-lang.org/u/jzakiya)\ **Post date:** [October 13, 2026, 7:36pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/6 "2026-10-13T19:36:14Z")
> [@06chaynes](#): > > Since p is an odd prime and m is even, p + m is odd. So that's why I say it walks every odd number (above p) without skips, at least it reads that way to me. That's exactly what it does, because only odd strings of bits can be primes. I just updated the paper again today (dated October 14, 2026, since I updated it today already), to simplify the code again, and clean up|clarify some language. Based on people's commentary, I hope the updated paper shows|answers your questions. If not, let me know. I've been running the updated code starting around 11;10am today (Oct 13, 2026). Here's the latest|largest output its generated so far. ```rust Starting search for next Mp with known p = 23209 [44497, 21288, 854509824303633803193300705318403036509901591304021058343269258282290064782167635856200500014457645861481315295253223674938340502225641436794294836286613933671922838722349286185054453799484919702814066298682412853022594582702532253637046393573819102339382603546705057592743425373988510067594258489091882652816984230481339231089370597522429657962221023625389786838476222562700937572849493656778309709848902611559817481821648562991414301186852631109919628014506891879938269919876375041476054570480393817802067642573802934320804004689212061263134937191146939217967863913998340450302066353316060446899821960016965149455247451256866120416455837785237889442736716622863694799063147972421915137281185223639485530939080700703965630524284803696329522594560178565231006428355914264455809535904827184567881970752815068646412535212946406293446404577519747900684536609902072584992617981311048365318249332003277695727334239248756022919323029881117042744212106822448167090688816268058419617823050362806871644195094989164027842731200313536528752898778625674473549278406773185197120724873440981199286044998761054195231373956949189989191876556229344730115045091462226103168618834097344609997156610133228831405954118698397360867836938451267026626659091843988180773279436086490179650284300557692234183476442984646309183072757232974100222299116389491938691664026821610953870032133749491829983634456251002018767911077341998982406542117192442961159639187837594167906896813306451433188950986000602255947701445471051471124124848433682921474574972057506821415068467850112481880920331630720013627342971796220098146625253125901337980386234817629898710708176158298693133149214166399431656277231164600237527367266776679870865785797830236117277818351059865801588376786510903900434642861824307368660843525509146180113489215970253073134536932334593263343428657338627378492178677797784904272941831813460434829238122857112185866161235173379896102730767761423558393178166224715620952758653591232586065130931612235961024495955052576313785415587572218003004463096123010675460429586233582774784375746614062343087428887376655420063237888060863198948004060435770727103254016551671980979670924439768697027789157597450820625427140967084876253330432907082362616208058343177345138018812833029933660200418178113067998719426282674176029537056946676010743381949863248322018120347951203883971813116798180480041145250934319940195212376997070020403473240618427512395565994017639267642387590352270623403841409398778197965052818880494122679879637450982929872559880623884514662196694567744027940130038179920182595248220029960545836068437836537220421151865495276144874163510998224619086027469138960543563366461310280362835876324827709909151758836738659026346983354907158533741172008557347289191834118874344507211706399728488280164719941918548596996410064074112835516746454014440640147699966792001636649078492049497299992037010722502767123614674570208325085786203978913246013088500640052780403783197363796495378941014322353383867757116808444859236033884177503488694746360263081077518495278672673007687714633814675074081403927708449052582362241943697206287236587208562293641356094566185255157887794517532173283111833000302025613005213405482252878149070265205440373545426910161611341185559050988906020137614109481965847736796392112521375419675323000779270489340923806543050956827559032136728828425649916323160041509893239953929650589544864646169009568125970129331389668409973033907297445999076186651095765310311061043682896569016209694536996136266470191569408033323541694057386738735231465391417715857531488577897250851792909910169470724853261427849940549334305896475592823992656458347993884214575074296814676874464971197215649974506724058916041508916049169707455165438683627351824021232173847650175009569246844585339764331444039879715595935280515640897481257047884715263635621831312250733095244741473379412994928937246504471873360093422945901669688636733052872215188392668343870518332217357980686070609320554480910523795553942258900948600643831553785127382196992543338144141784198002454900271443091682756574616685753240566083384505911986644720838738796540754497874824089314354427768560390125821906974331377915589874833096832220364826214637532467443257219325373542595632168868196845662314535257745740540690088721258932375726926780766042960522570262391944742291827500524719618152204706641289353527039250445951674387140964202979771525691667923635515333128240868122085666451405605834956472406582298196815961996323161565850516941679845809803706388743206005082498287908828447142468612698942513775417111948840517510717444158415311425872235504912292900931530294540012529260625223947584186787091065270997026119386422407099057687522692243445528559804365149519299366360636524787812055597948447738733157386435933019181691527123300142439165132639220658338166882600717005946057068109508190289169077800589855030939849414305609938324421065685342787335122628943893224737558800955291230162354473703668269418246876450051459098729949686427616991310346258467807714200493294634954267280195055460982624792493147249023081291160699372476860084646890874325382990275414749482976830377419937253467357638865913508180286605409768240640904878608687284690578097084189943966991203576327162981834473756946679902799601556403227035997733408463051882878040648605903489943500990090428817282136562244543138227751934870681977529470093118307377797864388134866337375506717466865840299561391687595163814871073257516237138953084739741321046512519898783055985137562909986862822821418697909218618375824776243596129635576799359999369344085923480717698699573491947266917238316136594697515748884132844396814671847273719744879357852879547726224395778018791817246412295326838150979939296919653496539270225341826037714755592301500206279366160321101433476538168211877778289236382492839507816309054101996807881965990251144060531583269667332503639847271289331205431366064069530883820899868706709436836481848789690764673023862695740597045358606957928324456815766130005846385401900094395353684780895776336253796523782075679613024968339290175813865387793255361742847784029992110588949340556741643663846869775018478118394443365250793299817506244603536408515810504456085656681183484766909632504119159101857786213084370375778253371993950568270608368720255920096107484259695785002799244185251870094775729333995933499076257379601075025939759382282614484710286255549932745375952696109293041118929794123755168354275719367365141154223682577274756986939801666353878982712419672047895827951421563601304219352939201617281945130711444593498910500078357202775578698708417758650476732444321615389586337183178052363104577036667976981794379775137254974699125521663805999652545541936035723389826056812617646779754277945047644116609828329736790436393517413288251558898045514749445906423194323706306414119366629747907481287373940832842913969451233186914869606743291916409591019592632025299628197611384253264924748540717955006148011213196330973338173358350731330358801176687055820667007316206485174294980719681580611007576366315566817988676676629818069714322226851713501056676703693691882424689948234282990975689672226518343470550974174195976295776513379484342672440028765751071277361281234011824451864987118511900268023620660925537819599017123223240195222037027161559785371968202312289222379716023280199762503203345842364475873165443711996121637218656014077109938287634462641911237643661498730924997478477798307306107972975765021697764315038032227248049476011713075846328424181343680728329020299532724418468785014598773583912750973647902334456053103347236956679606482172145264307156698559926286047178503741949513540448038604980058134803318961867847317924106411305428822060455457034623993478081873112040879949284318699106416865521492614531231783253320962518186939715705143181582332451403715983077334128673665133436729743874451580776248833276287003390901217261036364534945948597578267069197289616142254891035095245916484120686035290315924214004246222851715780026230502200012304905654599808044383293639930610712768452762188272135526848937482560309725734239359041881081604932493295818851065897194460578664420343244668944218859930843009169151416439747854996132480384642823239375104265690829603313763978877633592443681156487226034007047864955055396171494523624931526010865247828680422244153827517874928298622742605275785719186799859505979308352491593626969988121413269340766953822202945692532342274077693139016760771380343305198289191630235123888130456500445772972946518534337647490350165170146543325102202345905951720938063341522132865825600159040043213174225940378385162335105254933060024773771167209509009338521005232769588766592518165697175352104674517670696569105465127985627784868398418070770887556648506376679874586510201116038731912112614381982989015173251887069224596014819312276729672573465458064549365015500115328448677712179357286925172763809121710405012759558336757794987895061919977712975746432004968898100686118376848236917818928054045219935018646614556888891673782521226109539876603853518249396964141573474411786178864152187231072872681832426617408041561826083277082996504979905121576729761882674166062981961840205928992149503122068791348059470110958176511423269913276037734681753745733428156637089438932739933696432356682668732464139632035094818062195320955001580567851453434840805453125631107205858205890026353091573367671720125016243983573396956393115752805646325308011707276533642086384504961180674698139170920517060518064920905572492922057196081196237682745164205846001032313420319686537276432540345071367632274054907466295796072834575234227652980765772996039382235258886338751540189442236614051487377368191871254652241540528333803670931581186398680731835448665759542476167180453375355150728414382395794212745437166115535367048263957768441505047319734903176176353583999693271099471070016855442488574546932825424729408666367431733711263035317370459792311926982579362304589031818587148975192530703366798574784205700976688975137170702704092122565561067535398561047770288142891333643540586094191942881098885861170676614495216217663224969625604494749752841526809562332705130595227694664136670233457880177927254357892280283501771674153340181295757185220624956488625960241342854349445359997526435561960392392589534148436324133221048085564212838030416837663335740949389023767630410667756195923000289601031700507406595751284778714617941817407995143996744786287420431561654314601536316419773722086777893902300557814544690726153524427504853234241083524047092443029212029099057510938541927161209092151527496660113715920637523480328430989742744810118275178802273249944379671941834661049810424824484335554854300332454752382382575387785362503969349048207228022378600321077242427273559577596216705954978385577476832481767698691019969363764124908054104431258135562309403229995669410507869061560001668799471259677428825587266421236272771356548966731920925935827605895525944958390557775188182599430773976329437360627262869464537271395411127635295102553106088630644348895245378046988082281991300125435706980577758382748696320651710629889378007269601604348150095922464466723718089944069302233407247100092030141634979668048628892544474704539980677959253045377690089917491920942135794067331069174835878047355763069916910505856744867228478819552076510220321221144225115311556902621320151580940631531454823566207528919787538960710731134397251446863301951561400004159243550508846994979870220021654014363061263907055278823448015537418189345262220832101054862193900982756780966682798488261862603073406590467181148676985277920649376717780278320966958417359163686441603606338188292114506821091632091406602191783475767863949798191920391303037823635440366852329792530304401282072217590937306513920702609468017126262860885494045694567006749197056309580643372985177988939029566239014458631659924443381694125529837649434600565981192424844144940596207132164490577515769239206357734633567452508425758085518073722500745788910329276083662174307997019821662396368784000485410203494746501418379420966077237082321290470478615887034185693579996771486215404804695481122481571513704280852627012186267469991635981685640889473373475894097871907535351273155661295260715372756782780366420854197224596223931832477283860850556978410751616679570401202979195793508679229270695813501332563153166070154095763822082051684399748732729553965958532985987911797902110713318155368558266214589918316073370489457222186414248641266582577935019778268426880584442584972373506134982469960153759083758243333220265889317394698666742717430467634753497645506911473017508272050122325088825503782634226189081418110360232044483094917122073348832945196558930045450606186630066464264923682396019146123557820494410011041105352029248308941356759691092988813708083281472269286627276152071817520526023642930790051602960171096698266145887952446714972709623121336088800287469715461344195144343476677832930394086124235564902368800329544881012516861962147429738421449344065429019424751594247732152478118453408107243377529364274352501904296565836899003489345368013052920775677626638558887457826306248930171608249290273621192147578458420275754041934364280873277576348340883830877789952351851735368425837704493979337701560295930387002196518418354534911347404051951004651581481820521681180801097862520366245152535253445173913441503424092683220656401689350515658469355395408017218547191074429639783599094899320410039863575946472558059877105808942471773922977396345497637789562340536844867686961011228671] Elapsed time = 03:25:22.932911715 ``` ---
**Author:** ![06chaynes](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/06chaynes/32/12512_2.png) [@06chaynes](https://users.rust-lang.org/u/06chaynes)\ **Post date:** [October 13, 2026, 11:59pm UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/7 "2026-10-13T23:59:29Z")
I think what I'm really getting at is that composite exponents are still being walked, so a walk between 23209 and 44497 tests all 10,644 odd exponents, where only 2,033 are prime. Composite exponents can be skipped entirely, since if p = a\*b then 2^a-1 divides 2^p-1. So to me it seems the code ends up testing ~5x more candidates than needed. But take this all with a grain of salt ofc, I'm for sure no expert. ---
**Author:** ![jzakiya](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jzakiya/32/5396_2.png) [@jzakiya](https://users.rust-lang.org/u/jzakiya)\ **Post date:** [October 14, 2026, 2:23am UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/8 "2026-10-14T02:23:00Z")
> [@06chaynes](#): > > I think what I'm really getting at is that composite exponents are still being walked, so a walk between 23209 and 44497 tests all 10,644 odd exponents, where only 2,033 are prime. Composite exponents can be skipped entirely, since if p = a\*b then 2^a-1 divides 2^p-1. So to me it seems the code ends up testing ~5x more candidates than needed. You are exactly correct! Only the prime values of (p + m) need to be used. Here's the modified code to do that, as well as count the number of (p + m) primes up to new Mp. This substantially decreases the search times now, and is functionally equivalent to GIMPS using candidates primes to test with, only here, we don't need to create an external list first. ```rust require "big" require "primes-utils.cr" # provides ‘prime?' 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 ``` I think this is now the fastest MPG code. The ultimate fastest implementation is a multi-core parallel version. Here's an example in the performance increase compared to last version. ```rust 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 ``` ---
**Author:** ![simonbuchan](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/simonbuchan/32/19939_2.png) [@simonbuchan](https://users.rust-lang.org/u/simonbuchan)\ **Post date:** [October 14, 2026, 5:00am UTC](https://users.rust-lang.org/t/optimal-mersenne-primes-search-using-modular-groups-in-rust/142969/9 "2026-10-14T05:00:37Z")
Took a quick poke, seems the `prime?` that `prime-utils` provides from a quick search is a Miller-Rabin test only guaranteed up to 25 digits? I'm not sure if any of the `num-prime`'s configurations match, but with the default configuration for `is_prime()` I get mildly better numbers than your earlier output of the first few values (this is on my somewhat dinky and outdated XPS 13+, so probably not particularly comparable): ```plaintext 5, 2, 1 Starting search for next Mp with known p = 5 Elapsed time = 281.2µs 7, 2, 2 Starting search for next Mp with known p = 7 Elapsed time = 298.3µs 13, 6, 4 Starting search for next Mp with known p = 13 Elapsed time = 259µs 17, 4, 5 Starting search for next Mp with known p = 17 Elapsed time = 243.5µs 19, 2, 6 Starting search for next Mp with known p = 19 Elapsed time = 165.4µs 31, 12, 9 Starting search for next Mp with known p = 31 Elapsed time = 129.2µs 61, 30, 16 Starting search for next Mp with known p = 61 Elapsed time = 175µs 89, 28, 22 Starting search for next Mp with known p = 89 Elapsed time = 793.2µs 107, 18, 26 Starting search for next Mp with known p = 107 Elapsed time = 302.1µs 127, 20, 29 Starting search for next Mp with known p = 127 Elapsed time = 256.9µs 521, 394, 96 Starting search for next Mp with known p = 521 Elapsed time = 8.0918ms 607, 86, 109 Starting search for next Mp with known p = 607 Elapsed time = 5.389ms 1279, 672, 205 Starting search for next Mp with known p = 1279 Elapsed time = 91.4553ms 2203, 924, 326 Starting search for next Mp with known p = 2203 Elapsed time = 539.6406ms 2281, 78, 337 Starting search for next Mp with known p = 2281 Elapsed time = 110.8559ms 3217, 936, 453 Starting search for next Mp with known p = 3217 Elapsed time = 2.0603048s 4253, 1036, 581 Starting search for next Mp with known p = 4253 Elapsed time = 5.2588387s 4423, 170, 600 Starting search for next Mp with known p = 4423 Elapsed time = 1.2408111s 9689, 5266, 1194 Starting search for next Mp with known p = 9689 Elapsed time = 202.7715133s 9941, 252, 1224 Starting search for next Mp with known p = 9941 Elapsed time = 25.4320905s 11213, 1272, 1355 Starting search for next Mp with known p = 11213 Elapsed time = 119.9335619s ``` Code in question: ```rs use num_bigint::BigUint; use num_prime::nt_funcs::is_prime; use num_traits::Pow; use std::time::Instant; fn main() { let mut p: BigUint = 3u32.into(); let mut m = 2u64; let mut primes_tested = 0; let mut tm = Instant::now(); loop { let mut next_p = &p + m; while !is_prime(&next_p, None).probably() { m += 2; next_p += 2u64; } primes_tested += 1; // no BigUint: Shl let mp = BigUint::from(2u32).pow(&next_p) - BigUint::ONE; if is_prime(&mp, None).probably() { p = next_p; println!("{p}, {m}, {primes_tested}"); let next_tm = Instant::now(); println!("Starting search for next Mp with known p = {p}"); println!("Elapsed time = {:?}", next_tm - tm); m = 2; tm = next_tm; } else { m += 2; } } } ``` `num-prime` does require an earlier `num-bigint`: ```toml [package] name = "mp" version = "0.1.0" edition = "2024" [dependencies] num-bigint = "0.4.8" num-prime = "0.7.0" num-traits = "0.2.19" ```