blob: 7c0c8a6a3b8150e7eb63a1bcc2a05678733f40bb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
module H31
( isPrime
, isPrimeT
) where
import System.Random
isPrime :: Integral a => a -> Bool
isPrime x = and $ fmap ((/=0).(mod x)) [2..(x-1)]
testn = 10
isPrimeT 2 = True
isPrimeT x = and $ fmap ((/=0).(fstPow x (x-1))) $ take testn $ randomRs (2,(x-1)) (mkStdGen 100)
fstPow _ 1 x = x
fstPow m y x
| y `mod` 2 == 1 = (x * (fstPow m (y `div` 2) (sqr x))) `mod` m
| otherwise = fstPow m (y `div` 2) (sqr x)
where sqr a = (a*a) `mod` m
|
