| Primality Certificate |
Website Links For Primality |
Information AboutPrimality Certificate |
| CATEGORIES ABOUT PRIMALITY CERTIFICATE | |
| primality tests | |
|
Primality certificates lead directly to proofs that problems such as Primality Testing and the Complement of Integer Factorization lie in NP , the class of problems verifiable in polynomial time given a solution. These problems already trivially lie in Co-NP . This was the first strong evidence that these problems are not NP-complete , since if they were it would imply NP = coNP, a result widely believed to be false. PRATT CERTIFICATES Although not the first primality proof invented, the most famous, called the Pratt certificate, was conceived in 1975 by Vaughan Pratt . This was the first primality proof proven to have polynomial size and to be verifiable in polynomial time. It is based on Lehmer's Theorem , which is essentially the Converse of Fermat's Little Theorem with an added condition to make it true: :Suppose we have an integer ''x'' such that:
:Then, ''n'' is prime. Given such an ''x'' (called a ''witness'') and the prime factorization of ''n'' −1, it's simple to verify the above conditions quickly: we only need to do a linear number of modular exponentiations, since every integer has less prime factors than bits, and each of these can be done by Exponentiation By Squaring in O(log ''n'') multiplications (see Big-O Notation ). Even with grade-school integer multiplication, this is only O((log ''n'')4) time. However, it is possible to trick a verifier into accepting a composite number by giving it a "prime factorization" of ''n'' −1 that includes composite numbers. For example, suppose we claim that 85 is prime, supplying ''x''=4 and 84=6×14 as the "prime factorization" of ''n'' −1. Then:
We would falsely conclude that 85 is prime. We don't want to just force the verifier to factor the number, because there is no known general polynomial-time factoring algorithm. A better way to avoid this issue is to give primality certificates for each of the prime factors of ''n'' −1 as well, which are just smaller instances of the original problem. We continue recursively in this manner until we reach a number known to be prime, such as 2. We end up with a tree of prime numbers, each associated with a witness ''x''. For example, here is a complete Pratt certificate for the number 229:
Note that the product of the numbers at each level of the tree is at most the original number, so the total size of each level is linear. The number of levels is logarithmic, since ''n'' −1 is divisible by 2 for all odd primes. Together these observations can be used to show that the verification requires no more time than O(log ''n'') top-level verifications: the total time is O((log ''n'')5), which is quite feasible for numbers in the range that computational number theorists usually work with. However, while useful in theory and easy to verify, actually generating a Pratt certificate for ''n'' requires factoring ''n'' −1 and other potentially large numbers. This is simple for some special numbers such as Fermat Primes , but currently much more difficult than simple primality testing for large primes of general form. For larger numbers, an easier-to-generate primality certificate such as the Atkin-Goldwasser-Kilian-Morain certificate may be preferred. ATKIN-GOLDWASSER-KILIAN-MORAIN CERTIFICATES Write me --> REFERENCES |
|
|