"Perry E. Metzger" <perry@piermont.com>:

Igor Chudov @ home:

...

Actually factoring is not exponential even now. [... est.:] N ~= exp(((1.923+O(1)) * (ln n)^(1/3) * ln ln n)^(2/3))

The distinction between that and exponential is rather difficult for most ordinary people to see, and in any case subexponential and exponential are "practically the same" for purposes of this discussion.

When discussing the estimated time needed for factoring integers, it is usually assumed that an "algorithm" is something that is deterministic or probabilistic. Quantum computing should also be mentioned. Efficient algorithms for logarithms (the Diffie-Hellmann- problem) and factoring (the RSA-problem) on a quantum computer were found by Peter Shor [1]. Of course, no quantum computing device that you could run those "programs" on does exist. But as Gilles Brassard puts it, "In my opinion, the theoretical notion of feasible computation should be modelled on our understanding of the physical world, not on our technological abilities. After all, the classical Turing machine itself is an idealization that cannot be built in practice even not taking account of the unbounded tape: any real implmentation of a Turing machine would have nonzero probability of making a mistake. Does this discredit the model? I think not." [2] An other article by Brassard might still be availabe at <URL:http://www.rsa.com/rsalabs/cryptobytes/spring95/brassard.htm>. There, he writes quite optimistically: "I like to think that I shall see a special-purpose quantum factorization device in my lifetime." [1] Peter W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring (in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 116-134) [2] Gilles Brassard, A Quantum Jump in Computer Science (in: Computer Science Today (Springer-Verlag LNCS 1000), 1995, pp. 1-14)