FOM: Probabilistic proofs

[Stephen Cook]

Joe Shipman just wrote

	   If we are to get
	 "reproducibility" we must use either previously published tables of
	 physically generated random bits or deterministic pseudo-random number
	 generators; I claim that the first choice ought to allow us to give th
	e
	 probabilistic proof the same kind of status a computer-aided proof has
	 now.

An adversarial mathematician might study a previously published table of
physically generated random bits and use it  to devise an input for which the
probabilistic algorithm gives a wrong answer, and hence publish a "proof"
of a false theorem.   This may not be possible in the case of Rabin's test,
but should be quite possible in the case of Schwartz' test. (Find nonsingular
matrix of polynomials which is singular for all integer values given by the
random bits on the part of the table used.)

Steve Cook