From: Robin Chapman Subject: Re: Factorization Date: Sun, 20 Jun 1999 07:32:30 GMT Newsgroups: sci.math Keywords: Integer factorization is in class NP In article , sarafat@yahoo.com (Shymaa) wrote: > > I know that factorization is not in P and not proven to be NP Hard, > but is it known to be in NP or not? > Presumably factorization means factorization of an integer into primes. This is news to me. I never knew that factorization wasn't in P. But it is in NP. They key to this is that there is always a concise certificate for a number being prime. To certify an odd number p as prime, all one needs to do is to give an integer a such that a^{p-1} = 1 (mod p) but a^{(p-1)/q} <> 1 (mod p) for all prime factors q of p-1. Of course one needs the factorization of p-1 into primes for this, and one needs to certify the primes involved here too and so on. But at each stage, the primes involved decrease by a factor of at least 2 and we only need O(log p) recursive steps. The size of the certificate will be polynomial in log p, as will the time needed to verify it. There are variants of this scheme: e.g. replacing p-1 by p+1 or by using groups of points on elliptic curves. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "They did not have proper palms at home in Exeter." Peter Carey, _Oscar and Lucinda_ Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: Terry Boon Subject: Re: COMPOSITES belong to co-NP? Date: Mon, 1 Nov 1999 22:35:53 +0100 Newsgroups: sci.math,sci.crypt William Rowden wrote: > Here is a question from someone completely new to complexity theory > and number theory: > What "certificate" would allow one to verify primality in polynomial > time? I believe this is known as Pratt's Theorem. Fermat's Little Theorem ======================= For any natural number n if there exists b such that b^(n-1) = 1 mod n b^d != 1 mod n for any proper divisor d of n-1 then n is prime. Certificate for the primality of n ================================== 1) A number b such that b^(n-1) = 1 mod n b^d != 1 mod n for any proper divisor d of n-1 2) The prime factorisation of n-1 = (p_1^e_1)...(p_k^e_k) 3) Certificates that p_1, ..., p_k are prime. (Yes, it's a recursive definition -- but it costs us nothing to say that we can recognise 2 as prime without a certificate, and that ensures the recursion "bottoms out".) Verification of the certificate =============================== 1) Check b^(n-1) = 1 mod n 2) Check b^d != 1 mod n for any divisor d of n-1 If these conditions are met, then we have shown (by Fermat) that n is prime. It remains to show that this verification can be done in polynomial time. (1) is easy; the approach to (2) is as follows: 1) Verify that the certificate's factorisation of n-1 does give n-1. 2) Verify that p_1, ..., p_k are prime (using the certificates bundled as the certificate of n's primality). 3) Check that b^((n-1)/p_i) != 1 mod n, for i=1..k. (We don't check every proper divisor individually -- this is sufficient.) Although one might worry about the extra verifications of p_1,.., p_k taking too long, they don't (shown by induction). (In fact, the whole verification takes, IIRC, linear time.) Best wishes, Terry Boon [trailer deleted --djr] ============================================================================== From: Anton Stiglic Subject: Re: COMPOSITES belong to co-NP? Date: Mon, 01 Nov 1999 17:35:27 -0500 Newsgroups: sci.math,sci.crypt William Rowden wrote: > Here is a question from someone completely new to complexity theory > and number theory: > > What "certificate" would allow one to verify primality in polynomial > time? It is obvious to me that the composite decision problem ("Is n > composite?") belongs to NP, because one could produce as a certificate > an integer b such that b|n (b divides n). The reverse is not clear to > me: what information would permit verifying that the answer to "Is n > composite?" is NO? > Look at section 4.3 of the Big Green book for some algos and theorems. To understand how this pertains to complexity, let me try to explain: To prove that p is prime, we can use the following theorem: p is prime if and only if there exists an integer a satisfying (i) a^{p-1} = 1 mod p and (ii) a^{p-1}/1 != 1 mod n, for each prime q such that q | p-1. Now, an all powerfull proover P could factor p-1, and give this in the certificat, but then he must also proove that the q's that divide p-1 are in fact prime, and that he has all of them. To to this, he gives q1, q2, ..., qn such that p-1 = q1q2 ... qn (this can be verified in poly time) and prooves that the qi's are infact prime. He prooves that each qi is prime by using the same method, until he comes down to primes for which prooving they are primes can efficiently be done by just trying to divide it by each number smaller then it (or something like that). A time complexity study of this can proove that all this can be done in Poly of lg(p) time. There is actually a good little article explaining all of this, I could give you the ref tomorow. Anton ============================================================================== From: juola@mathcs.duq.edu (Patrick Juola) Subject: Re: COMPOSITES belong to co-NP? Date: 2 Nov 1999 10:15:19 -0500 Newsgroups: sci.math,sci.crypt In article <7vkqad$2na$1@eskinews.eskimo.com>, William Rowden wrote: >Here is a question from someone completely new to complexity theory >and number theory: > >What "certificate" would allow one to verify primality in polynomial >time? It is obvious to me that the composite decision problem ("Is n >composite?") belongs to NP, because one could produce as a certificate >an integer b such that b|n (b divides n). The reverse is not clear to >me: what information would permit verifying that the answer to "Is n >composite?" is NO? I don't have the exact information to hand, but I have a reference where you can find it out.... Pratt, V (1975), "Every prime has a succinct certificate," SIAM J. Comput. 4 (214-220). This is a formal proof, not merely a probabilistic statement, that a given number is a prime. -kitten