Discrete Logarithm in Polynomial Time

[Enthalpy]

You thought it was difficult? They did it...

In a set of p*q elements, which is not a field, and where the prime p and q are chosen big (like 500 bits), computing a^x is quick, but the reverse operation called discrete logarithm is long - that is, no quick method was known. So much that some methods for computer security rely on that, for instance some passports.
http://en.wikipedia.org/wiki/Discrete_logarithm

That was before. On May 12 at Eurocrypt 2014, Razvan Barbulescu and his mates have described a method in quasi-polynomial time:
http://ec14.compute.dtu.dk/program.html
they claim as an example that number sizes that would have needed 2¹²⁸ operations to crack go in 2⁶⁰

http://www.lemonde.fr/sciences/article/2014/05/13/une-percee-en-mathematique-rend-caduques-des-procedures-de-chiffrement_4415604_1650684.html

(sorry for ze lãnguage, other reports must exist)

Papers, possibly this most recent method: http://arxiv.org/abs/1306.4244

and http://cca.saclay.inria.fr/Data/Razvan.Barbulescu-10-01-2014.pdf

It all depends on the number sizes and the difficulty of individual operations. 2⁵⁶ simpler operations were made decades ago by EFF to crack DES. How small are the numbers chosen in existing applications? It's about time to double-check and take safety factors, or better, change the encryption method, because smaller improvements use to follow any breakthrough.

Even more disturbing: the discrete logarithm is known to be related with the factorization (finding p and q above), that is, cracking one would help crack the other.
http://en.wikipedia.org/wiki/Integer_factorization
If someone finds a practical path in that direction (the other, factoring eases logarithm, is simple), that would ruin all the algorithms we have now.
[A simple introduction is: Applied Cryptography, by Bruce Schneier]
All the public-key cryptography, which exchanges the keys for the simpler private-key ciphers in all working programmes, and authenticates messages or signs software, relies on the difficulty of factoring.