It should be at most 1/4 of the bases 'a' fail to prove that a given

number n is composite, so 3/4 of them should prove compositeness,

assuming n is actually composite.

The actual name of the test is the "Miller-Rabin psuedoprimality test"

see http://www.cacr.math.uwaterloo.ca/hac/

Here, you can download the "Handbook of Applied Cryptography" - see

Chap. 4, which refers to choosing public key parameters - i.e. finding

numbers which are prime. I find this entire book to be an excellent

reference - it gives clear description and algorithms, and also gives

plenty of good references.

Jonathan A. Zylstra

jzylst01@...

On Tue, 29 Apr 2003, Jon Perry wrote:

> 'It has been proven ([Monier80] and [Rabin80]) that the strong probable

> primality test is wrong no more than 1/4th of the time (3 out of 4 numbers

> which pass it will be prime). '

>

> From:

>

> http://www.utm.edu/research/primes/prove/prove2_3.html

>

> How does this work, surely I can create a list of n for which it fails...

>

> Jon Perry

> perry@...

> http://www.users.globalnet.co.uk/~perry/maths/

> http://www.users.globalnet.co.uk/~perry/DIVMenu/

> BrainBench MVP for HTML and JavaScript

> http://www.brainbench.com

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

>

>