-
Notifications
You must be signed in to change notification settings - Fork 0
/
generate_pseudoprimes_from_factors.pl
executable file
·116 lines (81 loc) · 2.54 KB
/
generate_pseudoprimes_from_factors.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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#!/usr/bin/perl
# Generate pseudoprimes using the prime factors of other pseudoprimes.
use 5.020;
use strict;
use warnings;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);
eval { require GDBM_File };
my $cache_db = "cache/factors.db";
dbmopen(my %db, $cache_db, 0444)
or die "Can't create/access database <<$cache_db>>: $!";
warn ":: Sieving primes...\n";
my @list;
my %seen;
while (my ($key, $value) = each %db) {
my @factors = split(' ', $value);
push @list, grep { !$seen{$_}++ } grep {
#length($_) < 30
($_ > 1e8) and ($_ < 1e15)
#and modint($_, 8) == 3
#and modint($_, 8) == 1
and kronecker(5, $_) == -1
#and is_square_free(subint($_, 1) >> 1)
#and is_square_free(addint($_, 1) >> 2)
#and (vecall { modint($_, 4) == 1 } factor(subint($_, 1) >> 1))
#and (vecall { modint($_, 4) == 3 } factor(addint($_, 1) >> 2))
} @factors;
last if (@list > 2e6);
}
dbmclose(%db);
warn ":: Found ", scalar(@list), " primes...\n";
warn ":: Generating fibonacci pseudoprimes...\n";
sub fibonacci_pseudoprimes ($list, $callback) {
my %common_divisors;
foreach my $p (@$list) {
my $k = kronecker(5, $p);
#if ($k == -1) {
if (1) {
foreach my $d (divisors(subint($p, $k))) {
if (lucasumod(1, -1, $d, $p) == 0) {
push @{$common_divisors{$d}}, $p;
}
#if (($k == 1) ? (powmod(5, $d, $p) == 1) : (powmod(5, $d, $p) == $d-1)) {
# push @{$common_divisors{$d}}, $p;
#}
}
}
}
foreach my $arr (values %common_divisors) {
my $l = $#{$arr} + 1;
for (my $k = 3 ; $k <= $l ; $k += 2) {
forcomb {
my $n = Math::Prime::Util::GMP::vecprod(@{$arr}[@_]);
$callback->($n);
}
$l, $k;
}
}
}
sub is_fibonacci_pseudoprime ($n) {
Math::Prime::Util::GMP::lucasumod(1, -1, $n, $n) eq Math::Prime::Util::GMP::subint($n, 1);
}
fibonacci_pseudoprimes(
\@list,
sub ($n) {
if (is_fibonacci_pseudoprime($n)) {
say $n;
warn "Fib: $n\n";
if (is_euler_pseudoprime($n, 5)) {
die "Found counter-example: $n";
}
if (kronecker(5, $n) == -1) {
if (is_pseudoprime($n, 2)) {
die "Found a special pseudoprime: $n";
}
}
}
}
);