Re: More primality testing (was: Elementary group theory: Proof of Fermat-Maas ...)

Since your post is long enough and since Tim Peters already answered
most parts (better than I could have done), I only answered your
questions regarding ECPP.

robert maas, see http://tinyurl.com/uh3t a écrit :
From: mm <m...@xxxxxxxxxx>
An addendum to my earlier followup. You cited several large numbers
you believe to be prime, but which you can't prove prime, and
challeged me to try to prove them prime. I counter-challenge. Below
are several large numbers I've already proven to be prime. Can you
also prove them prime? Some are really easy to prove prime if you
know the trick, while others are much more difficult.
Difficult with a "N-1" method, not with ECPP (Elliptic Curve Primality
Proving).

Did you program the ECPP yourself,

Yes.

or take somebody else's program
source and study it carefully to make sure you understand how it
works and trust it based on that understanding,

The only published ECPP source I know is in the LiDIA library. But it
is still too new to be fast (optimizing an ECPP implementation takes
time).

or did you just
trust some canned program without actually checking what it does
inside?

With ECPP, there is no need to check the program itself. ECPP has a
redhibitory advantage over all of its competitors [*], it produces
primality certificates. When running ECPP, if there is a hardware
failure or a bug in the program, either the program stops because of the
error or it produces an invalid certificate. In any case, we know that a
problem occurred. One could almost say that ECPP doesn't answer the
question 'Is this number prime?' but replaces it by a more easy one: 'Is
this certificate valid?'

[*] i.e., over APR-CL. No, it has no other one. AKS is a theoretical
revolution but, practically, to prove primality it is about as useful as
the Wilson theorem. (I am making a lot of friends there :-) )

[...] Is the Atkin-Goldwasser-kilian-morain certificate really faster
than the Pratt/Maas certificate if factorization of p-1 is
recursively known a priori due to direct construction of (p-1)/2
as a product already, for very large primes?

No. And, by using the Pocklington theorem, the difference would still
be greater. An ECPP certificate contains steps with "N-1" and "N+1" (Lucas) tests. They are used when this is possible precisely because
they are faster than a "EC" test.

I did a little experiment here just now. The following rather large
numbers are proven primes (by Pratt/Maas algorithm, formerly called
Fermat-Maas algorithm):

p1=954622147622608228972957007162328813832449706078477027700171216291543973761033616918333544268480756481510147656340593480746164697244619229336689663500803

p2=238464250384981680094134371148714282404227028068564027156500248280054808239211936121703390658836551417208081166489028260466711956419068655903034092225372055369392452746858308197514641758277050896406901813381632810192811343046636456415032392862112129202297173693585844727359092396894123304123306705856304586616598339768773337899176643

Constructing a certificate for each requires three steps: Run the
algorithm to prove it's really prime (which doesn't take long).
Convert the proof to a single base that is a primitive element
(which doesn't take long either). Issue a certificate stating the
base (virtually instant, limited by I/O rate rather than any
computing that is needed). (And do same recursively for factors of
p-1 if they are large enough to not be "apparently" prime already.)
Let me time my method:

(setq p1 954622147622608228972957007162328813832449706078477027700171216291543973761033616918333544268480756481510147656340593480746164697244619229336689663500803)
(setq p2 238464250384981680094134371148714282404227028068564027156500248280054808239211936121703390658836551417208081166489028260466711956419068655903034092225372055369392452746858308197514641758277050896406901813381632810192811343046636456415032392862112129202297173693585844727359092396894123304123306705856304586616598339768773337899176643)
[...]
(72 517)
That's just over 0.7 second to prove&make the certificate for the
153-digit prime, and just over 5 seconds to prove&make the
certificate for the 333-digit prime.
(list (- 13310 13283) (- 13924 13827))
(27 97)
That's just over a quarter-second to verify the certificate for the
153-digit prime, and just under 1 second to verify the certificate
for the 333-digit prime.

And my code isn't even compiled (except by incremental compiler
built into CMUCL interpretor).

How long does it take to generate, and to verify, an
Atkin-Goldwasser-kilian-morain certificate for those same primes?

Certifying p1 -> 0.32s
Verifying the certificate -> 0.10s
Certifying p2 -> 10.24s
Verifying the certificate -> 1.32s

The "0.10s" is not meaningful. Any running time below 0.10s is rounded
to 0.10s.

Here's another example:
p=7409816651035688885357808120562195190204006291424249054328800652173105144592546051523427394374806971810900275606483718086800588674400571045916946512639482926010704365481217129786242751758369992945635358211430895238352550469050630661 is prime.
[...]
(203 91)
That's just for the top level of the certificate, 2 seconds to
prove and issue, 1 second to verify, for a 232-digit prime.
It'd take too long to manually count up all the times for recursive
certification, but maybe I'll write the code someday soon.
So what's time to prove&issue, and to just verify, an
Atkin-Goldwasser-kilian-morain certificate for that prime?

Certifying p -> 1.73s
Verifying the certificate -> 0.46s

Here's another example:
p=19672623156857094972133172659022419078939060026617767829942707264261372108023395047990287923368939018606654349314262217698164167006662359813971450238106004902179945270732515543635689724286610426195422625824031645989653401861909379797410744021474238350587924893282639226806866312333991764376612244405086003161026928037986491686923688155348179245858095813686270976019037418416994297162434185184491826690636439822874326591141604286940272714002439071101959313983993348023153 is prime.
[...]
(1484 268)
That's nearly 15 seconds to prove primality and generate primitive
element, and just over 2.5 seconds to verify the certificate,
toplevel only again, for 470-digit prime. The next level down would
be each similar to the 232-digit prime earlier, 2 of them, i.e. 2 *
(2secgen 1secver), total for top two levels 19 sec generate and 4.5
second verify. Third level would be 4 copies of the timing for a
100-digit prime, which is very little time. Grand total probably
about 20 seconds to prove primality and generate recursive
certificate, 5 seconds to verify all levels. How does timing of
Atkin-Goldwasser-kilian-morain certificate for that 470-digit prime
compare, for prove&generate, and for verify, separately?

Certifying p -> 27.34s
Verifying the certificate -> 3.87s

All the running times were obtained with an AMD Athlon 3200+.

mm
.

Relevant Pages

  • Re: Unable to use stunnel with tin...
    ... Looks like you got an odd version of stunnel. ... was getting the certificate written correctly. ... Next verify you can connect to the server. ...
    (comp.os.linux.setup)
  • RE: Verifying X509Certificate signature
    ... issue--with that sort of data I know what data to pass to Verify. ... As you said that you want some information about verifying X509 certificate ... Microsoft MSDN Online Support Lead ...
    (microsoft.public.dotnet.framework.aspnet.security)
  • Re: Are ++ and -- operators really more efficient
    ... But you still need a way to verify that it's the right key. ... the signature contains a URL indicating ... where the certificate can be found. ... (This idea that public keys represent principals -- ...
    (comp.lang.c)
  • RE: Verifying X509Certificate signature
    ... I've got that you actually want to verify the signed certificate. ... Joe has mentioned, this is something related to verify the certificate ... cert store to retrieve key info in cert and do some RSA signing and ...
    (microsoft.public.dotnet.framework.aspnet.security)
  • Re: how can we restrict what certificate WSE will use?
    ... > X509SecurityTokenManager to verify the request is from a trusted client. ... > certificate to build a valid signature and encrypted data section. ...
    (microsoft.public.dotnet.framework.webservices.enhancements)