So this means that most primes are 'dangerous', in the sense that if you get 1 bit wrong, it is not a prime, and in fact, may be quite composite. Soooo.... Are there primes which _incorporate_ their error-correcting code into their own bit-string ? I.e., these primes don't need a separate set of error-detecting/correcting bits. BTW, I was thinking of primes over the usual integers represented in base 2. But I guess this wouldn't be possible for prime polynomials over GF(2)... At 11:34 AM 3/29/2013, Warren D Smith wrote:

...

Charles Greathouse points out paper by T.Tao...

--oh, great, scooped by Terry Tao. Terence Tao: A remark on primality testing and decimal expansions, J.Australian Math'l. Soc. 91,3 (2011) 405-413. http://arxiv.org/abs/0802.3361