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

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

commit 7bca5883d64ed00ff2656a397a3920e02408ed37
Author: Dana Jacobsen <d...@acm.org>
Date:   Tue Oct 29 20:52:51 2013 -0700

    Improve test coverage
---
 lib/Math/Prime/Util/PP.pm | 35 +++++++++++------------------------
 primality.c               |  5 -----
 t/16-randomprime.t        | 36 +++++++++++++++++++++++++++++++++---
 t/17-pseudoprime.t        | 16 ++++++++++++++++
 t/23-primality-proofs.t   | 34 ++++++++++++++++++++++++++++++++++
 t/32-iterators.t          | 26 ++++++++++++++++++++------
 t/80-pp.t                 | 40 ++++++++++++++++++++++++++++++++++------
 t/81-bignum.t             |  9 +++++++++
 8 files changed, 157 insertions(+), 44 deletions(-)

diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index f6de4a6..65ac6d6 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -733,11 +733,6 @@ sub _gcd_ui {
   $x;
 }
 
-sub _lcm_ui {
-  my($x, $y) = @_;
-  return (abs($x) / _gcd_ui($x, $y)) * abs($y);
-}
-
 sub _is_perfect_power {
   my $n = shift;
   return 0 if $n <= 3 || $n != int($n);
@@ -763,14 +758,6 @@ sub _order {
   return $lim+1;
 }
 
-# same result as:  int($n->blog(2)->floor->bstr)
-sub _log2 {
-  my $n = shift;
-  my $log2n = 0;
-  $log2n++ while ($n >>= 1);
-  $log2n;
-}
-
 
 
 sub is_pseudoprime {
@@ -1246,17 +1233,17 @@ sub _poly_new {
   return \@poly;
 }
 
-sub _poly_print {
-  my($poly) = @_;
-  carp "poly has null top degree" if $#$poly > 0 && !$poly->[-1];
-  foreach my $d (reverse 1 .. $#$poly) {
-    my $coef = $poly->[$d];
-    print "", ($coef != 1) ? $coef : "", ($d > 1) ? "x^$d" : "x", " + "
-      if $coef;
-  }
-  my $p0 = $poly->[0] || 0;
-  print "$p0\n";
-}
+#sub _poly_print {
+#  my($poly) = @_;
+#  carp "poly has null top degree" if $#$poly > 0 && !$poly->[-1];
+#  foreach my $d (reverse 1 .. $#$poly) {
+#    my $coef = $poly->[$d];
+#    print "", ($coef != 1) ? $coef : "", ($d > 1) ? "x^$d" : "x", " + "
+#      if $coef;
+#  }
+#  my $p0 = $poly->[0] || 0;
+#  print "$p0\n";
+#}
 
 sub _poly_mod_mul {
   my($px, $py, $r, $n) = @_;
diff --git a/primality.c b/primality.c
index 2711e3a..80f6252 100644
--- a/primality.c
+++ b/primality.c
@@ -11,11 +11,6 @@
 
 /* Primality related functions, including Montgomery math */
 
-/* TODO:
- *      - Convert F-U test to Montgomery
- *      - Convert Lucas tests to Montgomery
- */
-
 static const UV mr_bases_const2[1] = {2};
 
 /******************************************************************************
diff --git a/t/16-randomprime.t b/t/16-randomprime.t
index 0c577d2..7624c8a 100644
--- a/t/16-randomprime.t
+++ b/t/16-randomprime.t
@@ -7,8 +7,8 @@ use Test::More;
 #use Math::Random::MT::Auto qw/rand/;
 #sub rand { return 0.5; }
 use Math::Prime::Util qw/random_prime random_ndigit_prime random_nbit_prime
-                         random_maurer_prime is_prime
-                         prime_set_config/;
+                         random_maurer_prime random_proven_prime
+                         is_prime prime_set_config/;
 
 my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
 my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
@@ -64,7 +64,8 @@ plan tests => 13+3+3+3
               + (2 * scalar (keys %ranges))
               + (2 * scalar @random_to)
               + (1 * scalar @random_ndigit_tests)
-              + (2 * scalar @random_nbit_tests)
+              + (3 * scalar @random_nbit_tests)
+              + 3 + 4
               + 0;
 
 my $infinity = 20**20**20;
@@ -163,6 +164,7 @@ SKIP: {
 foreach my $bits ( @random_nbit_tests ) {
   check_bits( random_nbit_prime($bits), $bits, "nbit" );
   check_bits( random_maurer_prime($bits), $bits, "Maurer" );
+  check_bits( random_proven_prime($bits), $bits, "proven" );
 }
 
 sub check_bits {
@@ -173,3 +175,31 @@ sub check_bits {
   ok ( $n >= $min && $n <= $max && is_prime($n),
        "$bits-bit random $what prime is in range and prime");
 }
+prime_set_config(nobigint=>0);
+
+# Now check with custom irand
+{
+  my $seed = 1;
+  sub mysrand { $seed = $_[0]; }
+  #sub irand { $seed = (1103515245*$seed + 12345) % 4294967296; }
+  sub irand { $seed = ( 16807 * $seed ) % 2147483647; }
+  prime_set_config( irand => \&irand );
+}
+is( random_nbit_prime(10), 571, "random 10-bit prime with custom irand" );
+is( random_nbit_prime(20), 558769, "random 20-bit prime with custom irand" );
+is( random_ndigit_prime(9), 756473437, "random 9-digit with custom irand" );
+
+{
+  my $n = random_nbit_prime(80);
+  is( ref($n), 'Math::BigInt', "random 80-bit prime returns a BigInt" );
+  ok(    $n >= Math::BigInt->new(2)->bpow(79)
+      && $n <= Math::BigInt->new(2)->bpow(80),
+      "random 80-bit prime is in range" );
+}
+{
+  my $n = random_ndigit_prime(30);
+  is( ref($n), 'Math::BigInt', "random 30-digit prime returns a BigInt" );
+  ok(    $n >= Math::BigInt->new(10)->bpow(29)
+      && $n <= Math::BigInt->new(10)->bpow(30),
+      "random 30-digit prime is in range" );
+}
diff --git a/t/17-pseudoprime.t b/t/17-pseudoprime.t
index 93dffe5..0cc9456 100644
--- a/t/17-pseudoprime.t
+++ b/t/17-pseudoprime.t
@@ -73,6 +73,17 @@ my %pseudoprimes = (
  aeslucas1  => [ qw/989 3239 5777 10469 10877 27971 29681 30739 31631 39059 
72389 73919 75077 100127 113573 125249 137549 137801 153931 154697 155819/ ],
  aeslucas2  => [ qw/3239 4531 5777 10877 12209 21899 31631 31831 32129 34481 
36079 37949 47849 50959 51641 62479 73919 75077 97109 100127 108679 113573 
116899 154697 161027/ ],
 );
+
+if ($use64) {
+  push @{$pseudoprimes{psp3}}, 4398117272641;
+  push @{$pseudoprimes{3}}, 1099558795087;
+  push @{$pseudoprimes{lucas}}, 2199055761527;
+  push @{$pseudoprimes{slucas}}, 12598021314449;
+  push @{$pseudoprimes{eslucas}}, 10099386070337;
+  push @{$pseudoprimes{aeslucas1}}, 10071551814917;
+  push @{$pseudoprimes{aeslucas2}}, 34372519409;
+}
+
 my $num_pseudoprimes = 0;
 foreach my $ppref (values %pseudoprimes) {
   $num_pseudoprimes += scalar @$ppref;
@@ -105,6 +116,7 @@ plan tests => 0 + 3
                 + scalar @small_lucas_trials
                 + scalar(keys %lucas_sequences)
                 + 1  # frob-underwood
+                + 2*$use64  # frob-underwood
                 + 1*$extra;
 
 ok(!eval { is_strong_pseudoprime(2047); }, "MR with no base fails");
@@ -216,3 +228,7 @@ while (my($params, $expect) = each (%lucas_sequences)) {
   }
   is($fufail, 0, "is_frobenius_underwood_pseudoprime matches is_prime");
 }
+if ($use64) {
+  is( is_frobenius_underwood_pseudoprime(2727480595375747), 1, "frobenius with 
52-bit prime" );
+  is( is_frobenius_underwood_pseudoprime(10099386070337), 0, "frobenius with 
44-bit lucas pseudoprime" );
+}
diff --git a/t/23-primality-proofs.t b/t/23-primality-proofs.t
index c4b2a54..9915d3a 100644
--- a/t/23-primality-proofs.t
+++ b/t/23-primality-proofs.t
@@ -46,6 +46,7 @@ plan tests => 0
             + 8  # verification failures (Lucas/Pratt)
             + 11 # verification failures (n-1)
             + 7  # verification failures (ECPP)
+            + 3  # Verious other types
             + 0;
 
 is( is_provable_prime(871139809), 0, "871139809 is composite" );
@@ -259,3 +260,36 @@ is( verify_prime([1490266103, "ECPP",
                  [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");
+}
diff --git a/t/32-iterators.t b/t/32-iterators.t
index c16440f..ec7779c 100644
--- a/t/32-iterators.t
+++ b/t/32-iterators.t
@@ -6,15 +6,19 @@ use Test::More;
 use Math::Prime::Util qw/primes prev_prime next_prime
                          forprimes prime_iterator prime_iterator_object/;
 use Math::BigInt try => "GMP,Pari";
+use Math::BigFloat;
 
 my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
 
-plan tests => 8 + 5
-            + 12
-            + 3 + 7
-            + 2
-            + 3 + 7
-            + 25
+plan tests => 8        # forprimes errors
+            + 12 + 5   # forprimes simple
+            + 3        # iterator errors
+            + 7        # iterator simple
+            + 2        # forprimes/iterator nesting
+            + 2        # forprimes BigInt/BigFloat
+            + 3        # oo iterator errors
+            + 7        # oo iterator simple
+            + 25       # oo iterator methods
             + 0;
 
 ok(!eval { forprimes { 1 } undef; },   "forprimes undef");
@@ -108,6 +112,16 @@ ok(!eval { prime_iterator(4.5); }, "iterator 4.5");
   is_deeply( [@t], [qw/23 29 31 29 31 37 31 37 41 37 41 43 47 53 59 61 59 61 
67 71 73 79 73 79 83 79 83 89/], "triple nested iterator" );
 }
 
+# With BigInt and BigFloat objects
+{ my @t;
+  forprimes { push @t, $_ } Math::BigInt->new("5"), Math::BigInt->new("11");
+  is_deeply( [@t], [5,7,11], "forprimes with BigInt range" );
+}
+{ my @t;
+  forprimes { push @t, $_ } Math::BigFloat->new("5"), 
Math::BigFloat->new("11");
+  is_deeply( [@t], [5,7,11], "forprimes with BigFloat range" );
+}
+
 # Test new object iterator
 ok(!eval { prime_iterator_object(-2); }, "iterator -2");
 ok(!eval { prime_iterator_object("abc"); }, "iterator abc");
diff --git a/t/80-pp.t b/t/80-pp.t
index e4b2c8a..788c532 100644
--- a/t/80-pp.t
+++ b/t/80-pp.t
@@ -55,7 +55,13 @@ my %pseudoprimes = (
   37 => [ qw/9 451 469 589 685 817 1333 3781 8905 9271 18631 19517 20591 25327 
34237 45551 46981 47587 48133 59563 61337 68101 68251 73633 79381 79501 83333 
84151 96727/ ],
   61 => [ qw/217 341 1261 2701 3661 6541 6697 7613 13213 16213 22177 23653 
23959 31417 50117 61777 63139 67721 76301 77421 79381 80041/ ],
   73 => [ qw/205 259 533 1441 1921 2665 3439 5257 15457 23281 24617 26797 
27787 28939 34219 39481 44671 45629 64681 67069 76429 79501 93521/ ],
- lucas      => [ qw/5459 5777 10877 16109 18971 22499 24569 25199 40309 58519 
75077 97439/ ],
+ psp2       => [ qw/341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 
4033 4369 4371 4681 5461 6601 7957 8321 8481 8911 10261 10585/ ],
+ psp3       => [ qw/91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 
2821 3281 3367 3751 4961 5551 6601 7381 8401 8911 10585 11011/ ],
+ lucas      => [ qw/9179 10877 11419 11663 13919 14839 16109 16211 18407 18971 
19043/ ],
+ slucas     => [ qw/5459 5777 10877 16109 18971 22499 24569 25199 40309 58519 
75077/ ],
+ eslucas    => [ qw/989 3239 5777 10877 27971 29681 30739 31631 39059 72389 
73919 75077 100127/ ],
+ aeslucas1  => [ qw/989 3239 5777 10469 10877 27971 29681 30739 31631 39059 
72389 73919 75077 100127/ ],
+ aeslucas2  => [ qw/3239 4531 5777 10877 12209 21899 31631 31831 32129 34481 
36079 37949 47849 50959/ ],
 );
 # Test a pseudoprime larger than 2^32.
 push @{$pseudoprimes{2}}, 75792980677 if $use64;
@@ -251,8 +257,8 @@ plan tests => 2 +
               1 + 1 +    # factor
               10 + 8*3 + # factoring subs
               10 +       # AKS
-              2 +        # Lucas and BLS75 primality proofs
-              3 +        # M-R and Lucas on bigint
+              3 +        # Lucas and BLS75 primality proofs
+              4 +        # M-R and Lucas on bigint
               13 +       # Misc util.pm functions
               scalar(keys %ipp) +
               1;
@@ -279,8 +285,13 @@ require_ok 'Math::Prime::Util::PrimalityProving';
     *next_prime     = \&Math::Prime::Util::PP::next_prime;
     *prev_prime     = \&Math::Prime::Util::PP::prev_prime;
 
-    *is_strong_lucas_pseudoprime = 
\&Math::Prime::Util::PP::is_strong_lucas_pseudoprime;
+    *is_pseudoprime = \&Math::Prime::Util::PP::is_pseudoprime;
     *miller_rabin   = \&Math::Prime::Util::PP::miller_rabin;
+    *is_lucas_pseudoprime = \&Math::Prime::Util::PP::is_lucas_pseudoprime;
+    *is_strong_lucas_pseudoprime = 
\&Math::Prime::Util::PP::is_strong_lucas_pseudoprime;
+    *is_extra_strong_lucas_pseudoprime = 
\&Math::Prime::Util::PP::is_extra_strong_lucas_pseudoprime;
+    *is_almost_extra_strong_lucas_pseudoprime = 
\&Math::Prime::Util::PP::is_almost_extra_strong_lucas_pseudoprime;
+    *is_frobenius_underwood_pseudoprime = 
\&Math::Prime::Util::PP::is_frobenius_underwood_pseudoprime;
     *is_aks_prime   = \&Math::Prime::Util::PP::is_aks_prime;
 
     *factor         = \&Math::Prime::Util::PP::factor;
@@ -396,8 +407,21 @@ while (my($base, $ppref) = each (%pseudoprimes)) {
   my $npseudos = scalar @$ppref;
   my @expmr = map { 1 } @$ppref;
   my @gotmr;
-  if ($base eq 'lucas') { @gotmr = map { is_strong_lucas_pseudoprime($_) } 
@$ppref; }
-  else                  { @gotmr = map { miller_rabin($_, $base) } @$ppref;    
     }
+  if ($base =~ /^psp(\d+)/) {
+     my $pbase = $1;
+     @gotmr = map { is_pseudoprime($_, $pbase) } @$ppref;
+  } elsif ($base =~ /^aeslucas(\d+)/) {
+     my $inc = $1;
+     @gotmr = map { is_almost_extra_strong_lucas_pseudoprime($_, $inc) } 
@$ppref;
+  } elsif ($base eq 'eslucas') {
+     @gotmr = map { is_extra_strong_lucas_pseudoprime($_) } @$ppref;
+  } elsif ($base eq 'slucas') {
+     @gotmr = map { is_strong_lucas_pseudoprime($_) } @$ppref;
+  } elsif ($base eq 'lucas') {
+     @gotmr = map { is_lucas_pseudoprime($_) } @$ppref;
+  } else {
+     @gotmr = map { miller_rabin($_, $base) } @$ppref;
+  }
   is_deeply(\@gotmr, \@expmr, "$npseudos pseudoprimes (base $base)");
 }
 
@@ -575,12 +599,16 @@ is_deeply( 
[Math::Prime::Util::PrimalityProving::primality_proof_lucas(100003)],
 is_deeply( 
[Math::Prime::Util::PrimalityProving::primality_proof_bls75(1490266103)],
            [2, "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN 
1490266103\n\nType BLS5\nN 1490266103\nQ[1] 13\nQ[2] 19\nQ[3] 1597\nQ[4] 
1889\nA[0] 5\n----\n"],
            "primality_proof_bls75(1490266103)" );
+is_deeply( 
[Math::Prime::Util::PrimalityProving::primality_proof_bls75(27141057803)],
+           [2, "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN 
27141057803\n\nType BLS5\nN 27141057803\nQ[1] 47533\nQ[2] 285497\n----\n"],
+           "primality_proof_bls75(27141057803)" );
 
 {
   my $n = Math::BigInt->new("168790877523676911809192454171451");
   is( miller_rabin( $n, 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47), 1, 
"168790877523676911809192454171451 looks prime with bases 2..52" );
   is( miller_rabin( $n, 53), 0, "168790877523676911809192454171451 found 
composite with base 53" );
   is ( is_strong_lucas_pseudoprime($n), 0, "168790877523676911809192454171451 
is not a strong Lucas pseudoprime" );
+  is ( is_frobenius_underwood_pseudoprime($n), 0, 
"168790877523676911809192454171451 is not a Frobenius pseudoprime" );
 }
 
 {
diff --git a/t/81-bignum.t b/t/81-bignum.t
index 8fdd9c5..3dd376f 100644
--- a/t/81-bignum.t
+++ b/t/81-bignum.t
@@ -78,6 +78,7 @@ plan tests =>  0
              + 7   # moebius, euler_phi, jordan totient, divsum, znorder
              + 2   # liouville
              + 15  # random primes
+             + 2   # miller-rabin random
              + 0;
 
 # Using GMP makes these tests run about 2x faster on some machines
@@ -118,6 +119,7 @@ use Math::Prime::Util qw/
   random_nbit_prime
   random_strong_prime
   random_maurer_prime
+  miller_rabin_random
   verify_prime
 /;
 # TODO:  is_strong_lucas_pseudoprime
@@ -270,6 +272,13 @@ SKIP: {
 
 ###############################################################################
 
+$randprime = random_nbit_prime(80);
+is( miller_rabin_random( $randprime, 20 ), 1, "80-bit prime passes 
Miller-Rabin with 20 random bases" );
+$randprime += 2 while is_prime($randprime);
+is( miller_rabin_random( $randprime, 40 ), 0, "80-bit composite fails 
Miller-Rabin with 40 random bases" );
+
+###############################################################################
+
 
 sub check_pcbounds {
   my ($n, $expn, $percent, $percentrh) = @_;

-- 
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