This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.26 in repository libmath-prime-util-perl.
commit 3e6ff85c99601c1b4b27005830c7c8f9b1f4a723 Author: Dana Jacobsen <d...@acm.org> Date: Thu Apr 18 21:43:09 2013 -0700 Add GMP-ECPP verification example --- MANIFEST | 1 + TODO | 15 +++------- examples/verify-gmp-eccp-cert.pl | 61 ++++++++++++++++++++++++++++++++++++++++ lib/Math/Prime/Util.pm | 11 ++++---- lib/Math/Prime/Util/PP.pm | 1 - 5 files changed, 72 insertions(+), 17 deletions(-) diff --git a/MANIFEST b/MANIFEST index 10a9f2b..f0044b0 100644 --- a/MANIFEST +++ b/MANIFEST @@ -58,6 +58,7 @@ examples/test-bpsw.pl examples/test-factor-gnufactor.pl examples/test-primes-script.pl examples/test-primes-script2.pl +examples/verify-gmp-eccp-cert.pl bin/primes.pl bin/factor.pl t/01-load.t diff --git a/TODO b/TODO index d3db691..39a2833 100644 --- a/TODO +++ b/TODO @@ -33,14 +33,7 @@ - Implement S2 calculation for LMO prime count. -- Add primality proof output to is_provable_prime. - -- Fixup EllipticCurve so we define points and a curve. - -- Change is_provable_prime from Lucas to BLS75. - -- Use EllipticCurve to make ecm_factor. - -- add recursive AGKM format. - -- Can we easily provide a certificate for Maurer primes? +- Add Sage output style verification. Looks like NZMATH has ECPP but doesn't + produce a certificate. Adding a Primo parser (see WraithX's code) would + be awesome, but may be a lot more work. It would still be nice to have yet + another independent codebase for this. diff --git a/examples/verify-gmp-eccp-cert.pl b/examples/verify-gmp-eccp-cert.pl new file mode 100644 index 0000000..de3e616 --- /dev/null +++ b/examples/verify-gmp-eccp-cert.pl @@ -0,0 +1,61 @@ +#!/usr/bin/env perl +use warnings; +use strict; +use Math::BigInt try=>"GMP,Pari"; +use Math::Prime::Util qw/:all/; +use Data::Dump qw/dump/; + +# Takes the output of GMP-ECPP, creates a certificate in the format used +# by MPU, and runs it through the verifier. +# +# Example: +# +# perl -MMath::Prime::Util -E 'say random_ndigit_prime(60)' | \ +# gmp-ecpp -q | \ +# perl examples/verify-gmp-eccp-cert.pl + + +my $early_check = 0; + +my $N; +my ($n, $a, $b, $m, $q, $Px, $Py); +my @cert; + +while (<>) { + if (/^N\[(\d+)\]\s*=\s*(\d+)/) { + $n = $2; + if ($1 == 0) { + die "Bad input" if defined $N; + $N = $n; + @cert = ($n, "AGKM"); + } + } + elsif (/^a\s*=\s*(\d+)/) { $a = $1; } + elsif (/^b\s*=\s*(\d+)/) { $b = $1; } + elsif (/^m\s*=\s*(\d+)/) { $m = $1; } + elsif (/^q\s*=\s*(\d+)/) { $q = $1; } + elsif (/^P\s*=\s*\(\s*(\d+)\s*,\s*(\d+)\s*\)/) { + $Px = $1; + $Py = $2; + die "Bad input\n" + unless defined $N && defined $a && defined $b && defined $m + && defined $q && defined $Px && defined $Py; + + # If for a given q value, is_prime returns 2, that indicates it can + # produce an n-1 primality proof very quickly, so we could stop now. + if ($early_check) { + my $bq = Math::BigInt->new("$q"); + if (is_prime($bq) == 2) { + push @cert, [$n, $a, $b, $m, [prime_certificate($bq)], [$Px,$Py]]; + last; + } + } + push @cert, [$n, $a, $b, $m, $q, [$Px,$Py]]; + } + else { + last if /^proven prime/; + } +} + +print dump(\@cert), "\n"; +print verify_prime(@cert) ? "SUCCESS\n" : "FAILURE\n"; diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index e7e4d47..58e7724 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -1902,8 +1902,8 @@ sub verify_prime { warn "verify_prime: incorrect AGKM format\n"; return 0; } - my ($ni, $a, $b, $m, $q, $P); - $q = $n; + my ($ni, $a, $b, $m, $P); + my ($qval, $q) = ($n, $n); foreach my $block (@pdata) { if (ref($block) ne 'ARRAY' || scalar @$block != 6) { warn "verify_prime: incorrect AGKM block format\n"; @@ -1913,7 +1913,8 @@ sub verify_prime { warn "verify_prime: incorrect AGKM block format: block n != q\n"; return 0; } - ($ni, $a, $b, $m, $q, $P) = @$block; + ($ni, $a, $b, $m, $qval, $P) = @$block; + $q = ref($qval) eq 'ARRAY' ? $qval->[0] : $qval; if (ref($P) ne 'ARRAY' || scalar @$P != 2) { warn "verify_prime: incorrect AGKM block point format\n"; return 0; @@ -1953,8 +1954,8 @@ sub verify_prime { return 0; } } - # Check primality of last q using BPSW - return 0 unless verify_prime($q); + # Check primality of last q + return 0 unless verify_prime($qval); print "primality success: $n by A-K-G-M elliptic curve\n" if $verbose > 1; return 1; diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index d8a7bcd..f8f75a8 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -1856,7 +1856,6 @@ sub primality_proof_lucas { return @composite; } -use Data::Dump qw/dump/; sub primality_proof_bls75 { my ($n) = shift; my @composite = (0, []); -- 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