Too bad, the paper has been withdrawn due to a mistake :-/
This result has caused quite a lot of excitement in number theory (see the articles in [Quanta Magazine] and [Nature News]).
It turns out that the last digits of consecutive primes are not uniformly distributed but rather tend to be anti-correlated. For example, in base 10 the last digit of
I can only quote Derrick Stolee: 'Terry Tao just dropped a bomb'. :)
The basic idea of this paper is to test whether the decimal digits of three special constants $(\pi,e,\sqrt2)$ act as though chosen from a uniform distribution, based on their first ten million digits. In particular the author studies the sum of the digits compared to the expected behavior by the la
This paper seems pretty interesting, really. (In how it would relate to the algorithm of Shor). Does anyone know more about this work? Is it possible to improve the restriction on the characteristic size? Is that even an important restriction?
Thanks Anthony and Juan.
There's another blog post on this here: http://ellipticnews.wordpress.com/2013/06/21/quasi-polynomial-time-algorithm-for-discrete-logarithm-in-finite-fields-of-smallmedium-characteristic/.
@Noon Silk. I do not know what to say about heuristic 3, but, in relation to your first question, let's assume that all heuristics are valid and apply theorem 2 to solve the Discrete Logarithm over Z_q*, where q is prime. As far as I understood (someone please correct me if I am wrong) the algorithm
There was a discussion about a previous paper of Joux (with a weaker result) on this blog post:
And here is a question on cstheory.SE about this paper: http://cstheory.stackexchange.com/q/18134/1542