Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Finding Primes

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 4, 2009
    • 0 Attachment
      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.



      --
      Posted By Lance to Computational Complexity at 8/04/2009 06:00:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.