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

Header Data

From: Jim choate <ravage@bga.com>
To: stanton@acm.org
Message Hash: 6799dc2d9a102f48c5a19ddd412b6faefd1c9465098daf9052059cad23ee7294
Message ID: <199406171911.OAA11449@zoom.bga.com>
Reply To: <9406171900.AA20063@sten.lehman.com>
UTC Datetime: 1994-06-17 19:11:41 UTC
Raw Date: Fri, 17 Jun 94 12:11:41 PDT

Raw message

From: Jim choate <ravage@bga.com>
Date: Fri, 17 Jun 94 12:11:41 PDT
To: stanton@acm.org
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <9406171900.AA20063@sten.lehman.com>
Message-ID: <199406171911.OAA11449@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text

> Lets try a game:
> I'm thinking of a number, lets call it my private factor.
> I tell you that it is less than some other number, which we'll call my
> public key.
> For any number you choose, I'll tell you whether your choice is above or
> below my private factor.
> How long will it take you to guess my factor?
> Lets try. my public key is 24.
> Is the factor above 10? No.
> Is the factor above 5? Yes.
> Is the factor above 7? No.
> Is it 6? Yes.
> And look: 24 / 6 = 4 ! You guessed my private key, and you happen to have factored
> my public key at the same time! Wow!
You only found a single set of factors for your public key (ie 3,8 also work)
and if I had asked "is the number 6?" as my first question then I would have 
had it in 1 single guess which does *NOT* qualify as factoring your key.

> You may not think that you are talking about factoring, but factoring is a
> subset of what you are discussing.
the fact it is a subset of what I am talking about means that there are some
issues (and possibly an algorithm or two) that are outside of the purvue of
a discussion limited to simply factoring. The horizon has been expanded.