From: Bodo_Moeller@public.uni-hamburg.de (Bodo Moeller)
Date: Thu, 6 Jun 1996 16:04:25 +0800
To: cypherpunks@toad.com
Subject: Re: Fate of Ecash if RSA is cracked?
Message-ID: <m0uRIwy-0000AJC@ulf.mali.sub.org>
MIME-Version: 1.0
Content-Type: text/plain


"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)