-
Notifications
You must be signed in to change notification settings - Fork 0
/
generate_psp_from_root.sf
52 lines (49 loc) · 15.7 KB
/
generate_psp_from_root.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/usr/bin/ruby
# Generate Fermat base-2 pseudoprimes from a given root.
#var arr = [522925572082528736632187, 1820034970687975620484907, 4263739170243679206753787, 4360728281510798266333387, 28541906071781213329174507, 33833150661360980271172507, 84444874320158644422192427, 175352076630428496579381067, 270136290676063386556053067, 615437738523352001584590187, 3408560627000081376639770587, 11260257876970792445537580187]
#var arr = [26641259752490421121, 1457836374916028334162241, 24541683183872873851606952966798288052977151461406721, 53487697914261966820654105730041031613370337776541835775672321, 58571442634534443082821160508299574798027946748324125518533225605795841]
#var arr = [3183276534603733, 11861640972220321, 26862493078871893, 51516243805731301, 190276732600534693, 245840587068477781, 386096840467598593]
#var arr = [42310088783100741554666880481, 21593590390253023722267234622513201, 16412975107923138847512341751620644377601, 325533792014488126487416882038879701391121]
#var arr = [9857524690572481, 33439671284716801, 96653613831890401, 270136961300544031, 528096456788419441, 650643395658753601, 710238404427321601, 1822922951416158241, 4011563714063821201, 4525693104167627041, 4631812281009523441, 7049793086137296001, 8605736094003523201, 10449416165574628801, 11175581620177915681, 12746447178170148001, 12769123623410580481, 17705945296667070001]
#var arr = [12062716067698821000001, 211215936967181638848001, 411354705193473163968001, 14295706553536348081491001, 32490089562753934948660824001, 782293837499544845175052968001, 611009032634107957276386802479001]
#var arr = [192739365541, 461574735553, 10028704049893, 84154807001953, 197531244744661, 973694665856161, 3060522900274753, 3183276534603733, 11861640972220321, 26862493078871893, 51516243805731301, 190276732600534693, 245840587068477781, 386096840467598593]
#var arr = [18677955240001, 458631349862401, 286245437364810001, 312328165704192001]
#var arr = [26641259752490421121, 1457836374916028334162241, 24541683183872873851606952966798288052977151461406721, 53487697914261966820654105730041031613370337776541835775672321, 58571442634534443082821160508299574798027946748324125518533225605795841]
#var arr = [63973, 192739365541, 461574735553, 10028704049893, 84154807001953, 197531244744661, 973694665856161, 3060522900274753, 3183276534603733, 11861640972220321, 26862493078871893, 51516243805731301, 190276732600534693, 245840587068477781, 386096840467598593]
#var arr = [294409, 56052361, 118901521, 172947529, 216821881, 228842209, 1299963601, 2301745249, 9624742921, 11346205609, 13079177569, 21515221081, 27278026129, 65700513721, 71171308081, 100264053529, 168003672409, 172018713961, 173032371289, 192739365541]
#var arr = [46657, 2433601, 2628073, 19683001, 67371265, 110592000001, 351596817937, 422240040001, 432081216001, 2116874304001, 3176523000001, 18677955240001, 458631349862401, 286245437364810001, 312328165704192001]
#var arr = [2628073, 19683001, 162771337, 110592000001, 432081216001, 2116874304001, 3176523000001, 45959653368000001, 312328165704192001, 4204440099079577973001, 12062716067698821000001, 166907179917730088712001, 211215936967181638848001, 411354705193473163968001, 1445518018084204472472001, 1585481317956993310056001, 14295706553536348081491001, 992582047968915360867561001, 4040041638461720375328768001, 4514616524376898279488000001, 32490089562753934948660824001, 131791785167458780065792000001, 339299689869647426865103569217, 782293837499544845175052968001]
#var arr = [252601, 314821, 1909001, 3581761, 4335241, 5049001, 5310721, 5444489, 15247621, 29111881, 35703361, 36765901, 38624041, 53711113, 68154001, 99036001, 101649241, 104852881, 115039081, 133800661, 161035057, 172290241, 214852609, 238244041, 299736181]
#var arr = [9857524690572481, 33439671284716801, 96653613831890401, 270136961300544031, 528096456788419441, 650643395658753601, 710238404427321601, 1822922951416158241, 4011563714063821201, 4525693104167627041, 4631812281009523441, 7049793086137296001, 8605736094003523201, 10449416165574628801, 11175581620177915681, 12746447178170148001, 12769123623410580481, 17705945296667070001]
#var arr = [443372888629441, 582920080863121, 39671149333495681, 842526563598720001, 2380296518909971201, 3188618003602886401, 33711266676317630401, 54764632857801026161]
#var arr = [68435117188079800987, 164853581396047908970027, 522925572082528736632187, 1820034970687975620484907, 4263739170243679206753787, 4360728281510798266333387, 28541906071781213329174507, 33833150661360980271172507, 84444874320158644422192427, 175352076630428496579381067, 270136290676063386556053067, 615437738523352001584590187, 3408560627000081376639770587, 11260257876970792445537580187]
#var arr = [12876480001, 102293818705, 162303632569, 639554081761, 783962120161, 3224063844001, 4553777859841, 10276904735461, 40867660260505, 51496980091921, 51641004415105, 52412615611201, 52933062609505, 73892907966241, 97388953462801, 107862864807061, 182236335107905, 210587050134721]
#var arr = [19154790699045, 43913624518905, 56123513337585, 162522591775545, 221776809518265, 3274782926266545, 4788772759754985]
#var arr = [576480525985, 1886616373665, 3193231538989185, 11947816523586945, 101817952350880305, 171800042106877185]
#var arr = [141934960805533535384100259905, 21481714221246334566521324297985, 2609668563371076823446624111609234945, 39823778710699695742841310585748767105, 91517623383064245561364437489760682145, 283437449706067209889983933178767178305, 487954732492026166035814706202314376705, 499412475213573176738355575538562510785, 1667290021770201095403065629700606750145, 24496848009559651796239676018610941626785, 73297250063765486245716204161838451864065, 31214532012520383045838858739096429870040705, 125365126527183302043148011968823435306857985, 189113722193582469015226874182815207467976705, 196815537559265035209874062742063577420856705, 214602304120888814092063010092195938453592065, 871005264581548962932418919531990803260747265, 78608978003846049041116965738897583982829325185, 406402829025353014759868508514893182061635216385, 1054353771375531219864416131622474190655479560385, 2497529342332924877105134171746311085591402630465, 8321395327031499581392144057169057667676851380865, 16163138937411407201730795835385583884472576023745, 19944291043277491221878400955113092258507813067585, 64969883450324971076303393673011703445483161551745, 67313152631028760521480057555329912464497126382785, 74875990602425226938138664024259158432269224416705, 75989686810836033659430630396794739057812803595265, 438550573193178260751440867754887273727516317214465, 533076975052547554562094771803380614669259691657985, 6476034191965725664738875807983686448327824830485505, 41874469252684939188766205446627396186239168839365185, 48379566508488575622055850581588165632009391383215745, 59814998665432229834089744101334010488805635671365505, 72057216387777032608301187065391363788323269794759745, 411080929033363473555391879524806756034108137877793665, 610012201694720081796846702960249688144417680786846465, 1018329989576989704159754753835889677652405111555820545, 1027749515814195197950870615261518477976512598053404865, 1089308277895899597186417596452273942827827801935128705, 6792141007930247659612580831051940405232245489721132545, 7678739531271742330943794118368350987916932488808614145, 18862600423988271678875644986362750911465679136559134465, 71637839226104625568428039749667176822512021882103384385, 73257149758147750501240531736307749308900399315221437505, 131393938060059348352532655132697448960788060630502806785, 147722431492705339415781997425542771343697631011575451905, 159794689707372355333060022641622475669953737003517035905, 273144095679252939235857927245653370241323758698067030785, 301665440857953949041553259401389093093907522977903685185, 1172594855911332483974102491005975474562533545673609081345, 4168306949109111474379686622906580020615952735919579025665, 5349457805698512307106674655065437128438739335693225480385, 7583190872114539873321060125323684618509072354028159123265, 10283584008448773696475907793170493467187054108119687416065, 12234418303749373766457825700620527121617068058319432387585, 19810051926806549133247526622166712749924876567141948419585, 31181864586874200535646254647554630886806514113047859293185, 58772050807386648865843953171910036379257828942591085045505, 79615102993580263509479106446502418762547606112620185896705, 82635378868788575647430064182378545917770837975071035716865, 89435572021639193230723806578408893095083926585853507745345, 103461538776511821408206095140694645146310038396156492100545, 165502573617193579886078524884554371013787876466850820614145, 189077537770124861971835596817558772196854831488333103585345, 267784959963229866373534534278260976898219467353932511749185, 369070392893516565676954743410549284718528476924103461811265, 2849415592287421817408189356341963620880286613378173462928385, 8407202972124872375256931092471885668310030843991793216491905, 10649934519495512281862244386450879723780037980908499987548545, 34863998958891679307591791000688445434120146942577693602521345, 56511588686677123690238435995851357647525489518073167567656705, 58109424498388083084293446151725669510763856247238506839632385, 109400466503635187778688237536910752705181679671725472176533505, 463149379463251167706230703520995680069543921166639491398457345, 1690699446901876059668610579970439442290871886615097427974814465, 2845358328636614328617082131255054540223949221002124433109986305, 2963658210542356083852877246926416492931527804540089510269883905, 14701083488299057530174696885922722686956286485260401577115414785, 34876211029082329247213569555171852240834666838025652465732381185, 92912938629279819547534342645052548497217920713200285549935083265, 189340493048741310917683298328059020081147484104707189207601179585, 220258496540970105839863316321479368440458633091652250627182550785, 71967245196653338257378864734797608168672816153312963139871238665985, 129959381219943649417033775959204959948797179242551459265680758859265, 158691907814457458479220201033582552840277423788671901979418171299585, 7062833437200724142430664017877308496583276362473698642553317283474945, 46009993464351973747087455663482348080143005689116838928720068417823745, 155028067161627317530854052699444297997729264222942234687358807669181185, 22321294006753093794484119100782564881584237146952694846489144434824034305, 26323146142093761386080652469589506558048968348929832552142387819284363265, 644811775887535379664225513644980219319376317839497786625735944865592422785, 3975013805230187223393382482115938401564721846649947371792471394797770697985, 19666546275088335320957353962363201658812107005039715284928928608628170883585, 247268394706429287667926073879906993323506152529131362077041417598952609718785, 260349946905396900671119543882338184521094086965438750470975350786567337602945, 321030150905393790929751720043602006651739765349595158023943724894346115208705, 265254290756066930358119577715591455268521886989391944998212913199131074729078785, 1283186592486556731274818824677271745370779905816725683274659717405002608404148545, 2853450403236152332571821875265293508017495635204070217869999840422343584089739265, 10314769048017202862487190022261078137366617506364556874576731255559303133731265345, 11741457044150231137356174490544808074004327146682132288353157271768338063142288065, 19948738964527549499432007591778845447137932958457586625953063419475941273954097665, 61751285336040585295804391670071058142224865543324607243406589162503580666870926270465, 206506498518895650199577226124316092776953187049631892229044263107601141847713087538945, 382314270322310985139418831028955559235551077239363319937510690579825910692881422216705, 1692492088492238622532768569558090666689925078386295740708067178336619326186090793391105, 72148620605333310080719701812041760839024918297692839329815300886091224428394819515628545, 278162906898013748642772019172998608839057854602841254854175736240572851175099616062424065, 772459017179480479061611372132330246001039753130436193419524315193543873326133868681083905, 23016037591494880781207254677674405791538920089036061003925025850757168330033146229133479745, 15076244937897319383799036175429336548625369631595367899653198961989759434810928251355411574785, 369003864634310951251471583928101781391289349473480615361557117731115260969451004130994432230785, 50288615560869993778808557399593955835579110574835306045039369638803685072626967951165243647931265, 54772208597990407430395018479557528859948250022718336556935666676225482342335045521290671839328385, 967037403232220731074074563038316755517610240570658812669537184604036430235566311331012838883641380865, 158187160409249161202798539163939228646964656295329913967778296913812576561852899807747016936421334492545, 3717244910717158061241869794170130224455174443632345624307057397938775397436321031917968743482485623000552386373033202447105, 37839385943068863406967633413004957540054532539686888463944906014566240419460804270776358938980032660929917901837033235462145]
#var arr = [64075459460541239985, 14370921672011352376545, 537329970884826078063105, 5981802520294676451270038145, 141934960805533535384100259905, 2609668563371076823446624111609234945, 1667290021770201095403065629700606750145, 125365126527183302043148011968823435306857985, 871005264581548962932418919531990803260747265, 78608978003846049041116965738897583982829325185, 8321395327031499581392144057169057667676851380865, 74875990602425226938138664024259158432269224416705, 1018329989576989704159754753835889677652405111555820545, 147722431492705339415781997425542771343697631011575451905, 10283584008448773696475907793170493467187054108119687416065, 12234418303749373766457825700620527121617068058319432387585, 165502573617193579886078524884554371013787876466850820614145, 14701083488299057530174696885922722686956286485260401577115414785, 321030150905393790929751720043602006651739765349595158023943724894346115208705]
#var arr = [192463418472849397730107809253922101, 1347320741392600160214289343906212762456021, 70865138168006643427403953978871929070133095474701, 3363391752747838578311772729701478698952546288306688208857, 132153369641266990823936945628293401491197666138621036175881960329, 9105096650335639994239038954861714246150666715328403635257215036295306537]
#var arr = [34015651529746754841597629769101132590516759547941]
#var arr = [341]
var arr = [1]
#var arr = [24301222105, 34200607741, 194305088689, 7362505969365, 19702357790989, 2985533798982149, 6091629437910701, 24781034010920641, 98129837465651129, 99860491537987361, 105697961209955269, 154533752639483489, 406611602100644641, 714567498159333701]
#var arr = [6147353521, 18441949681, 24155301361, 2945030568769, 22415236323481, 6328140564467401, 45669044917576081, 111893049583818721, 3164607919507114081, 129717501475261645009, 716074318521330199201]
#var arr = [3277, 3281, 121463, 491209, 11530801, 512330281, 15656266201, 139309114031, 7947339136801, 72054898434289, 334152420730129, 17676352761153241, 172138573277896681, 4398575137518327194521]
#var arr = [3465253618401, 44202753561285411, 1640293473202755801, 10623546148468360251]
#var arr = [687979968481, 1928376089641, 2638625591701, 3148470889201, 3152088903601, 14682521533681, 19656816822721, 37333372057201, 47003559452641, 80643055074121, 129235662445121, 140940741166849, 196945133626801, 336301807660741, 345186571310209, 439931062854361, 490464498901105, 531259716925081]
#var arr = [27453375098872012081, 1553120766503217777601, 2316867089206526090641, 5745765587660958183661, 170845977240460180827001, 211376155831990085740609, 9920799542911938327843841, 375623792044867850082496129, 15853017707070075884775600001]
var seen = Set(arr...)
for v in (arr) {
#for v in (t.divisors.grep{_ > 2**64}) {
for k in (3..1e4) {
is_coprime(k, v) || next
with (v*k) {|z|
if (is_pseudoprime(z) && is_composite(z) && !seen.contains(z)) {
say z if (z > 2**64)
arr << z
seen << z
}
}
}
#}
}