1994-07-18 - Pseudo-Random Number Generators & BIG Primes

Header Data

From: nzook@math.utexas.edu
To: cypherpunks@toad.com
Message Hash: 40fcfcbfe553f0235cc639a72b2d36a54fa0b8805734460b63004f31a0ae734b
Message ID: <9407181955.AA00121@vendela.ma.utexas.edu>
Reply To: N/A
UTC Datetime: 1994-07-18 19:57:59 UTC
Raw Date: Mon, 18 Jul 94 12:57:59 PDT

Raw message

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

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.


Nathan Zook

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