Skip Menu |
 

This queue is for tickets about the Crypt-Primes CPAN distribution.

Report information
The Basics
Id: 81858
Status: open
Priority: 0/
Queue: Crypt-Primes

People
Owner: Nobody in particular
Requestors: DANAJ [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Critical
Broken in: 0.50
Fixed in: (no value)



Download (untitled) / with headers
text/plain 2.9k
Non-primes can be output. The following composites were output as primes, among others: k = 21: $n = 1911397 $q = 3389 $R = 282 $a = 157556 k = 22: $n = 3928201 $q = 6547 $R = 300 $a = 1484394 k = 23: $n = 5652191 $q = 5827 $R = 485 $a = 1681748 k = 24: $n = 10661593 $q = 10331 $R = 516 $a = 9714028 k = 25: $n = 23098001 $q = 11549 $R = 1000 $a = 6646295 k = 26: $n = 58430417 $q = 30181 $R = 968 $a = 18479234 k = 27: $n = 91232443 $q = 23357 $R = 1953 $a = 13984184 k = 28: $n = 134314891 $q = 61331 $R = 1095 $a = 93910376 k = 29: $n = 294064651 $q = 59407 $R = 2475 $a = 136600046 k = 30: $n = 678452923 $q = 85469 $R = 3969 $a = 223918500 k = 31; $n = 1664622517 $q = 113797 $R = 7314 $a = 1524268152 k = 32: $n = 4161742801 $q = 204007 $R = 10200 $a = 3552462523 k = 33: $n = 8346731851 $q = 135389 $R = 30825 $a = 4625470817 k = 34: $n = 10507024331 $q = 355087 $R = 14795 $a = 683743932 k = 35: $n = 22906099031 $q = 524287 $R = 21845 $a = 20000672580 k = 36: $n = 67746784591 $q = 1041137 $R = 32535 $a = 3251985907 k = 37: $n = 130367729377 $q = 538247 $R = 121104 $a = 76521143978 k = 40: $n = 673761838129 $q = 3205459 $R = 105096 $a = 435193122567 k = 45: $n = 34249843808647 $q = 14335241 $R = 1194603 $a = 11836036430930 k = 45: $n = 21934702357663 $q = 16958449 $R = 646719 $a = 6112934571513 k = 50: $n = 855983502397553 $q = 180945769 $R = 2365304 $a = 104098228240266 A couple ways to see these -- it usually takes less than a minute to reproduce the smaller sizes: perl -MCrypt::Primes=maurer -MMath::Prime::Util=is_pr'while (1) { $n = maurer(Size=>22); die "$n\n" if !is_prime($n->pari2iv); }' perl -MCrypt::Primes=maurer -MMatality=is_prime -E 'while (1) { $n = maurer(Size=>22); die "$n\n" if !is_prime($n->pari2iv); }' Obviously these bit sizes are very small, but I believe this can still happen for large bit sizes -- it is just much rarer. I admit I have not seen examples with larger bit sizes. The code does not implement the tests for either Lemma 1 or Lemma 2 of Maurer's paper. It uses only a small part of Lemma 2. Hence the values of n are not proven prime. Given the r setting being used (0.5 - 1), Lemma 1 should be used. This means after checking b == 1, we need to ensure gcd( a^(2*R) mod n - 1, n) == 1. This is Lemma 1, and Menezes 4.62 uses this. Lemma 2 _also_ includes the gcd. I suspect you read Menezes Note 4.63 (i) which indicates q > n^(1/3) is necessary, with the implication that this is sufficient. That note refers to Lemma 2, which has additional requirements. The point of using Lemma 2 is that we can make r >= 0.33334 instead of r >= 0.5, which means smaller q values can be used, reducing the levels of recursion. But this isn't done in the Crypt::Primes code. When q > R (as is the case with r >= 0.5) then the additional requirements of Lemma 2 are often not true because x = 0, hence forcing y^2-4x to be a perfect square.
Download (untitled) / with headers
text/plain 750b
Looks like my terminal had some issues when pasting in the commands to get a quick reproduce: perl -MCrypt::Primes=maurer -MMath::Prime::Util=is_prime -E 'while (1) { $n = maurer(Size=>22); die "$n\n" if !is_prime($n->pari2iv); }' or perl -MCrypt::Primes=maurer -MMath::Primality=is_prime -E 'while (1) { $n = maurer(Size=>22); die "$n\n" if !is_prime($n->pari2iv); }' Alternately write to a file, e.g.: perl -MCrypt::Primes=maurer -E 'while (1) { my $n = maurer(Size=>80); say $n; }' >/tmp/p80 then run something like: perl -Mbigint -MMath::Prime::Util=:all -ne 'chomp; warn $_ unless is_prob_prime($_)' /tmp/p80 Or insert a primality test into the maurer code after it decides $n is prime, and have it write out the k/n/a/R/q values.
Download (untitled) / with headers
text/plain 2.7k
Attached is a patch that fixes this, as well as two changes to increase prime diversity. (1) Prime diversity: Maurer's paper uses q = floor(r*k). Menezes et al. uses q = floor(r*k)+1. Crypt::Primes uses q = floor(r*k)+2. After testing, the +1 version generates the most primes: Number of unique 20-bit primes generated with p0=12: +0 2877 +1 3597 +2 3229 (2) Prime diversity: The number I should be chosen in the interval [I+1, 2I]. makerandom_itv uses an inclusive lower limit and an exclusive upper limit. Crypt::Primes was using 2I as the upper limit, meaning 2I would never get selected. This ended up dropping off many primes in the high end. I suspect the two calls selecting $a have the same issue, but at least the non-Generator one is really not important. (3) The critical patch. This implements Lemma 1. I have not seen composites output after this patch. --- lib/Crypt/Primes-orig.pm 2003-01-16 12:08:32.000000000 -0800 +++ lib/Crypt/Primes.pm 2012-12-11 22:31:54.675376956 -0800 @@ -592,7 +79,7 @@ $r = 0.5; } - my $q = maurer ( Size => floor ( $r * $k ) + 2, Verbosity => $v, + my $q = maurer ( Size => floor ( $r * $k ) + 1, Verbosity => $v, Generator => $params{Generator}, Intermediates => $params{Intermediates} ); if ($params{Relprime}) { while ((grep /$q/, @used)) { @@ -613,7 +100,7 @@ while (1) { - my $R = PARI ( makerandom_itv ( Lower => $I + 1, Upper => 2 * $I ) ); + my $R = PARI ( makerandom_itv ( Lower => $I + 1, Upper => 2 * $I + 1 ) ); $n = floor( 2 * $R * $q + 1 ); print "n = $n\n" if $v == 2; print "." if $v == 1; @@ -624,9 +111,11 @@ print "(passes trial division)\n" if $v == 2; print "+" if $v == 1; $a = makerandom_itv( Lower => 2, Upper=> $n - 2 ); $a = makerandom_itv( Lower => 2, Upper=> $R ) if $params{Generator}; - my $t1 = Mod (2, $n); my $t2 = Mod ($a, $n); + my $t2 = Mod ($a, $n); my $b = $t2 ** ( $n - 1 ); - if ( ($b == 1) && ( $q > $n ** (1/3.0) ) ) { + if ( $b == 1 ) { + $b = $t2 ** ( 2 * $R ); + if (gcd($b-1, $n) == 1) { print "$n is prime! a = $a, R = $R\n" if $v == 2; print "($k)" if $v == 1; my @s; @@ -648,9 +137,9 @@ return { @factors, @intermediates, Prime => $n, Generator => $a } if $params{Generator}; return { @factors, @intermediates, Prime => $n } if $params{Factors} or $params{Intermediates}; return $n; - } - } - + } # gcd(a^((n-1)/q)-1 mod n, n) == 1 [(n-1)/q = 2R] + } # a^n-1 mod n == 1 + } # BASE } }


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.