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. Re:Huh by KingKire64 · · Score: 0, Troll

    So much for comedy!

    you guys need to relax

    --
    "All I can tell the "lesser of two evils" folks is that if they keep voting for evil, they'll keep getting evil."-Lp.org
  2. This is brute force but.... by chairmanKAGA · · Score: 0, Troll

    ...couldn;t you figure out if a number is prime by taking the number you want to see if is prime, start at 2 and muliply that by every number until it is greater than the number you want to see if is prime, if not then go to 3 and repeat until a number * 2 > than your number?

    This isn't elegant but I'm assuming it would work. I'm not a math wiz, only some calculas but could someone tell me why I'm wrong?

    Also, that is in polynomial time I beleive.

    Also, is the product of 2 primes always prime?

    Thanx.

    --
    "Allez Cusine!"
  3. a pedantic ass writes by streetlawyer · · Score: 0, Troll
    It is possible to know that a number is not prime without knowing its factors.

    No it isn't. If you know that X is prime, you know that its factors are 1 and X.

    Yes, I know, I know.

    --


    -- the most controversial site on the Web
  4. Undergraduate Student Project by Anonymous Coward · · Score: 0, Troll

    It turns out that both Kayal and Saxena are undergraduate students, and the result is developed out of their final-year project thesis. When was the last time that a Senior at a US university produced a result of this calibre? Answer: Never been done.

    Computer Science at IIT, Kanpur, incidentally, has traditionally been the most difficult course to gain admission into in the IIT system. About 250,000 applicants write a grueling entrance test (the JEE) to get admission to about 30~40 seats in CS/IITK.

    Finally, a result to make all that selectivity worthwhile.

  5. Er by cca93014 · · Score: 0, Troll

    Is polynomial-time like Hammer-time?

    --

    Invoicing, Time Tracking, Reporting