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 4eb186d88ee41723c6eb63f7e8d544d90e2c8d81 Author: Dana Jacobsen <d...@acm.org> Date: Wed Mar 5 18:34:22 2014 -0800 Shawe-Taylor random provable primes. No documentation. --- lib/Math/Prime/Util.pm | 8 +++ lib/Math/Prime/Util/RandomPrimes.pm | 100 ++++++++++++++++++++++++++++++++++++ 2 files changed, 108 insertions(+) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index ac134a3..7f5aba5 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -36,6 +36,7 @@ our @EXPORT_OK = random_prime random_ndigit_prime random_nbit_prime random_strong_prime random_proven_prime random_proven_prime_with_cert random_maurer_prime random_maurer_prime_with_cert + random_shawe_taylor_prime primorial pn_primorial consecutive_integer_lcm gcd lcm factor factor_exp all_factors divisors moebius mertens euler_phi jordan_totient exp_mangoldt liouville @@ -335,6 +336,13 @@ sub random_maurer_prime { return Math::Prime::Util::RandomPrimes::random_maurer_prime($bits); } +sub random_shawe_taylor_prime { + my($bits) = @_; + _validate_num($bits, 2) || _validate_positive_integer($bits, 2); + require Math::Prime::Util::RandomPrimes; + return Math::Prime::Util::RandomPrimes::random_shawe_taylor_prime(@_); +} + sub random_maurer_prime_with_cert { my($bits) = @_; _validate_num($bits, 2) || _validate_positive_integer($bits, 2); diff --git a/lib/Math/Prime/Util/RandomPrimes.pm b/lib/Math/Prime/Util/RandomPrimes.pm index a7135e8..35b88ec 100644 --- a/lib/Math/Prime/Util/RandomPrimes.pm +++ b/lib/Math/Prime/Util/RandomPrimes.pm @@ -832,6 +832,106 @@ sub random_maurer_prime_with_cert { croak "Failure in random_maurer_prime, could not find a prime\n"; } # End of random_maurer_prime +sub random_shawe_taylor_prime { + my $k = shift; + my $which = shift; + + my $seed; + { + # TODO: should go through RANDF + if (!defined $_BRS) { + require Bytes::Random::Secure; + $_BRS = Bytes::Random::Secure->new(NonBlocking=>1); + } + $seed = $_BRS->bytes(512/8); + } + + my($status,$prime,$prime_seed,$prime_gen_counter) + = _ST_Random_prime($k, $seed); + croak "Shawe-Taylor random prime failure: loop overflow" unless $status; + + return $prime; +} + +sub _seed_plus_one { + my($s) = @_; + for (my $i = length($s)-1; $i >= 0; $i--) { + vec($s, $i, 8)++; + last unless vec($s, $i, 8) == 0; + } + return $s; +} + +sub _ST_Random_prime { # From FIPS 186-4 + my($k, $input_seed) = @_; + croak "Shawe-Taylor random prime must have length >= 2" if $k < 2; + $k = int("$k"); + + croak "Shawe-Taylor random prime, invalid input seed" + unless defined $input_seed && length($input_seed) >= 32; + + if (!defined $Digest::SHA::VERSION) { + eval { require Digest::SHA; $Digest::SHA::VERSION >= 2.00; } + or do { croak "Must have Digest::SHA 2.00 or later"; }; + } + + my $k2 = Math::BigInt->new(2)->bpow($k-1); + + if ($k < 33) { + my $seed = $input_seed; + my $prime_gen_counter = 0; + 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; + $prime_gen_counter++; + $seed = _seed_plus_one($seedp1); + # c is small so we can provably test it. + return (1,$c,$seed,$prime_gen_counter) if is_prob_prime($c); + return (0,0,0,0) if $prime_gen_counter > 4*$k; + } + } + my($status,$c0,$seed,$prime_gen_counter) + = _ST_Random_prime( (($k+1)>>1)+1, $input_seed); + return (0,0,0,0) unless $status; + my $iterations = int(($k + 255) / 256) - 1; # SHA256 generates 256 bits + my $old_counter = $prime_gen_counter; + my $xstr = ''; + for my $i (0 .. $iterations) { + $xstr = Digest::SHA::sha256_hex($seed) . $xstr; + $seed = _seed_plus_one($seed); + } + my $x = Math::BigInt->from_hex('0x'.$xstr); + $x = $k2 + ($x % $k2); + my $t = ($x + 2*$c0 - 1) / (2*$c0); + while (1) { + if (2*$t*$c0 + 1 > 2*$k2) { $t = ($k2 + 2*$c0 - 1) / (2*$c0); } + my $c = 2*$t*$c0 + 1; + $prime_gen_counter++; + # Only do this if we're pretty sure the candidate is prime. + if (is_prob_prime($c)) { + my $astr = ''; + for my $i (0 .. $iterations) { + $astr = Digest::SHA::sha256_hex($seed) . $astr; + $seed = _seed_plus_one($seed); + } + my $a = Math::BigInt->from_hex('0x'.$astr); + $a = ($a % ($c-3)) + 2; + my $z = $a->copy->bmodpow(2*$t,$c); + if (Math::BigInt::bgcd($z-1,$c)->is_one && $z->copy->bmodpow($c0,$c)->is_one) { + croak "Shawe-Taylor random prime failure at ($k): $c not prime" + unless is_prob_prime($c); + return (1, $c, $seed, $prime_gen_counter); + } + } + return (0,0,0,0) if $prime_gen_counter > 4*$k + $old_counter; + $t++; + } +} + + # Gordon's algorithm for generating a strong prime. sub random_strong_prime { my $t = shift; -- 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