1994-06-17 - Re: Prime magnitude and keys…a ?

Header Data

From: “Perry E. Metzger” <perry@imsi.com>
To: Jim choate <ravage@bga.com>
Message Hash: 553032cce48dde8f1d0a6304baaa90027c5a5140577afe6cf5187c32bc0258c1
Message ID: <9406171853.AA02690@snark.imsi.com>
Reply To: <199406171830.NAA09354@zoom.bga.com>
UTC Datetime: 1994-06-17 18:53:51 UTC
Raw Date: Fri, 17 Jun 94 11:53:51 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 11:53:51 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171830.NAA09354@zoom.bga.com>
Message-ID: <9406171853.AA02690@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain

Jim choate says:
> > 
> > And you think no one would have noticed such a thing before.
> >
> Is a possibility...especially since I can find no reference to it
> or why it won't work.

You can't find a reference in the library on why you can't build a
machine that cracks DES by repeatedly trying the digitized sound
tracks of porno films, either. Maybe you should try that -- who knows,
it might work.

> > I can pretty much hint to you that such a thing can't really be done
> > in log base 2 of n time in the sense that I believe I can prove that
> >
> This is a joke right? Why in the world should the base have a damn thing
> to do with the algorithm?

Ahem. Perhaps you should have kept awake in school. Log base 2 of a
number just means the number of bits in it.

> > any algorithm that did that would have to involve none of the basic
> > four arithmetic operations on the numbers in question. (Algorithms
> > involving no arithmetic on the numbers are still possible, but
> > intuitively quite unlikely.)
> >
> Sorry, I don't follow your reasoning here at all. Could you clarify?

It is very unlikely to me that you can factor a number in time smaller
than you can square it. Thats the point I'm trying to make. Sorry to
burst your bubble. Oh, I'm sure you'll come back with some silly
comment on "what does squaring the number have to do with anything" or
some similar crud.

> As far as I am concerned if it could be done w/ a neural network,

Oh, god. Neural networks have been invoked. As we know, neural
networks are magical. They are always the answer. After all, we have a
huge number of complex mathematical proofs out there that have been
solved with neural nets -- why, the Reiman Hypothesis was recently
proved by one, wasn't it? Or was that the exact measurement of Dan
Quayle's IQ -- its so easy to confuse them.

I tell you what, Jim. I'll pay you $10,000 if you can come up with an
algorithm that factors numbers or even just breaks RSA in O(log(n))
time or less (where n is the length of the number being factored or
the public key). I'd offer more, but it would be cruel. If you don't
know what the notation O(f(n)) means, please don't come back asking.