#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;
use Math::Prime::Util qw/is_prime is_provable_prime is_provable_prime_with_cert
prime_certificate verify_prime
prime_get_config prime_set_config
/;
my $use_test_warn;
BEGIN {
eval "use Test::Warn";
$use_test_warn = $@ ? 0 : 1;
}
my $extra = 0+(defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING});
my $use64 = ~0 > 4294967295;
my $broken64 = (18446744073709550592 == ~0);
# Do some tests only if:
# EXTENDED_TESTING is on OR we have the GMP backend
# Note that with Calc, these things are incredibly slow.
use Math::BigInt try=>"GMP,Pari";
my $doexpensive = 0 + ($extra || ( (!$use64 || !$broken64) && Math::BigInt->config()->{lib} eq 'Math::BigInt::GMP' ));
my @plist = qw/20907001 809120722675364249/;
if ($extra || $use64) {
push @plist, "677826928624294778921";
}
if ($extra || prime_get_config->{'gmp'}) {
push @plist, "980098182126316404630169387";
}
## This is too slow without Math::Prime::Util::GMP.
#push @plist, '3364125245431456304736426076174232972735419017865223025179282077503701'
# if prime_get_config->{'gmp'};
#
#push @plist, '6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151'
# if $extra
# && (prime_get_config->{'gmp'} || Math::BigInt->config()->{lib} eq 'Math::BigInt::GMP');
#
#push @plist, '531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127'
# if $extra && prime_get_config->{'gmp'};
plan tests => 0
+ 2 # is_provable_prime
+ 6 * scalar(@plist)
# hand-done proofs
+ 1*$doexpensive # n-1 for 2^521-1
+ 1*$extra # n-1 for 2^607-1
#+ (($doexpensive && !$broken64) ? 1 : 0) # n-1 proof
+ (($doexpensive) ? 1 : 0) # n-1 proof
+ 2 # Pratt and ECPP
+ 28 # borked up certificates generate warnings
+ 6 # verification failures (tiny/BPSW)
+ 8 # verification failures (Lucas/Pratt)
+ 8 # verification failures (n-1)
+ 7 # verification failures (ECPP)
+ 3 # Verious other types
+ 0;
is( is_provable_prime(871139809), 0, "871139809 is composite" );
is( is_provable_prime(1490266103), 2, "1490266103 is provably prime" );
foreach my $p (@plist) {
SKIP: {
skip "Broken 64-bit causes trial factor to barf", 6
if $broken64 && $p > 2**60;
ok( is_prime($p), "$p is prime" );
my($isp, $cert) = is_provable_prime_with_cert($p);
is( $isp, 2, " is_provable_prime_with_cert returns 2" );
ok( defined($cert) && $cert =~ /^Type/m,
" certificate is non-null" );
prime_set_config(verbose=>1);
ok( verify_prime($cert), " verification of certificate for $p done" );
prime_set_config(verbose=>0);
# Note, in some cases the certs could be non-equal (but both must be valid!)
my $cert2 = prime_certificate($p);
ok( defined($cert2) && $cert2 =~ /^Type/m,
" prime_certificate is also non-null" );
if ($cert2 eq $cert) {
ok(1, " certificate is identical to first");
} else {
ok( verify_prime($cert2), " different cert, verified" );
}
}
}
# Some hand-done proofs
if ($doexpensive) {
my $proof = <<EOPROOF;
[MPU - Primality Certificate]
Version 1.0
Proof for:
N 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
Type BLS5
N 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
Q[1] 65427463921
Q[2] 308761441
Q[3] 7623851
Q[4] 409891
Q[5] 61681
Q[6] 1613
Q[7] 521
Q[8] 157
Q[9] 131
Q[10] 53
Q[11] 41
Q[12] 31
Q[13] 17
A[0] 3
A[1] 3
A[2] 3
A[3] 3
A[4] 3
A[5] 3
A[6] 3
A[8] 3
A[9] 3
A[10] 3
A[11] 3
A[12] 3
A[13] 3
----
EOPROOF
ok( verify_prime($proof), "2**521-1 primality proof verified" );
}
if ($extra) {
my $proof = <<EOPROOF;
[MPU - Primality Certificate]
Version 1.0
Proof for:
N 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
Type BLS5
N 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
Q[1] 845100400152152934331135470251
Q[2] 341117531003194129
Q[3] 7432339208719
Q[4] 607
A[0] 3
A[1] 3
A[2] 3
A[3] 3
----
Type BLS5
N 845100400152152934331135470251
Q[1] 1801
Q[2] 601
Q[3] 251
Q[4] 101
A[1] 3
A[2] 3
A[3] 3
----
EOPROOF
ok( verify_prime($proof), "2**607-1 primality proof verified" );
}
if ($doexpensive) {
my @proof = ('3364125245431456304736426076174232972735419017865223025179282077503701', 'n-1',
[2,5,127, ['28432789963853652887491983185920687231739655787', 'n-1',
[ 2,3,163,650933, [ '44662634059309451871488121651101494489', 'n-1',
[ 2,3,23,4021,2321273 ],
[ 11, 2, 2, 2, 2 ]
] ],
[ 2, 2, 2, 2, 2 ]
],
'9316417838190714313' ],
[ 2, 2, 2, 2, 2 ]);
ok( verify_prime(@proof), "simple n-1 proof verified" );
}
{
my @proof = (20907001, "Pratt", [ 2,
3,
5,
[23,"Pratt",[2,[11,"Pratt",[2,5],2]],5],
[101, "Pratt", [2, 5], 2],
], 14 );
ok( verify_prime(@proof), "simple Lucas/Pratt proof verified" );
}
{
my $proof = <<EOPROOF;
[MPU - Primality Certificate]
Version 1.0
Proof for:
N 1030291136596639351761062717
Type ECPP
N 1030291136596639351761062717
A 1030291136596639351761062709
B 0
M 1030291136596575744618987466
Q 317851433704525489
X 4215121326
Y 246323849244309081587435955
EOPROOF
ok( verify_prime($proof), "ECPP primality proof of 1030291136596639351761062717 verified" );
}
#{
# my @proof = ('809120722675364249', "n-1", ["B", 20000, '22233477760919', 2], [2, 4549], [3, 2]);
# ok( verify_prime(@proof), "n-1 T7 primality proof of 809120722675364249 verified" );
#}
# Failures for verify_prime
# First, let's get the borked up formats, which is should warn about.
SKIP: {
skip "No Test::Warn", 28 unless $use_test_warn;
my $result;
warning_like { $result = verify_prime([1490266103, 'INVALID', 1, 2, 3]) }
{ carped => qr/^verify_prime: / },
"warning for unknown method";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'Pratt', 1, 2, 3]) }
{ carped => qr/^verify_prime: / },
"warning for invalid Lucas/Pratt";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'Pratt', 1, [2], 3]) }
{ carped => qr/^verify_prime: / },
"warning for invalid Lucas/Pratt";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'Pratt', [1], 2, 3]) }
{ carped => qr/^verify_prime: / },
"warning for invalid Lucas/Pratt";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'n-1', 1, 2, 3]) }
{ carped => qr/^verify_prime: / },
"warning for invalid n-1 (too many arguments)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'n-1', 1, 2]) }
{ carped => qr/^verify_prime: / },
"warning for invalid n-1 (non-array f,a)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'n-1', [1], 2]) }
{ carped => qr/^verify_prime: / },
"warning for invalid n-1 (non-array a)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'n-1', [2, 13, 19, 1597, 1889], [2, 2, 2, 2]]) }
{ carped => qr/^verify_prime: / },
"warning for invalid n-1 (too few a values)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP']) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (no n-certs)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP', 15]) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (non-array block)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP', [15,16,17]]) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (wrong size block)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP', [694361, 694358, 0, 695162, 26737, [348008, 638945]]]) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (block n != q)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP', [1490266103, 1442956066, 1025050760, 1490277784, 2780369, 531078754]]) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (block point wrong format)";
is( $result, 0, " ...and returns 0" );
warning_like { $result = verify_prime([1490266103, 'ECPP', [1490266103, 1442956066, 1025050760, 1490277784, 2780369, [531078754, 0, 195830554]]]) }
{ carped => qr/^verify_prime: / },
"warning for invalid ECPP (block point wrong format)";
is( $result, 0, " ...and returns 0" );
}
is( verify_prime([]), 0, "verify null is composite" );
is( verify_prime([2]), 1, "verify [2] is prime" );
is( verify_prime([9]), 0, "verify [9] is composite" );
is( verify_prime([14]), 0, "verify [14] is composite" );
is( verify_prime(['28446744073709551615']), 0, "verify BPSW with n > 2^64 fails" );
is( verify_prime([871139809]), 0, "verify BPSW with composite fails" );
is( verify_prime([1490266103, 'Pratt', [2,13,19,1597,1889], 5]), 1, "Lucas/Pratt proper" );
is( verify_prime([1490266103, 'Pratt', [4,13,19,1597,1889], 5]), 0, "Pratt with non-prime factors" );
is( verify_prime([1490266103, 'Pratt', [[4],13,19,1597,1889], 5]), 0, "Pratt with non-prime factors" );
is( verify_prime([1490266103, 'Pratt', [2,13,29,1597,1889], 5]), 0, "Pratt with wrong factors" );
is( verify_prime([1490266103, 'Pratt', [2,13,19,1597], 5]), 0, "Pratt with not enough factors" );
is( verify_prime([1490266103, 'Pratt', [2,13,19,1597,1889], 1490266103]), 0, "Pratt with coprime a" );
is( verify_prime([185156263, 'Pratt', [2,3,3,10286459], 2]), 0, "Pratt with non-psp a" );
is( verify_prime([1490266103, 'Pratt', [2,13,19,1597,1889], 3]), 0, "Pratt with a not valid for all f" );
is( verify_prime([1490266103, 'n-1', [2, 13, 19, 1597, 1889], [5, 2, 2, 2, 2]]), 1, "n-1 proper" );
is( verify_prime([1490266103, 'n-1', [2, 23, 19, 1597, 1889], [5, 2, 2, 2, 2]]), 0, "n-1 with wrong factors" );
is( verify_prime([1490266103, 'n-1', [13, 19, 1597, 1889], [2, 2, 2, 2]]), 0, "n-1 without 2 as a factor" );
is( verify_prime([1490266103, 'n-1', [2, 13, 1889, 30343], [5, 2, 2, 2]]), 0, "n-1 with a non-prime factor" );
is( verify_prime([1490266103, 'n-1', [2, 13, 1889, [30343]], [5, 2, 2, 2]]), 0, "n-1 with a non-prime array factor" );
# I don't know how to make F and R (A and B) to not be coprime
#is( verify_prime(['9848131514359', 'n-1', ["B", 20000, 890588851, 2], [2, 3, 19, 97], [3, 5, 2, 2]]), 1, "n-1 T7 proper" );
#is( verify_prime(['9848131514359', 'n-1', ["B", 20000, 890588951, 2], [2, 3, 19, 97], [3, 5, 2, 2]]), 0, "n-1 T7 with misfactor" );
#is( verify_prime(['9848131514359', 'n-1', ["B", 0, 890588851, 2], [2, 3, 19, 97], [3, 5, 2, 2]]), 0, "n-1 T7 with B < 1" );
#is( verify_prime(['9848131514359', 'n-1', ["B", 20000, 16921188169, 2], [2, 3, 97], [3, 5, 2]]), 0, "n-1 T7 with wrong B" );
is( verify_prime([1490266103, 'n-1', [2, 13], [5, 2]]), 0, "n-1 without enough factors" );
is( verify_prime([914144252447488195, 'n-1', [2, 3, 11, 17, 1531], [2, 2, 2, 2, 2]]), 0, "n-1 with bad BLS75 r/s" );
is( verify_prime([1490266103, 'n-1', [2, 13, 19, 1597, 1889], [3, 2, 2, 2, 2]]), 0, "n-1 with bad a value" );
is( verify_prime([1490266103, "ECPP",
[1490266103, 1442956066, 1025050760, 1490277784, 2780369, [531078754, 195830554]],
[2780369, 2780360, 0, 2777444, 694361, [2481811, 1317449]],
[694361, 694358, 0, 695162, 26737, [348008, 638945]]]),
1, "ECPP proper" );
is( verify_prime([1490266103, "ECPP",
[1490266103, 1442956066, 1025050760, 1490277784, 5560738, [531078754, 195830554]],
[5560738, 2780360, 0, 2777444, 694361, [2481811, 1317449]]]),
0, "ECPP q is divisible by 2" );
is( verify_prime([74468183, "ECPP",
[74468183, 89, 1629, 74475075, 993001, [47943960, 8832604]],
[993001, 0, 992984, 994825, 3061, [407531, 231114]]]),
0, "ECPP a/b invalid" );
is( verify_prime([1490266103, "ECPP",
[1490266103, 1442956066, 1025050760, 1490277784, 536, [531078754, 195830554]],
[536, 2780360, 0, 2777444, 694361, [2481811, 1317449]]]),
0, "ECPP q is too small" );
is( verify_prime([694361, "ECPP",
[694361, 694358, 0, 30, 26737, [264399, 59977]]]),
0, "ECPP multiplication wrong (infinity)" );
is( verify_prime([694361, "ECPP",
[694361, 694358, 0, 695161, 26737, [264399, 59977]]]),
0, "ECPP multiplication wrong (not infinity)" );
is( verify_prime([1490266103, "ECPP",
[1490266103, 1442956066, 1025050760, 1490277784, 2780369, [531078754, 195830554]],
[2780369, 2780360, 0, 2777444, 694361, [2481811, 1317449]],
[694361, 694358, 0, 695162, [26737, "n-1", [2],[2]], [348008, 638945]]]),
0, "ECPP non-prime last q" );
{
my $header = "[MPU - Primality Certificate]\nVersion 1.0\nProof for:";
{
my $cert = join "\n", $header,
"N 2297612322987260054928384863",
"Type Pocklington",
"N 2297612322987260054928384863",
"Q 16501461106821092981",
"A 5";
is( verify_prime($cert), 1, "Verify Pocklington");
}
{
my $cert = join "\n", $header,
"N 5659942549665396263282978117",
"Type BLS15",
"N 5659942549665396263282978117",
"Q 42941814754495493",
"LP 2",
"LQ 3";
is( verify_prime($cert), 1, "Verify BLS15");
}
{
my $cert = join "\n", $header,
"N 43055019307158602560279",
"Type ECPP3",
"N 43055019307158602560279",
"S 106563369",
"R 404032076977387",
"A 0",
"B 4",
"T 1";
is( verify_prime($cert), 1, "Verify ECPP3");
}
}