From: nzook@math.utexas.edu
Date: Mon, 18 Jul 94 12:57:59 PDT
To: cypherpunks@toad.com
Subject: Pseudo-Random Number Generators & _BIG_ Primes
Message-ID: <9407181955.AA00121@vendela.ma.utexas.edu>
MIME-Version: 1.0
Content-Type: text/plain



I've pasted my algebra prelim, so please consider my intuition here as
possibly being above average.

Last week, some posters were talking about using "good" pseudo-random number 
generators for working with big primes.  I would hope that all here are 
aware of the non-recursive and non-algebraic distribution of primes.  It is
my deepest suspicion that in fact primes are strongly non-recursive and
non-algebraic.  That is, I suspect that tests for primeness, and quests
for primitive roots of primes, form a test for randomness whose strength
is directly linked to the length of the prime, possibly in a non-polynomial
fashion.

What I am saying is:  until I see a proof that some pseudo-random code will
in fact work for primality testing (in all cases), or primitive root
searching, I shall hold that {p|p is a "bad" prime} is nonempty.  As a
lemma, I claim that elements of this set are _precisely_ the sorts of primes
that we would wish to use.

$.02

Nathan Zook

When Senator Hatch supports a Clinton nominee great guns from the get-go,
worry.