Re: Can someone give me an example of this type of problem?

From: "grouchy" <hennebry@xxxxxxxxxxxxxxxxxxxxx>
Date: 26 Nov 2005 11:04:00 -0800

A certificate for primeness of an odd prime P
could include all the prime factors of P-1
together with the certificates of their primality
together with with an r in 1..P-1 such that
r**k != 1 mod P for any k in 1..P-2 .
The above factors can be used to verify the validity of r.
Finding a certificate for an even
prime is left as an exercise.

.

References:
- Can someone give me an example of this type of problem?
  - From: Nathan Gilbert
- Re: Can someone give me an example of this type of problem?
  - From: Googmeister
- Re: Can someone give me an example of this type of problem?
  - From: jeffrey_h_miller
- Re: Can someone give me an example of this type of problem?
  - From: Nathan Gilbert
- Re: Can someone give me an example of this type of problem?
  - From: tchow
- Re: Can someone give me an example of this type of problem?
  - From: jeffrey_h_miller
- Re: Can someone give me an example of this type of problem?
  - From: stephen
- Re: Can someone give me an example of this type of problem?
  - From: jeffrey_h_miller
- Re: Can someone give me an example of this type of problem?
  - From: stephen

Prev by Date: Re: Text fingerprinting
Next by Date: Re: Text fingerprinting
Previous by thread: Re: Can someone give me an example of this type of problem?
Next by thread: Re: Can someone give me an example of this type of problem?
Index(es):
- Date
- Thread

Relevant Pages

Re: Old question: looking for prime number list > 1,000,000
... > Or you can print a "certificate" of primality. ... See V. Pratt, "Every prime has a succinct certificate", SIAM ... be made contingent solely on the primality or 2,3,5, and 7, again using ...
(sci.math)
Re: Can someone give me an example of this type of problem?
... A similar certificate could exist for the problem ... >>is prime or composite need not actually identify any factors. ... > In the case of primality, the certificate is a solution to the ... I do not know what you mean by 'the "primality relation" ...
(comp.theory)
Re: The time for genertating and testing a prime
... need to test them for primality. ... a source of randomness (which can be very slow, ... prime certificate?) ... $ time openssl genrsa 2048 ...
(sci.crypt)
Re: More primality testing (was: Elementary group theory: Proof of Fermat-Maas ...)
... Did you program the ECPP yourself, ... error or it produces an invalid certificate. ... revolution but, practically, to prove primality it is about as useful as ... That's just over a quarter-second to verify the certificate for the ...
(sci.math)
Re: Is it known whether or not integer factoring is NP-complete?
... > factor between 2 and k, simply exhibit a factor as a certificate. ... Given that primality testing is in P, ... > the prime factorization of P, ...
(comp.theory)