Newsgroups: sci.crypt.research
+     convex!!!!
From: (Don Beaver)

Subject: Re: A cryptographic pseudorandom number generator
Message-ID: <1995Mar26.174936.26230@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: (sci.crypt.research co-moderator)
Organization: Penn State Computer Science
Date: Sun, 26 Mar 1995 17:49:36 GMT
Lines: 58

Benjamin Cox  writes:
> (Don Beaver) writes:
>> In fact, it is theoretically trivial to factor N when N is no bigger
>> than 2^1000000000000000.
>Would you care to explain this assertion?

Here's a polynomial-time algorithm that manages to factor N when N
is no bigger than 2^1000000000000000:

1.  If N>2^1000000000000000, then output 0.   // Yes, this is wrong!
2.  Otherwise, for i = 1..2^1000000000000000, check whether i divides N.
    If so, append i to the output, set N = N/i, and continue.

Theoretical Analysis

Correctness:  Always correct for N <= 2^1000000000000000.
              Always wrong for larger N.  (But we don't care.)

Running Time:

Size of input, n         Running Time, t(n)
----------------         ------------------
1                        t(1) <= 2^1000000000000000 * 10^45
2                        t(2) <= 2^1000000000000000 * 10^45
1000000000000000         t(1000000000000000) <= 2^1000000000000000 * 10^45
1000000000000001         t(1000000000000001) = 1
1000000000000002         t(1000000000000002) = 1
1000000000000003         t(1000000000000003) = 1
any n>1000000000000000   t(n) = 1.

Since t(n) = O(1), the algorithm is polynomial-time.

Is complexity theory helpful in this case?  You bet it isn't!

That was the point that I was trying to make earlier: the
complexity-theoretic results can't be used to say that lg(512)-bit
windows of a BBS generator are secure.

Sure, the theoretical proofs might lend some support to a
*superstitious* belief.  And we might *hope* that it's safe to form
such beliefs, even when they are logically unfounded.  But we might
just be unlucky.  We might have overlooked that the theoretical proof
said, "For N larger than 2^2^2^2^1000...", or that it is difficult to
find out precisely how big N must be for an *eventually-true* property
to start holding.

And cryptography is exactly the place that such unluck and oversight
can lead to holes...