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.
RT for rt.cpan.org