polynomial time test for primality

[grobyccil]

A team from INDIAN INSTITUTE OF TECHNOLOGY KANPUR found a polynomial time test for primality.
Read the full article on http://www.cse.iitk.ac.in/news/primality.html

I think this result will change the cryptography field in the next years.

And now... bigger keys?

[proactive]

That's a job well done! But from what I read on the scientists' homepage it's not gonna revolutionize cryptography yet... Even though the new method is faster than any old method, it's still slow when dealing with large numbers.

BTW, I don't know the details, but somehow you'll need a large prime number when you deal with cryptography. But because large prime numbers are hard to find, encryption algorithms use numbers they believe are prime, but may not be. That can cause a potential security flaw. ....From what I've heard.

Perhaps someone got more details?

[evilempire]

i read it a week or more ago so sorry if i mixed it up, but i recall it being slower

the reason its important was because it can tell if a number is prime with 100% certainty

[grobyccil]

about speed...
That's rigth evilempire!
The probabilistic method is faster yet, but the complexity of this one is polynomial and is deterministic.

[Terr]

The new algorithm has no immediate applications, since existing ones are faster and their error probability can be made so small that it is practically zero. Still, for mathematicians and computer scientists, the new algorithm represents a great achievement because, they said, it simply and elegantly solves a problem that has challenged many of the best minds in the field for decades.

So it probably won't revolutionize crypto by itself, given the speed issues inherent in the business, but it may lead to faster factoring. Hmm. Well, it's nice to remember that we can always fall back on quantum-based encryption (which will probably be as hard to break with quantum methods as it is to break current encryption with current methods...)

But if their find is really mathematically groundbreaking, more power to them. Primes are pretty dang cool.

[ruffo]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=#post) by grobyccil
about speed...
That's rigth evilempire!
The probabilistic method is faster yet, but the complexity of this one is polynomial and is deterministic.

That's true. And IMHO we will continue to use probabilistic method.

I briefly explain why

Let's talk about probability.
In [0-n] range there are about n/log(n) primes.

So the probability to find a prime for a random input is about 1/log(n).
That means, for an average-but-still-computable number 1/500.

The idea is to take some (in fact a lot) of random (pseudo random, you know...) number, and test for their primality. That would be a long task, if math wouldn't help us, since the input number are BIG (>512 bits, think 2^512).

Now we THOUGHT that factorize a number is an NP problem. Indians discovered it's in P.

By the way, using a math trick, (miller-rabin probabilistic primality test) we can check for primality in O(k*log(n)), where k means how many times we want to check that number.
(we must to check it several times because some numbers fail this test)
(search for miller rabin to know more. Google knows it :)

Now we can simplify it for a large n as O(log(n)).

Sweet and kick-ass complexity, huh?

Brilliant discover by the way. One step closer to P=NP? (hell, i'm just joking :P)

[nabylbt]

There are 2kinds of cryptosystems: symmetric and asymmetric.
Symmetric cryptosystems use the same key (the secret key) to encrypt and decrypt a message.... and asymmetric cryptosystems use one key (the public key) to encrpt a message and a different key (the private key) to decrypt it...

because of the complexity of keeping the symetric key secret, the asymetric system is used as defined in RSA: http://www.rsasecurity.com/rsalabs/faq/
the RSA is used in BGP or other system publicly available .....
Even if p=np is true, the equivalence relation used is not meaningful enough enough to shorten the computation time enough. a polynomial of deg. 20 would still be impractical to use ....the slight difference of language used in the defs are polynomial time "tractable" and exp time "intractable" is just way far too slight....
Don't forget that the number used are just relatively prime to each other....

anyways check out this web site for further explanations on the topic it is very well explained in detail:
http://www.momentus.com.br/PGP/doc/howpgp.html