[Edu-sig] Miller-Rabin (first draft, slow)

[Tim Peters]

[posted & mailed]

[Kirby Urner, with a supernaturally slow Miller-Rabin program]

Haven't had time to look at this in detail, but two things you need to pick
up if you're going to sling bigints in Python:

1)     1L << N
   computes the same result as
       2L ** N
   (for int N >= 0) but shifting is much faster than exponentiating.

2)     pow(i, j, k)
   computes the same result as
       (i**j) % k
   but can be unboundedly faster.

#2 is crucial.  To see why, compute, e.g., 2L**1000000 % 3 by hand,
computing 2L**1000000 first <wink>.  Then do it smarter:  "OK,
(2L**1000000)%3 == (2L**2 % 3)**500000 % 3 == 1L**500000 % 3 == 1L % 3 ==
1L".  That's the kind of savings 3-argument pow can buy you (it does mods
repeatedly under the covers, so that it never actually needs to do
arithmetic with numbers larger than k**2; and the latter can be unboundedly
smaller than i**j, so 3-argument pow can be unboundedly faster).

>     # if any of the primes is a factor, we're done
>     if 0 in map(lambda i,n=n,b=bases:
>                 primes.gcd(n,b[i])==1, range(len(bases))):
>        print "Definitely not prime"
>        return

*Try* writing a nice, readable Python loop -- it might grow on you <wink>.
Note that since you're using primes as bases, gcd(n,b[i]) == 1 is equivalent
to the simpler n % b[i] != 0.  So:

    for base in bases:
        if n % base == 0:
            print "Definitely not prime"
            return

from-the-convoluted-to-the-obvious-ly y'rs  - tim