CODEWITHSUNDEEP
haskellmathprimality-test
Eros Fabrici
Eros Fabrici

Reputation: 19

Fermat Primality Test Haskell

I have implemented the following two functions for establishing if n is a fermat prime number (will return n if its true, -1 if not), but it returns always -1, can't figure out why (gc is a funct taht calculates gcd)

fermatPT :: Int -> Int
fermatPT n = fermatPT' n list
  where
    list = [a | a <- [1..n-1]]

-- | heper function
fermatPT' :: Int -> [Int] -> Int
fermatPT' n l      | gc (n, head l) == 1 && fermatTest n (head l) = fermatPT' n (tail l)
                   | null l                                       = n
                   | otherwise                                    = -1
                where
                  fermatTest n a = mod (a^(n-1)) n == 1

Upvotes: 0

Views: 486

Answers (1)

chepner
chepner

Reputation: 531225

Your function should return a boolean indicating if the given number is a prime. If you do that, you can use the all function to define this simply as

fermatPT :: Integer -> Bool
fermatPT n = all (fermatTest n) (filter (\a -> gcd n a == 1) [1..n-1])
             where fermatTest n a = mod (a^(n-1)) n == 1

gcd is defined in the Prelude.

all avoids the explicit recursion that requires you to apply the test to one element of [1..n-1] at a time; its definition is effectively

all _ [] = True
all p (x:xs) = p x && all p xs

Note that mod (a ^ (n - 1)) n is inefficient, since it may require computing an absurdly large number before ultimately reducing it to the range [0..n-1]. Instead, take advantage of the fact that ab mod n == (a mod n * b mod n) mod n, and reduce the value after each multiplication. One way to implement this (not the fastest, but it's simple):

modN :: Integer -> Integer -> Integer -> Integer
modN a 0 _ = 1
modN a b n = ((a `mod` n) * (modN a (b - 1) n)) `mod` n

Then use

fermatTest n a = modN a (n-1) n == 1

Note that you could use this (with Int instead of Integer) to correctly implement fermatPT :: Int -> Bool; although the input would still be restricted to smaller integers, it won't suffer from overflow.

Upvotes: 2

Related Questions