1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- #!/usr/bin/perl
- # Extract primes from Carmichael numbers that satisfy Pomerance's conditions for being a factor a PSW pseudoprime.
- use 5.020;
- use strict;
- use warnings;
- use Storable;
- use ntheory qw(:all);
- use Math::Prime::Util::GMP;
- use experimental qw(signatures);
- #my $storable_file = "cache/factors-carmichael.storable";
- my $storable_file = "cache/factors-lucas-carmichael.storable";
- my $carmichael = retrieve($storable_file);
- my $B = 100_000; # smooth value
- my %seen;
- while (my ($n, $value) = each %$carmichael) {
- foreach my $p (split(' ', $value)) {
- length($p) < 100 or next;
- modint($p, 8) == 3 or next;
- kronecker(5, $p) == -1 or next;
- next if exists $seen{$p};
- undef $seen{$p};
- # Conditions for p +/- 1
- my $pp1 = addint($p, 1);
- my $pm1 = subint($p, 1);
- modint($pp1, 4) == 0 or next;
- modint($pp1, 8) != 0 or next;
- modint($pm1, 4) != 0 or next;
- my $pm1d2 = divint($pm1, 2);
- my $pp1d4 = divint($pp1, 4);
- modint($pm1d2, 4) == 1 or next;
- is_smooth($pp1d4, $B) or next;
- is_smooth($pm1d2, $B) or next;
- #is_square_free($pp1d4) or next;
- #is_square_free($pm1d2) or next;
- next if not vecall { modint($_, 4) == 3 } factor($pp1d4);
- next if not vecall { modint($_, 4) == 1 } factor($pm1d2);
- say $p;
- }
- }
|