Slashdot Mirror

← Back to Stories (view on slashdot.org)

Turns out, Primes are in P

Posted by chrisd on from the cats-and-dogs-living-together dept.

zorba1 writes "Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem."

5 of 436 comments (clear)

  1. What is 'x' and how is 'q' calculated? by Mr.+Sketch · · Score: 4, Interesting

    From looking at the algo, I can't figure out what 'x' (or maybe it's a chi) is? Can someone help? I've looked it over, but couldn't find a definition of it. I'm also assuming that the 'if (r is prime)' line is a recursive call to itself? Also, how do we determine 'q' the 'largest prime factor of r-1' ? Another recursive call to get the factors? I must admit, I'm kind of lost by the algo, but it's still interesting.

    --
    Things you think are in the Constitution, but are not.
  2. I'm dead tired by Henry+V+.009 · · Score: 3, Interesting

    I'm dead tired and will look at the paper in the morning. But right now I have a problem with step 6:
    "Let q be the largest prime factor of r-1"
    Won't getting q boost the thing back into power n complexity?

  3. Re:p=np? by Vengie · · Score: 3, Interesting

    3-sat isnt it 3-cnf-sat? or is cnf typically dropped?

    --
    When in doubt, parenthesize. At the very least it will let some poor schmuck bounce on the % key in vi. (Larry Wall)
  4. O(num_bits**12) time estimates by Adam+J.+Richter · · Score: 5, Interesting

    We give a deterministic O((log n)**12) time algorithm for testing whether a number is prime.

    [Sorry, the Slashdot filter does not allow me to superscript the 12.]

    The algorithm takes O(log2(n)**12) time, where n is number being factored. If we optimistically assume that this algorithm can test the primality of a 16-bit number in one microsecond, then here is how long it would take to test time primality of some larger numbers.

    • 2**12 times as long for a 32-bit number = 4096 microseconds = 4 milliseconds,
    • 4**12 times as long for a 64-bit number = 16,777,216 microseconds = 16 seconds,
    • 8**12 times as long for a 128-bit number = 68,719,476,736 microseconds = 68,719 seconds = 19 hours,
    • 16**12 times as long for a 256-bit number = 281,474,976,710,656 microseconds = 9 years.

    I don't know what a realistic base time for this algorithm really would be, and I don't know where the cross over point against existing exponential time deterministic primality testing algorithms would be, but at least this provide a sense of how log2(n)**12 grows.

  5. Re:Big consequences related to encryption by fatphil · · Score: 3, Interesting

    The PRP tests used to check numbers for compositeness or probable primality
    actually test to see if this exponentiation procedure works.

    RSA does work with carmichael numbers instead of primes, for example, because

    a^c == a (mod c) for all a s.t. (a,c)==1, c a carmichael number

    Try it - it works!

    Phil

    --
    Also FatPhil on SoylentNews, id 863