This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.27
in repository libmath-prime-util-perl.

commit 738a95316119849b6187465320e6c907b84a1004
Author: Dana Jacobsen <d...@acm.org>
Date:   Fri May 17 12:30:20 2013 -0700

    More verbose/error output consistency for verify_prime.  Tests.
---
 Makefile.PL             |   1 +
 lib/Math/Prime/Util.pm  |  40 +++++++++-------
 t/23-primality-proofs.t | 125 +++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 142 insertions(+), 24 deletions(-)

diff --git a/Makefile.PL b/Makefile.PL
index 02ee4b1..c4251a6 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -20,6 +20,7 @@ WriteMakefile1(
 
     BUILD_REQUIRES=>{
                       'Test::More'       => '0.45',
+                      'Test::Warn'       => 0,
                       'bignum'           => '0.22',   # 'use bigint' in tests
                     },
     PREREQ_PM    => {
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index ce2c220..91802b5 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -1745,7 +1745,7 @@ sub verify_prime {
   if ($method eq 'Pratt' || $method eq 'Lucas') {
     # Based on Lucas primality test, which requires full n-1 factorization.
     if (scalar @pdata != 2 || (ref($pdata[0]) ne 'ARRAY') || (ref($pdata[1]) 
eq 'ARRAY')) {
-      print "verify_prime: incorrect Pratt format, must have factors and a 
value\n" if $verbose;
+      carp "verify_prime: incorrect Pratt format, must have factors and a 
value\n";
       return 0;
     }
     my @factors = @{shift @pdata};
@@ -1776,7 +1776,7 @@ sub verify_prime {
       $factors_seen{"$f"} = 1;
     }
     if ($B != 1) {
-      print "verify_prime: n-1 not completely factored" if $verbose;
+      print "primality fail: n-1 not completely factored" if $verbose;
       return 0;
     }
 
@@ -1804,7 +1804,7 @@ sub verify_prime {
   if ($method eq 'n-1') {
     # BLS75 or generalized Pocklington
     # 
http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
-    # Pull of optional theorem 7 data
+    # Pull off optional theorem 7 data
     my ($theorem, $t7_B1, $t7_B, $t7_a) = (5, undef, undef, undef);
     if (scalar @pdata == 3 && ref($pdata[0]) eq 'ARRAY' && $pdata[0]->[0] =~ 
/^(B|T7|Theorem\s*7)$/i) {
       $theorem = 7;
@@ -1812,13 +1812,13 @@ sub verify_prime {
       $t7_B  = Math::BigInt->new("$t7_B");
     }
     if (scalar @pdata != 2 || (ref($pdata[0]) ne 'ARRAY') || (ref($pdata[1]) 
ne 'ARRAY')) {
-      warn "verify_prime: incorrect n-1 format, must have factors and a 
values\n";
+      carp "verify_prime: incorrect n-1 format, must have factors and a 
values\n";
       return 0;
     }
     my @factors = @{shift @pdata};
     my @as = @{shift @pdata};
     if ($#factors != $#as) {
-      warn "verify_prime: incorrect n-1 format, must have a value for each 
factor\n";
+      carp "verify_prime: incorrect n-1 format, must have a value for each 
factor\n";
       return 0;
     }
 
@@ -1940,24 +1940,24 @@ sub verify_prime {
     #      Ux,Uy should be 600992528322000913770, 206075883056439332684
     #      Vx,Vy should be 0, 1
     if (scalar @pdata < 1) {
-      warn "verify_prime: incorrect AGKM format\n";
+      carp "verify_prime: incorrect AGKM format\n";
       return 0;
     }
     my ($ni, $a, $b, $m, $P);
     my ($qval, $q) = ($n, $n);
     foreach my $block (@pdata) {
       if (ref($block) ne 'ARRAY' || scalar @$block != 6) {
-        warn "verify_prime: incorrect AGKM block format\n";
+        carp "verify_prime: incorrect AGKM block format\n";
         return 0;
       }
       if (Math::BigInt->new("$block->[0]") != Math::BigInt->new("$q")) {
-        warn "verify_prime: incorrect AGKM block format: block n != q\n";
+        carp "verify_prime: incorrect AGKM block format: block n != q\n";
         return 0;
       }
       ($ni, $a, $b, $m, $qval, $P) = @$block;
       $q = ref($qval) eq 'ARRAY' ? $qval->[0] : $qval;
       if (ref($P) ne 'ARRAY' || scalar @$P != 2) {
-        warn "verify_prime: incorrect AGKM block point format\n";
+        carp "verify_prime: incorrect AGKM block point format\n";
         return 0;
       }
       my($Px, $Py) = @$P;
@@ -1969,16 +1969,16 @@ sub verify_prime {
       $Px = $n->copy->bzero->badd("$Px") unless ref($Px) eq 'Math::BigInt';
       $Py = $n->copy->bzero->badd("$Py") unless ref($Py) eq 'Math::BigInt';
       if (Math::BigInt::bgcd($ni, 6) != 1) {
-        warn "verify_prime: AGKM block n '$ni' is divisible by 2 or 3\n";
+        print "primality fail: AGKM block n '$ni' is divisible by 2 or 3\n" if 
$verbose;
         return 0;
       }
       my $c = $a*$a*$a * 4 + $b*$b * 27;
       if (Math::BigInt::bgcd($c, $ni) != 1) {
-        warn "verify_prime: AGKM block gcd 4a^3+27b^2,n incorrect\n";
+        print "primality fail: AGKM block gcd 4a^3+27b^2,n incorrect\n" if 
$verbose;
         return 0;
       }
       if ($q <= $ni->copy->broot(4)->badd(1)->bpow(2)) {
-        warn "verify_prime: AGKM block q is too small\n";
+        print "primality fail: AGKM block q is too small\n" if $verbose;
         return 0;
       }
       # Final check, check that we've got a bound above and below (Hasse)
@@ -1990,13 +1990,13 @@ sub verify_prime {
       # Compute U = (m/q)P, check U != point at infinity
       $ECP->mul( $m->copy->bdiv($q)->as_int );
       if ($ECP->is_infinity) {
-        warn "verify_prime: AGKM point does not multiply correctly.\n";
+        print "primality fail: AGKM point does not multiply correctly (1).\n" 
if $verbose;
         return 0;
       }
       # Compute V = qU, check V = point at infinity
       $ECP->mul( $q );
       if (! $ECP->is_infinity) {
-        print "verify_prime: AGKM point does not multiply correctly.\n" if 
$verbose;
+        print "primality fail: AGKM point does not multiply correctly (2).\n" 
if $verbose;
         return 0;
       }
     }
@@ -2007,7 +2007,7 @@ sub verify_prime {
     return 1;
   }
 
-  print "verify_prime: Unknown method: '$method'.\n" if $verbose;
+  carp "verify_prime: Unknown method: '$method'.\n";
   return 0;
 }
 
@@ -2894,8 +2894,14 @@ array reference if the result is not 2 (definitely 
prime).
 
 Given an array representing a certificate of primality, returns either 0 (not
 verified), or 1 (verified).  The computations are all done using pure Perl
-Math::BigInt and should not be time consuming (the Pari or GMP backends will
-help with large inputs).
+Math::BigInt.  Lucas/Pratt and n-1 proofs are not time consuming, but ECPP
+proofs can be rather slow, especially without the GMP or Pari backends.
+
+If the certificate is malformed, the routine will carp a warning in addition
+to returning 0.  If the C<verbose> option is set (see L</prime_set_config>)
+then if the validation fails, the reason for the failure is printed in
+addition to returning 0.  If the C<verbose> option is set to 2 or higher, then
+a message indicating success and the certificate type is also printed.
 
 A certificate is an array holding an C<n-cert>.  An C<n-cert> is one of:
 
diff --git a/t/23-primality-proofs.t b/t/23-primality-proofs.t
index 470039c..d525fbe 100644
--- a/t/23-primality-proofs.t
+++ b/t/23-primality-proofs.t
@@ -3,6 +3,7 @@ use strict;
 use warnings;
 
 use Test::More;
+use Test::Warn;
 use Math::Prime::Util qw/is_prime is_provable_prime is_provable_prime_with_cert
                          prime_certificate verify_prime
                          prime_get_config
@@ -30,10 +31,14 @@ my @plist = qw/20907001 809120722675364249 
677826928624294778921
          @plist;
 
 plan tests => 0
-            + 2 # is_provable_prime
+            + 2  # is_provable_prime
             + 6 * scalar(@plist)
-            + 6 # hand-done proofs
-            + 17 # verification failures
+            + 6  # hand-done proofs
+            + 28 # borked up certificates generating warnings
+            + 6  # verification failures (tiny/BPSW)
+            + 8  # verification failures (Lucas/Pratt)
+            + 12 # verification failures (n-1)
+            + 7  # verification failures (ECPP)
             + 0;
 
 is( is_provable_prime(871139809), 0, "871139809 is composite" );
@@ -107,16 +112,79 @@ SKIP: {
 }
 
 # Failures for verify_prime
+
+# First, let's get the borked up formats, which is should warn about.
+{
+  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, 'INVALID', 1, 2, 3]), 0, "unknown method" );
-is( verify_prime([1490266103, 'Pratt', 1, 2, 3]), 0, "Pratt with wrong count" 
);
-is( verify_prime([1490266103, 'Pratt', 1, [2]]), 0, "Pratt with non-array 
arguments" );
-is( verify_prime([1490266103, 'Pratt', [1], [2]]), 0, "Pratt with non-array 
arguments" );
+
+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" );
@@ -124,3 +192,46 @@ is( verify_prime([1490266103, 'Pratt', [2,13,19,1597], 
5]), 0, "Pratt with not e
 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" );

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits

Reply via email to