[Tutor] pickle problems

[Dave Angel]

On 08/23/2012 04:43 AM, Steven D'Aprano wrote:
> On Wed, Aug 22, 2012 at 11:39:46PM -0400, Dave Angel wrote:
>> On 08/22/2012 07:32 PM, Richard D. Moores wrote:
>>> <snip>
>>>
>>> My code uses gmpy2.is_prime()  (lines 79 and 89). is_prime() is VERY fast.
>> You do know that this gmpy2 function is only statistically correct ?  it
>> can false positive.  I don't know what the probs are, but it uses
>> Miller-Rabin, with a default factor of 25.
> What Dave means is:
>
> - If gmpy2.is_prime says a number is not prime, then that is 
>   certainly true;
>
> - but if it says that a number is prime, then that is only 
>   probably true.
>
> With 25 Miller-Rabin tests, the probability of a false positive is (if I 
> remember correctly) 1 time in 4**25 or about 1 time in a million 
> billion. (That's American billion, 10**9, not old-style English 
> billion.) If you tested a thousand prime numbers a second for thirty 
> thousand years, you would expect perhaps one false positive.
>
> The odds are much higher that a hardware fault or stray cosmic ray 
> hitting the CPU or memory chip will cause the computer to calculate the 
> wrong answer.
>

I knew of the Miller Rabin test, but I did not know the probabilities
involved. I'm a little surprised I didn't see any docs on the gmpy2 site
that gave such probabilities.  it defaults to 25, without explaining how
that number relates to anything in the wikipedia article.  
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Does anyone know if the gmp2 code is testing the sequence described in
wikipedia, where a is  2, 3, 5, 7, 11, 13, and 17 ?   If that relates
directly, it would seem that 7 tests would give 100% confidence for n up
to 14+ digits.



-- 

DaveA