Programming Praxis – Proving Primality

In today’s Programming Praxis exercise we have to implement an algorithm to prove the primality of a number. Let’s get started, shall we?

Some imports:

import Data.Bits
import Data.List

the tdFactors and expm functions have both been featured in previous exercises.

tdFactors :: Integer -> [Integer]
tdFactors n = f n [2..floor . sqrt $ fromIntegral n] where
    f _ []     = []
    f r (x:xs) | mod r x == 0 = x : f (div r x) (x:xs)
               | otherwise    = f r xs

expm :: Integer -> Integer -> Integer -> Integer
expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 .
             filter (flip testBit 0 . snd) .
             zip (iterate (flip mod m . (^ 2)) b) .
             takeWhile (> 0) $ iterate (`shiftR` 1) e

Unfortunately, these math-heavy problems typically resist shortening, so this is pretty similar to the Scheme solution.

isPrime :: Integer -> Bool
isPrime n = f 2 $ tdFactors (n - 1) where
    f _ []     = False
    f b (q:qs) | expm b (n - 1)         n /= 1 = f (b + 1) (q:qs)
               | expm b (n - 1 `div` q) n /= 1 = True
               | otherwise                     = f b qs

All that’s left is a quick test:

main :: IO ()
main = print . isPrime $ 2^89 - 1
About these ads

Tags: , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: