← Back to branch summary

~ubuntu-branches/ubuntu/trusty/libmath-prime-util-gmp-perl/trusty

« back to all changes in this revision

Viewing changes to t/17-pseudoprime.t

  • Committer: Package Import Robot
  • Author(s): gregor herrmann
  • Date: 2013-12-21 22:30:22 UTC
  • mfrom: (4.1.1 sid)
  • Revision ID: package-import@ubuntu.com-20131221223022-3qji7vypk03d2i83
Tags: 0.16-1
* Team upload.
* New upstream release.
* Add years of upstream copyright.
* Add debian/NEWS, mentioning an API change.
* Make Recommends on libmath-prime-util-perl versioned.
* Slightly improve short and long description.
* Use debhelper 9.20120312 to get all hardening flags.
* Use canonical URL in Vcs-Git field.
* Install example scripts.
* Add a patch to fix a spelling mistake.
* Declare compliance with Debian Policy 3.9.5.

Show diffs side-by-side

added added

removed removed

Lines of Context:
t/17-pseudoprime.t
3
3
use warnings;
4
4
 
5
5
use Test::More;
6
 
use Math::Prime::Util::GMP qw/is_strong_pseudoprime is_strong_lucas_pseudoprime is_prime/;
 
6
use Math::Prime::Util::GMP qw/
 
7
   is_strong_pseudoprime
 
8
   is_lucas_pseudoprime
 
9
   is_strong_lucas_pseudoprime
 
10
   is_extra_strong_lucas_pseudoprime
 
11
   is_almost_extra_strong_lucas_pseudoprime
 
12
   is_prime
 
13
   lucas_sequence
 
14
   miller_rabin_random
 
15
   primes/;
 
16
my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
7
17
 
8
18
# pseudoprimes from 2-100k for many bases
9
19
 
36
46
 1795265022 => [ qw/1795265023 1797174457 1797741901 1804469753 1807751977 1808043283 1808205701 1813675681 1816462201 1817936371 1819050257/ ],
37
47
 3046413974 => [ qw/3046413975 3048698683 3051199817 3068572849 3069705673 3070556233 3079010071 3089940811 3090723901 3109299161 3110951251 3113625601/ ],
38
48
 3613982119 => [ qw/3626488471 3630467017 3643480501 3651840727 3653628247 3654142177 3672033223 3672036061 3675774019 3687246109 3690036017 3720856369/ ],
39
 
 lucas      => [ qw/5459 5777 10877 16109 18971 22499 24569 25199 40309 58519 75077 97439/ ],
 
49
 lucas      => [ qw/323 377 1159 1829 3827 5459 5777 9071 9179 10877 11419 11663 13919 14839 16109 16211 18407 18971 19043/ ],
 
50
 slucas     => [ qw/5459 5777 10877 16109 18971 22499 24569 25199 40309 58519 75077 97439 100127 113573 115639 130139/ ],
 
51
 eslucas    => [ qw/989 3239 5777 10877 27971 29681 30739 31631 39059 72389 73919 75077 100127 113573 125249 137549 137801 153931 155819/ ],
 
52
 aeslucas1  => [ qw/989 3239 5777 10469 10877 27971 29681 30739 31631 39059 72389 73919 75077 100127 113573 125249 137549 137801 153931 154697 155819/ ],
 
53
 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/ ],
40
54
);
41
55
my $num_pseudoprimes = 0;
42
56
foreach my $ppref (values %pseudoprimes) {
43
57
  $num_pseudoprimes += scalar @$ppref;
44
58
}
45
 
my @small_lucas_trials = (2, 9, 16, 100, 102, 2047, 2048, 5781, 9000, 14381);
 
59
 
 
60
# 323 and 377 are Lucas pseudoprimes, but not strong Lucas pseudoprimes
 
61
my @small_lucas_trials = (2, 9, 16, 100, 102, 323, 377, 2047, 2048, 5781, 9000, 14381);
46
62
 
