This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.40 in repository libmath-prime-util-perl.
commit d57550a045e60a3a6ba85d5ad26438fe831795e2 Author: Dana Jacobsen <d...@acm.org> Date: Thu Mar 6 18:47:44 2014 -0800 random ST primes streamline the 32-bit case, allow 2-bit to return 2 --- lib/Math/Prime/Util.pm | 31 +++++++++++++++++++------------ lib/Math/Prime/Util/RandomPrimes.pm | 14 ++++++++------ 2 files changed, 27 insertions(+), 18 deletions(-) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index d9cca63..4610a2e 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -2355,8 +2355,9 @@ The proof construction consists of a single chain of C<BLS3> types. Construct an n-bit provable prime, using the Shawe-Taylor algorithm in section C.6 of FIPS 186-4. This uses 512 bits of randomness and SHA-256 as the hash. This is a slightly simpler and older (1986) method than -Maurer's 1999 construction. The primary reason to use this rather than -Maurer's method is to use FIPS 186-4 algorithm. +Maurer's 1999 construction. It is a bit faster than Maurer's method, and +uses less system entropy for large sizes. The primary reason to use this +rather than Maurer's method is to use FIPS 186-4 algorithm. Similar to L</random_nbit_prime>, the result will be a BigInt if the number of bits is greater than the native bit size. For better performance @@ -3455,21 +3456,22 @@ Seconds per prime for random prime generation on a circa-2009 workstation, with L<Math::BigInt::GMP>, L<Math::Prime::Util::GMP>, and L<Math::Random::ISAAC::XS> installed. - bits random +testing rand_prov Maurer CPMaurer - ----- -------- -------- --------- -------- -------- - 64 0.0001 +0.000008 0.0002 0.0001 0.022 - 128 0.0020 +0.00023 0.011 0.063 0.057 - 256 0.0034 +0.0004 0.058 0.13 0.16 - 512 0.0097 +0.0012 0.28 0.28 0.41 - 1024 0.060 +0.0060 0.65 0.65 2.19 - 2048 0.57 +0.039 4.8 4.8 10.99 - 4096 6.24 +0.25 31.9 31.9 79.71 - 8192 58.6 +1.61 234.0 234.0 947.3 + bits random +testing rand_prov Maurer Shw-Tylr CPMaurer + ----- -------- -------- --------- -------- -------- -------- + 64 0.0001 +0.000008 0.0002 0.0001 0.010 0.022 + 128 0.0020 +0.00023 0.011 0.063 0.028 0.057 + 256 0.0034 +0.0004 0.058 0.13 0.042 0.16 + 512 0.0097 +0.0012 0.28 0.28 0.085 0.41 + 1024 0.060 +0.0060 0.65 0.65 0.24 2.19 + 2048 0.57 +0.039 4.8 4.8 1.0 10.99 + 4096 6.24 +0.25 31.9 31.9 8.2 79.71 + 8192 58.6 +1.61 234.0 234.0 112.9 947.3 random = random_nbit_prime (results pass BPSW) random+ = additional time for 3 M-R and a Frobenius test rand_prov = random_proven_prime maurer = random_maurer_prime + Shw-Tylr = random_shawe_taylor_prime CPMaurer = Crypt::Primes::maurer L</random_nbit_prime> is reasonably fast, and for most purposes should @@ -3493,6 +3495,11 @@ result is uniformly distributed, only about 10% of the primes in the range are selected for output. This is a result of the FastPrime algorithm and is usually unimportant. +L</random_shawe_taylor_prime> similarly constructs a provable prime. It +uses a simpler construction method. The implementation uses a single large +random seed followed by SHA-256 as specified by FIPS 186-4. As seen, it +is a bit faster than the Maurer implementation. + L<Crypt::Primes/maurer> times are included for comparison. It is pretty fast for small sizes but gets slow as the size increases. It does not perform any primality checks on the intermediate results or the final diff --git a/lib/Math/Prime/Util/RandomPrimes.pm b/lib/Math/Prime/Util/RandomPrimes.pm index 6c6b4d2..d1306ca 100644 --- a/lib/Math/Prime/Util/RandomPrimes.pm +++ b/lib/Math/Prime/Util/RandomPrimes.pm @@ -883,15 +883,18 @@ sub _ST_Random_prime { # From FIPS 186-4 if ($k < 33) { my $seed = $input_seed; my $prime_gen_counter = 0; + my $kmask = 0xFFFFFFFF >> (32-$k); # Does the mod operation + my $kstencil = (1 << ($k-1)) + ($k > 2); # Sets high and low bits while (1) { my $seedp1 = _seed_plus_one($seed); my $cvec = Digest::SHA::sha256($seed) ^ Digest::SHA::sha256($seedp1); - my $c = Math::BigInt->from_hex('0x' . unpack("H*", $cvec)); - $c = $k2 + ($c % $k2); - $c = (2 * ($c >> 1)) + 1; + # my $c = Math::BigInt->from_hex('0x' . unpack("H*", $cvec)); + # $c = $k2 + ($c % $k2); + # $c = (2 * ($c >> 1)) + 1; + my($c) = unpack("L*", substr($cvec,-4,4)); + $c = ($c & $kmask) | $kstencil; $prime_gen_counter++; $seed = _seed_plus_one($seedp1); - # c is small so we can provably test it. my ($isp, $cert) = is_provable_prime_with_cert($c); return (1,$c,$seed,$prime_gen_counter,$cert) if $isp; return (0,0,0,0) if $prime_gen_counter > 10000 + 16*$k; @@ -936,8 +939,7 @@ sub _ST_Random_prime { # From FIPS 186-4 } if ($looks_prime) { - # We really should do what Maurer does and just test a in (2,3,5,7,11,13). - # Instead we'll do the FIPS 186-4 method, which is rather stupid. + # We could use a in (2,3,5,7,11,13), but pedantically use FIPS 186-4. my $astr = ''; for my $i (0 .. $iterations) { $astr = Digest::SHA::sha256_hex($seed) . $astr; -- 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