A program to perform modular arithmetic

Write a computer program to add and multiply mod n, for any n given as input. The output of these operations should be the least residues of the sums and products of the two integers. Also include the feature that if \mathsf{gcd}(a,n) = 1, an integer c between 0 and n-1 such that ac = 1 mod n may be printed on request.

mod :: Integer -> Integer -> Integer
mod a n'
 | a < 0     = mod (a+n) n
 | a > n     = mod (a-n) n
 | otherwise = a
 where n = abs n'

plusMod :: Integer -> Integer -> Integer -> Integer
plusMod n a b = mod (a+b) n

timesMod :: Integer -> Integer -> Integer -> Integer
timesMod n a b = mod (a*b) n

invMod :: Integer -> Integer -> Maybe Integer
invMod a n 
 = if (gcd a n) /= 1 
    then Nothing 
    else Just $ foo $ fst $ bezout a n
   where foo k = if k < 0 then (k+n) else k
Post a comment or leave a trackback: Trackback URL.

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

%d bloggers like this: