Re: [PrimeNumbers] SPRP
- The statement on the web site is unclear ...
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"
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
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). '
> How does this work, surely I can create a list of n for which it fails...
> Jon Perry
> Unsubscribe by an email to: email@example.com
> The Prime Pages : http://www.primepages.org/
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/