47
63
my %large_pseudoprimes = (
48
64
   '75792980677' => [ qw/2/ ],
59
75
  $num_large_pseudoprime_tests += scalar @{$large_pseudoprimes{$psrp}};
60
76
}
61
77
 
62
 
 
63
 
plan tests => 0 + 7
 
78
my %lucas_sequences = (
 
79
  "323 1 1 324" => [0,2,1],
 
80
  "323 4 1 324" => [170,308,1],
 
81
  "323 4 5 324" => [194,156,115],
 
82
  "323 3 1 324" => [0,2,1],
 
83
  "323 3 1  81" => [0,287,1],
 
84
  "323 5 -1 81" => [153,195,322],
 
85
  "49001 25 117 24501" => [20933,18744,19141],
 
86
  "18971 10001 -1 4743" => [5866,14421,18970],
 
87
);
 
88
 
 
89
 
 
90
plan tests => 0 + 9
64
91
                + 3
65
92
                + 6
66
93
                + $num_pseudoprimes
67
94
                + 1  # mr base 2    2-4k
68
95
                + 9  # mr with large bases
69
96
                + scalar @small_lucas_trials
70
 
               # + $num_large_pseudoprime_tests
 
97
                + scalar(keys %lucas_sequences)
 
98
              # + $num_large_pseudoprime_tests
 
99
                + 10*$extra  # Large Carmichael numbers
 
100
                + 2 # M-R-random
71
101
                + 0;
72
102
 
73
103
eval { is_strong_pseudoprime(2047); };
76
106
like($@, qr/defined/i, "is_strong_pseudoprime with base undef fails");
77
107
eval { is_strong_pseudoprime(2047, ''); };
78
108
like($@, qr/positive/i, "is_strong_pseudoprime with base '' fails");
79
 
# We return 1 for bases 0 and 1 now
80
 
#eval { is_strong_pseudoprime(2047,0); };
81
 
#like($@, qr/>= 2/i, "is_strong_pseudoprime with base 0 fails");
82
 
#eval { is_strong_pseudoprime(2047,1); };
83
 
#like($@, qr/>= 2/i, "is_strong_pseudoprime with base 1 fails");
 
109
eval { is_strong_pseudoprime(2047,0); };
 
110
like($@, qr/invalid/i, "is_strong_pseudoprime with base 0 fails");
 
111
eval { is_strong_pseudoprime(2047,1); };
 
