Tuesday, August 04, 2009

Finding Primes

The newest polymath project Finding Primes asks a question that ties together number theory and computation: Given a number n find any prime p>n deterministically in time polynomial in the length of the binary representation of n (about log n).

This problem came into vogue shortly after the AKS Primality algorithm put checking primes in deterministic polynomial time. A deterministic algorithm exists if you either believe in full derandomization or in conjectures on distributions of primes. The following algorithm will likely run in polynomial time.
while(not prime(n)) {n++}
output n
Many cryptographic protocols require finding prime numbers to multiply together to get hard-to-factor composites. By the prime number theorem, picking numbers of k bits at random will find a prime in O(k) tries with high probability and one could then run the Solovay-Strassen or Miller-Rabin primality tests.

Those tests would never give you absolute evidence that you found a prime. Goldwasser and Kilian gave a procedure for finding primes with a certificate of primality. The AKS algorithm eliminates the need for a certificate.

Oddly enough we would usually prefer a probabilistic over the deterministic method to find primes. Otherwise the adversary can use the same deterministic procedure and factor your number as easily as you put it together.

17 comments:

  1. There's another motivation to deterministically find large primes: such primes need to be generated to run deterministic algorithms that perform field operations over large fields.

    For example, there have been some extractor algorithms that involve treating the input as elements in a prime field and then doing some field operations with them. To make such an algorithm truly explicit, one needs to be able to generate a large enough prime deterministically.

    ReplyDelete
  2. I have a basic question about this polymath stuff. If someone not participating in the discussion comes up with a solution, would his or her credi be diminished by the suspicion that he/she somehow benefitted from the discussions, even though this might not be the case. I believe that someone not participating in such a project is under no obligation to quote or cite any unpublished but new fact unearthed during the discussions. But of course for some one participating in the project, not doing so would be dishonest. Does one need to register somewhere in order to view the postings ? Even if this is the case, I am afraid because of seepage in a large community, facts unearthed but unpublished would become known as "common knowledge" -- and this would be to the detriment of individual researchers thinking about the same questions.

    Have these questions been raised already in some forum ? The seem to be natural concerns.

    ReplyDelete
  3. Oddly enough we would usually prefer a probabilistic over the deterministic method to find primes. Otherwise the adversary can use the same deterministic procedure and factor your number as easily as you put it together

    Is that easy to see? Sorry if it is a stupid question.

    ReplyDelete
  4. Anon 3: Suppose Alice use a deterministic prime finding algorithm to find two primes p and q at least 2^500 and multiply then together to get n=pq to use in say RSA. Eve could use the same algorithm, get the same p and q and decode messages at will.

    ReplyDelete
  5. Perhaps the ideal situation would be some sort of (family of) deterministic maps which could take a random seed as input and output a prime which is approximately uniform on some interval.

    ReplyDelete
  6. Anon 5, we already know how to do this, if I understand your comment correctly.

    Use random bits to pick a random number from the interval, and check if the number is prime or not and repeat until you find a prime. The primes are dense enough that you will find a prime quickly with high probability.

    If you really want to be stingy about the randomness, after you pick the first number uniformly at random, you can recycle the randomness using extractors so that you don't really need to add much more randomness to get a new uniform sample.

    Since the primes have relatively high density in intervals, you cannot get a much more efficient solution (in terms of randomness used), than the one above.

    ReplyDelete
  7. I guess what I mean is an explicit function f_N such that for every integer x in [N, 2N] f_N(x) is a prime in [N, 2N], and for every prime p in [N, 2N] there are approximately N/log(N) integers such that f_N(x)=p.

    This is probably FAR too much to hope for!

    ReplyDelete
  8. One correction:

    The should be about "Log(n)" integers, not "N/Log(n)".

    ReplyDelete
  9. Lance: For crypto applications, we'd just move the randomness elsewhere; i.e., Alice would pick two primes at least 2^500 + x, where x is some "random" 490-bit number.

    ReplyDelete
  10. (Actually, for crypto applications, we'd likely just keep using Miller-Rabin.)

    ReplyDelete
  11. Deterministic prime generation is not very useful for most crypto, but not for the reason you suggest.

    For DLOG type systems (e.g. ElGamal variants that are widely used), deterministic prime generation is fine. The issue is that a random prime is likely "better," in terms of producing a hard instance of the problem you're dealing with.

    ReplyDelete
  12. Ok I misunderstood and thought that if there is a deterministic algo to find prime then factoring is easy. I guess any such result is not known.

    Anon 3.

    ReplyDelete
  13. The last two sentences are misleading. The algorithm to find a prime, given an input, is deterministic. The inputs need not be generated deterministically. The whole point of crypt is to choose inputs that the adversary would have little chance in guessing (or finding given certain information).

    On a related note, Hendrik Lenstra gives a great talk on the difference between testing for primality and factoring for both integers and polynomials.

    ReplyDelete
  14. In terms of practical efficiency I recall that the superpolynomial algorithm of Cohen and Lenstra used only 4 Rabin-Miller tests because they weeded out most composites the expected benefit of additional R-M tests was so small relative to the superpolynomial part which involved the hard-coded products of the first n primes...

    ReplyDelete
  15. "A deterministic algorithm exists if you either believe in full derandomization or in conjectures on distributions of primes."

    Dear Lance, what do you mean by "full derandomization"? Is there a conjecture (no matter how bold; but not obviously false) regarding derandomization that will imply that there is a deterministic algorithm to find large primes?

    ReplyDelete
  16. "If you you either believe in full derandomization"

    I do not think there is a formal way to define "full derandomization" (and certainly I have no idea how to do it) but it can refer to a meta conjecture that every randomized construction/algorithm related to "interesting" mathematics can be replaced by a deterministic constriction/algorithm (with a polynomial overhead).

    In this particular case "derandomization" essentially refer to "random-like" properties of the primes

    ReplyDelete
  17. I added a link to a 2006 post on full derandomization.

    ReplyDelete