Re: Fate of Ecash if RSA is cracked?

At 8:01 AM 6/3/96, Perry E. Metzger wrote:
>Dr. Dimitri Vulis writes:
....
>> This'll happen, probably sooner than later.
>
>Why do you assume that? There are plenty of problems that are
>provably not solvable in non-exponential time even if P=NP. What makes
>you think this one is going to be solved?
>
>.pm

The "Idea Futures" forum has established odds on this. The current odds are
currently 60% that a 1024 bit number will be factored by 2010 and 30% that
a 512 bit number will be factored by 1997.

See <http://if.arc.ab.ca/IF.shtml> for Idea Futures and
<http://if.arc.ab.ca/bin/summary> for odds for various questions.

Norman Hardy writes:
> At 8:01 AM 6/3/96, Perry E. Metzger wrote:
> >Dr. Dimitri Vulis writes:
> ....
> >> This'll happen, probably sooner than later.
> >
> >Why do you assume that? There are plenty of problems that are
> >provably not solvable in non-exponential time even if P=NP. What makes
> >you think this one is going to be solved?
> 
> The "Idea Futures" forum has established odds on this. The current odds are
> currently 60% that a 1024 bit number will be factored by 2010 and 30% that
> a 512 bit number will be factored by 1997.

Thats totally different from a high speed polynomial time factoring
algorithm. Thats saying we can factor bigger numbers with
time. Exponential growth still holds, however.

.pm

On Mon, 3 Jun 1996, Norman Hardy wrote:

> At 8:01 AM 6/3/96, Perry E. Metzger wrote:
> >Dr. Dimitri Vulis writes:
> ....
> >> This'll happen, probably sooner than later.
> >
> >Why do you assume that? There are plenty of problems that are
> >provably not solvable in non-exponential time even if P=NP. What makes
> >you think this one is going to be solved?
> >
> >.pm
> 
> The "Idea Futures" forum has established odds on this. The current odds are
> currently 60% that a 1024 bit number will be factored by 2010 and 30% that
> a 512 bit number will be factored by 1997.
> 

True, but by that time I'll be able to use 2048 or bigger keys with the same
or better performance as 1024 bit keys now.  As long as factoring is
exponential, you can always make it impossible to factor your keys. 
And I think it will always be exponential.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Jeremey Barrett
Senior Software Engineer			jeremey@forequest.com 
The ForeQuest Company       			http://www.forequest.com/

   "less is more."
		-- Mies van de Rohe.

   Ken Thompson has an automobile which he helped design.  Unlike most
   automobiles, it has neither speedometer, nor gas gage, nor any of the
   numerous idiot lights which plague the modern driver.  Rather, if the
   driver makes any mistake, a giant "?" lights up in the center of the
   dashboard.  "The experienced driver", he says, "will usually know
   what's wrong."

		-- 'fortune` output

Jeremey Barrett wrote:
> > The "Idea Futures" forum has established odds on this. The current odds are
> > currently 60% that a 1024 bit number will be factored by 2010 and 30% that
> > a 512 bit number will be factored by 1997.
> > 
> 
> True, but by that time I'll be able to use 2048 or bigger keys with the same
> or better performance as 1024 bit keys now.  As long as factoring is
> exponential, you can always make it impossible to factor your keys. 
> And I think it will always be exponential.

Actually factoring is not exponential even now. For Number Fiels Sieve 
method the number of operations is estimated as

N ~= exp(((1.923+O(1)) * (ln n)^(1/3) * ln ln n)^(2/3))

(taken from Schneier, A.C., page 256)

	- Igor.

Igor Chudov @ home writes:
> Actually factoring is not exponential even now. For Number Fiels Sieve 
> method the number of operations is estimated as
> 
> N ~= exp(((1.923+O(1)) * (ln n)^(1/3) * ln ln n)^(2/3))
> 
> (taken from Schneier, A.C., page 256)

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.

.pm