112
like($@, qr/invalid/i, "is_strong_pseudoprime with base 1 fails");
84
113
eval { is_strong_pseudoprime(2047,-7); };
85
114
like($@, qr/positive/i, "is_strong_pseudoprime with base -7 fails");
86
115
eval { is_strong_pseudoprime(undef, 2); };
108
137
# Check that each strong pseudoprime base b makes it through MR with that base
109
138
while (my($base, $ppref) = each (%pseudoprimes)) {
110
139
  foreach my $p (@$ppref) {
111
 
    if ($base eq 'lucas') {
 
140
    if       ($base =~ /^aeslucas(\d+)/) {
 
141
      my $inc = $1;
 
142
      ok(is_almost_extra_strong_lucas_pseudoprime($p,$inc), "$p is an almost extra strong Lucas pseudoprime (increment $inc)");
 
143
    } elsif ($base eq 'eslucas') {
 
144
      ok(is_extra_strong_lucas_pseudoprime($p), "$p is an extra strong Lucas pseudoprime");
 
145
    } elsif ($base eq 'slucas') {
112
146
      ok(is_strong_lucas_pseudoprime($p), "$p is a strong Lucas-Selfridge pseudoprime");
 
147
    } elsif ($base eq 'lucas') {
 
148
      ok(is_lucas_pseudoprime($p), "$p is a Lucas-Selfridge pseudoprime");
113
149
    } else {
114
150
      ok(is_strong_pseudoprime($p, $base), "Pseudoprime (base $base) $p passes MR");
115
151
    }
151
187
    ok(!is_strong_lucas_pseudoprime($n), "$n is not a prime and not a strong Lucas-Selfridge pseudoprime");
152
188
  }
153
189
}
 
190
 
 
191
while (my($params, $expect) = each (%lucas_sequences)) {
 
192
  my ($n, $p, $q, $k) = split(' ', $params);
 
193
  is_deeply( [lucas_sequence($n,$p,$q,$k)], $expect, "Lucas sequence $params" );
 
194
}
 
195
 
 
196
if ($extra) {
 
197
  my $n;
 
198
  # Zhang 2004
 
199
  $n = "9688312712744590973050578123260748216127001625571";
 
200
  is( is_strong_pseudoprime($n, 2..70), 1, "968..571 is spsp(1..70)" );
 
201
  is( is_strong_pseudoprime($n, 71),    0, "968..571 is found composite by base 71" );
 
202
  # Bleichenbacher
 
203
  $n = "68528663395046912244223605902738356719751082784386681071";
 
204
  is( is_strong_pseudoprime($n, @{primes(2,100)}), 1, "685..071 is spsp(1..100)" );
 
205
  is( is_strong_pseudoprime($n, 101),    0, "685..071 is found composite by base 101" );
 
206
  # Arnault 1994, strong pseudoprime to all bases up to 306
 
207
  #my $p1 = Math::BigInt->new("29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883");
 
208
  #$n = $p1* (313 * ($p1-1) + 1) * (353 * ($p1-1) + 1);
 
209
  $n = "2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867";
 
210
  is( is_strong_pseudoprime($n, @{primes(2,306)}), 1, "Arnault-397 Carmichael is spsp(1..306)" );
 
211
  is( is_strong_pseudoprime($n, 307), 0, "Arnault-397 Carmichael is found composite by base 307" );
 
212
  # Strong pseudoprime to first 150 bases
 
213
  $n = "2504564851231996223418611498583553580586431162725714036294663419005627942030045018144967085826016995812748308972856014960994030057096300272690934546847718913274308904632162037753108744756079484071197757334474410667077275268095650646955133107287726653142089063491101528203219286279619714745365476456016263876476506935633902632378276445418807506643579691598485378380707876204179521868647423847956174718793857337275560326966743283833603259339320266954292802259534246253628396748505321522751546284902630334444060405092248083998624231344891540701484875133564504847404605998928272819163447443703835478321841022013831138852193839499198235152203734163783925867691241340516136948911294063782761240713332883707486122030071233696262539897861764349350102562679795879652984483644711085101952997260985769555028200212433179592354351467963621580674595217679045289986395851940360535530808265791863676735166100444465385760336851651312776349197351443263637225179385994064241024523629682623814114793546441523513505946466820080716059467";
 
214
  is( is_strong_pseudoprime($n, @{primes(2,876)}), 1, "250...467 is spsp(1..876)" );
 
215
  is( is_strong_pseudoprime($n, 877), 0, "250..467 is found composite by base 877" );
 
216
  # Strong pseudoprime to first 168 bases
 
217
  # N = (n+1) * (37*n+1) * (41*n+1)
 
218
  $n = "2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867";
 
219
  is( is_strong_pseudoprime($n, @{primes(2,1008)}), 1, "280...867 is spsp(1..876)" );
 
220
  is( is_strong_pseudoprime($n, 1009), 0, "280..867 is found composite by base 877" );
 
221
}
 
222
 
 
223
{
 
224
  my @mrs = map { miller_rabin_random($_, 0) } 0 .. 999;
 
225
  my @expect = (1) x 1000;
 
226
  is_deeply( [@mrs], [@expect], "Miller-Rabin with 0 random bases" );
 
227
}
 
228
{
 
229
  # This is the number above which fails the first 168 bases.
 
230
  my $n = "2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867";
 
231
  # 33 random bases on a 3948 bit number => p < 1e-200.
 
232
  # This is why we use k random bases and not the first k bases.
 
233
  my $isprime = miller_rabin_random($n, 33);
 
234
  is($isprime, 0, "Miller-Rabin with 100 uniform random bases for n returns prime" );
 
235
}