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

1 of 436 comments (clear)

  1. bad in math? by RelliK · · Score: 2, Redundant

    log2(16) = 4
    log2(32) = 5
    log2(64) = 6
    log2(128) = 7
    log2(256) = 8

    by your assumption a*log2(16)^12 + b = 1 ms
    for simplicity, let's ignore the constant b.
    then:

    a*log2(16)^12 = a * 4^12 = 1 ms (by assumption)
    a*log2(32)^12 = a * 5^12 = 14.5 ms
    a*log2(64)^12 = a * 6^12 = 129.75 ms
    ...
    a*log2(256)^12 = a * 8^12 = 4096 ms

    --
    ___
    If you think big enough, you'll never have to do it.