12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 |
- #!/usr/bin/perl
- use 5.020;
- use autodie;
- use warnings;
- use Math::GMPz;
- use Storable;
- use ntheory qw(:all);
- use experimental qw(signatures);
- use List::Util qw(uniq);
- use Math::Prime::Util::GMP;
- eval { require GDBM_File };
- my $cache_db = "factors.db";
- my $storable_file = "factors-carmichael.storable";
- dbmopen(my %cache_db, $cache_db, 0444)
- or die "Can't create/access database <<$cache_db>>: $!";
- sub my_is_carmichael ($n, $factors) {
- my $nm1 = Math::GMPz->new($n) - 1;
- return if not vecall { Math::GMPz::Rmpz_divisible_p($nm1, Math::GMPz->new($_) - 1) } @$factors;
- scalar(uniq(@$factors)) == scalar(@$factors);
- }
- sub my_is_carmichael_fast ($n, $factors) {
- my $nm1 = Math::Prime::Util::GMP::subint($n, 1);
- return if not vecall {
- Math::Prime::Util::GMP::modint($nm1, ($_ < ~0) ? ($_ - 1) : Math::Prime::Util::GMP::subint($_, 1)) eq '0'
- } @$factors;
- scalar(uniq(@$factors)) == scalar(@$factors);
- }
- {
- my $nm1 = Math::GMPz::Rmpz_init();
- my $pm1 = Math::GMPz::Rmpz_init();
- sub my_is_carmichael_faster ($n, $factors) {
- Math::GMPz::Rmpz_set_str($nm1, $n, 10);
- Math::GMPz::Rmpz_sub_ui($nm1, $nm1, 1);
- return if not vecall {
- ($_ < ~0) ? Math::GMPz::Rmpz_divisible_ui_p($nm1, $_ - 1) : do {
- Math::GMPz::Rmpz_set_str($pm1, $_, 10);
- Math::GMPz::Rmpz_sub_ui($pm1, $pm1, 1);
- Math::GMPz::Rmpz_divisible_p($nm1, $pm1);
- }
- } @$factors;
- scalar(uniq(@$factors)) == scalar(@$factors);
- }
- }
- my $table = {};
- if (-e $storable_file) {
- say "# Loading data...";
- $table = retrieve($storable_file);
- }
- say "# Checking database...";
- while (my ($key, $value) = each %cache_db) {
- next if exists $table->{$key};
- #~ Math::Prime::Util::GMP::is_pseudoprime($key,2) || next;
- my @factors = split(' ', $value);
- if (scalar(@factors) >= 3 and my_is_carmichael_faster($key, \@factors)) {
- $table->{$key} = $value;
- }
- }
- say "# Storing data...";
- store($table, $storable_file);
- dbmclose(%cache_db);
|