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

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.

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.

ReplyDeleteFor 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.

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.

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

ReplyDeleteOddly 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 togetherIs that easy to see? Sorry if it is a stupid question.

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.

ReplyDeletePerhaps 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.

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

ReplyDeleteUse 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.

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.

ReplyDeleteThis is probably FAR too much to hope for!

One correction:

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

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(Actually, for crypto applications, we'd likely just keep using Miller-Rabin.)

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

ReplyDeleteFor 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.

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.

ReplyDeleteAnon 3.

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).

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

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"A deterministic algorithm exists if you either believe in full derandomization or in conjectures on distributions of primes."

ReplyDeleteDear 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?

"If you you either believe in full derandomization"

ReplyDeleteI 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

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

ReplyDelete