/
strong_miller_rabin_pseudoprimes_cached.pl
executable file
·83 lines (63 loc) · 5.48 KB
/
strong_miller_rabin_pseudoprimes_cached.pl
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#!/usr/bin/perl
# Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness.
# https://oeis.org/A014233
# Version with terms > 2^64.
# Interesting Carmichael number that is also strong psp to the first 7 prime bases:
# 129713907272647698631
use 5.020;
use strict;
use warnings;
use Storable;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);
my $fermat_file = "cache/factors-fermat.storable";
my $fermat = retrieve($fermat_file);
my @terms;
while (my ($n) = each %$fermat) {
next if length($n) > 100;
if (is_strong_pseudoprime($n, 2)) {
push @terms, Math::GMPz->new($n);
}
}
@terms = sort { $a <=> $b } @terms;
my $p = 2;
my @bases = ($p);
foreach my $n (@terms) {
if (is_strong_pseudoprime($n, @bases)) {
say "a(", scalar(@bases), ") <= $n";
$p = next_prime($p);
unshift @bases, $p;
while (is_strong_pseudoprime($n, $p)) {
say "a(", scalar(@bases), ") <= $n";
$p = next_prime($p);
unshift @bases, $p;
}
}
}
__END__
# Upper-bounds less than 100 digits:
a(1) <= 2047
a(2) <= 5173601
a(3) <= 11734055449745947
a(4) <= 534049563499447969
a(5) <= 8614572538322761627
a(6) <= 8614572538322761627
a(7) <= 41234316135705689041
a(8) <= 41234316135705689041
a(9) <= 41234316135705689041
a(10) <= 318665857834031151167461
a(11) <= 318665857834031151167461
a(12) <= 318665857834031151167461
a(13) <= 3317044064679887385961981
a(14) <= 6003094289670105800312596501
a(15) <= 59276361075595573263446330101
a(16) <= 564132928021909221014087501701
a(17) <= 564132928021909221014087501701
a(18) <= 1543267864443420616877677640751301
a(19) <= 1543267864443420616877677640751301
# Some larger upper-bounds:
a( 20) .. a( 46) <= 105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043
a( 47) .. a(168) <= 6941543021392713730431668387068999032987505813628626223678951265009922979171494889619620919629218172938050022712650390231108995307237169269667644098333312684776469399924110119789527532161256933656112818109620945798457804143586629828296071826627003328849527952336389650813108369731049080747183836913592892951933560765345204468790419691959105305515726737868378312872715843312320064073674571001295106119373097331445689095722655847864191050899780290639922180983329597857624757187701943317347314318342630851888782724340309365489828447876503970224596096163190175586664838655752084811432643865453475409306234610422754846201955355349982116992680801631254169733179214516679698471486732095757632702985749004267668618407596194879010235811205069773345370151540294560707067912911972617117872568917574563797510424723636252899372760040898527772334935423922327351299656281932266256675132502702322760435460536571309302586539469310861406622510368133332971804029286468542260235396204271045794929827474636467550655521103657096119618759746982193439030809406498947869770588717242290031299573971411197982166717351757954266001066384132372994264058429334563291496657469558139808375030168417007373133166391119553220773091860698215980720042621281779381114805103592526045494482900527480395872621990534353634675251867
a(169) .. a(256) <= 106345207806296484231668043910066785399795652556314098984703724996175611913155370425059004666755351126370765757325069220154090475525113111331534155822504132427954121926028977897326016452032633264303162177531381326310998970713694521304856783427108211035837719173191888424497687716945903847840832601158220338315116311569353516661115745397618364437941836386218808101529448483687495168944238726821330736995943973596941803495501200742109710969089802656966120128959989924056907838239415947883597253487288911265130861076995785143322559232949628580082040985968381890859811544811963250166807225739883175758540592938038640525057077635260377283817570121188506720763322577723854603213904763949026451035886610117960695498777558294914095190286423434103595325322044355050505888390419892966130432853384420025991603809604285550077998959033403957562518661694503445321270371924756278334786001733438835926798599715925477942244937628383988529536076933049398733022131632892984494328799535905089231306547424707999668050846457897292105617153237859066140231207977706483096753560267776977308513770417672719215980272226316038096369457350381579229798547106736019854318870385754141371733858517502044218801634760265587498814280073328060552232702804872921969797735332629722017664747892121030708748712733180842486503682755515481434761547891191431690407378061063299887695616928512486921716155822944378708863947668462062195571745339003058779915940858554595239390172360173769656161537253021381577803596097455028941144286297184282046724577533468348343936096263977229393852616124982192888432604948830175933041671162863393593616389115022094081675889914163162852300506873558662214056728175728839204797446701664449699367321558065141345504373533192399722226922311408612622529245371708935701643178960931071329253928802738471610262504489056899252740549408250528391001108587552456472577625704595893048563596869581967781113019047808212452621728173827862405874506295664794063113108306419852891590636875366731732762664553725634243782507523770949879136684328870372364698244368287699980886402179469945231457642085062803806579094674257318340352731256782194724089323