Modular Arithmetic
July 7, 2009
Modular arithmetic is a branch of number theory that is useful in its own right and as a tool in such disciplines as integer factorization, calendrical and astronomical calculations, and cryptography. Modular arithmetic was systematized by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
Modular arithmetic is a system of arithmetic for integers in which all results are expressed as non-negative integers less than the modulus. A familiar use of modular arithmetic is the twelve-hour clock, in which eight hours after nine o’clock is five o’clock; that is, 9 + 8 ≡ 5 (mod 12). The ≡ sign used in modular arithmetic specifies congruence, not equality. Two numbers are congruent in a given modulus if the difference between them is an even multiple of the modulus; for instance 17 ≡ 5 (mod 12). Modular addition is like regular addition, but “wraps around” at the modulus. Modular subtraction is the inverse operation of modular addition, and modular multiplication is just repeated modular addition; for instance 4 − 9 ≡ 7 (mod 12), and 3 × 7 ≡ 9 (mod 12).
Modular division is the inverse operation of modular multiplication, just as regular division is the inverse operation of regular multiplication. In modular arithmetic, the modular inverse of an integer p is that integer q for which p × q ≡ 1 (mod n); the modular inverse is undefined, just as division by zero is undefined, unless the target number is coprime to the modulus. The extended Euclidean algorithm calculates the inverse; given ax + by = g = gcd(x, y), when g = 1 and x > 0, b (mod x) and a (mod y) are the inverses of y (mod x) and x (mod y), respectively. Then modular division is just modular multiplication by the inverse. For instance, 9 ÷ 7 ≡ 3 (mod 12).
Exponentiation in modular arithmetic is repeated modular multiplication, just as exponentiation is repeated multiplication in normal arithmetic. Modular exponentiation could be performed by first computing the exponentiation and then performing the modulo operation, but that could involve a large intermediate result. A better method performs the modulo operations at each multiplication, squaring when possible to reduce the number of intermediate multiplications.
Square root is defined in modular arithmetic as that number which, when multiplied by itself, equals the target number, just as in normal arithmetic. And just as in normal arithmetic, every square root has a conjugate on the “other side” of zero, except that in modular arithmetic there is no “other side” of zero, so the two conjugates are the negatives of each other, adding to the modulus. For instance the square roots of 18 (mod 31) are 7 and 24, since 7 × 7 ≡ 18 (mod 31) and 24 × 24 ≡ 18 (mod 31), and 7 + 24 = 31.
Square root is a more difficult concept in modular arithmetic than regular arithmetic, because there are many cases where the modular square root does not exist. For instance, consider the squares x2 (mod 13), 0 ≤ x < 13: 0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1. There is no number that can be squared modulo 13 to evaluate to 7, so the square root of 7 modulo 13 does not exist; the only numbers that have square roots modulo 13 are 1, 3, 4, 9, 10, and 12, or, equivalently, ±1, ±3, and ±4. Another restriction is that the modular square root is only defined if the modulus is an odd prime. For instance, consider the squares x2 (mod 15), 0 ≤ x < 15: 0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1. The number 4 has two sets of conjugate square roots: ±2 and ±7. Since the solution is not unique, the modular square root can be said not to exist when the modulus is composite.
If you need a refresher on the math that supports modular arithmetic, you can look at any number theory textbook, or search the internet for terms such as modular arithmetic, bezout identity, modular inverse, jacobi symbol, and quadratic residue.
Your task is to write a library that provides convenient access to the basic operations of modular arithmetic: addition, subtraction, multiplication, division, exponentiation, and square root. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Praxis – Modular Arithmetic By Remco Niemeijer Yesterday’s Programming Praxis problem is about making a convenient way to do modular arithmetic. While the […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/07/08/programming-praxis-modular-arithmetic/ for a version with comments):
import Data.Bits import Data.List euclid :: Integral a => a -> a -> a euclid x y = f 1 0 x 0 1 y where f a b g u v w | w == 0 = mod a y | otherwise = f u v w (a-q*u) (b-q*v) (g-q*w) where q = div g w inv :: Integral a => a -> a -> a inv x m | gcd x m == 1 = euclid x m | otherwise = error "divisor must be coprime to modulus" (<=>) :: Integral a => a -> a -> a -> Bool a <=> b = \m -> mod a m == mod b m (<+>), (<->), (<*>), (</>) :: Integral a => a -> a -> a -> a a <+> b = \m -> mod (a + mod b m) m a <-> b = a <+> (-b) a <*> b = \m -> mod (a * mod b m) m a </> b = \m -> (a <*> inv b m) m 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 (<^>) :: Integer -> Integer -> Integer -> Integer (<^>) = expm sqrtm :: Integral a => a -> a -> [a] sqrtm x m = case [n | n <- [1..m], (n <*> n) m == mod x m] of (_:_:_:_) -> [] s -> s modulo :: a -> (a -> b) -> b modulo = flip ($) main :: IO () main = do mapM_ (modulo 12) [ print . (17 <=> 5), print . (8 <+> 9), print . (4 <-> 9), print . (3 <*> 7), print . (9 </> 7)] mapM_ (modulo 13) [ print . (6 <^> 2), print . (7 <^> 2), print . sqrtm 10][…] OLE 2 or ActiveX, we are referring to a very specific type of object, sometimes called a … Modular Arithmetic « Programming Praxis – programmingpraxis.com 12/31/1969 Programming Praxis. A collection of etudes, updated weekly, for […]
Here is an improved version of modular inverse, based on Algorithm 9.4.4 from the book Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance:
(define (inverse x m)(if (not (= (gcd x m) 1))
(error 'inverse "divisor must be coprime to modulus")
(let loop ((z (modulo x m)) (a 1))
(if (= z 1) a
(let ((q (- (quotient m z))))
(loop (+ m (* q z)) (modulo (* q a) m)))))))
Here is a variant of the above code where the operation take and return functions. The intention is to get rid of the ugliness of having to pass the modulo value in every function invocation.
The disadvantage is that you cant use ints directly in the expressions, you have to wrap them in the ugly i functions. Is there a solution to this?
test_func = ((i 5) *% (i 6) +% (i 7)) 13
(=%) :: TModNum -> TModNum -> (Integer -> Bool)
a =% b = \m -> (a m) == (b m)
type TModNum = (Integer -> Integer)
(+%), (-%), (*%), (/%) :: TModNum -> TModNum -> TModNum
a +% b = \m -> mod ((a m) + (b m)) m
a -% b = \m -> mod ((a m) - (b m)) m
a *% b = \m -> mod ((a m) * (b m)) m
a /% b = \m -> mod ((a m) * (inv (b m) m)) m
i :: Integer -> (Integer -> Integer)
i n = \m -> mod n m
I am wondering, how do you deal with integer overflow when doing modular arithmetic? Especially when the size of modulus is close to the size of a c integer.
For example, for addition in c I am trying the following with unsigned integers
unsigned int res, a, b, p;
…
res = a+b;
if(res < a)
while (res < (res = res + (0-p) % p));
but I still need to figure out if it is correct.
I just want a result that's congruent to the correct result – it doesn't have to be the smallest remainder mod p.
To answer my own question, here is what I came up with:
uint res = a+b;
if(res < a){
while((p2 = (p < p) p = p2;
if (p > res) res = res – p; else res = (res – p) – p;
}
But a better strategy may be to make sure the modulus p is always one bit less than the range of the integer, use signed ints and then reduce mod p before each addition or subtraction and not have any extra code.
@Matthew: See https://programmingpraxis.com/2013/05/28/modular-multiplication-without-overflow/.
[…] method, as well as the extended Euclidean algorithm in Algorithm X. I describe (with code) the original Euclidean algorithm, the modern Euclidean algorithm, the binary algorithm, and the extended Euclidean algorithm at my […]
[…] method, as well as the extended Euclidean algorithm in Algorithm X. I describe (with code) the original Euclidean algorithm, the modern Euclidean algorithm, the binary algorithm, and the extended Euclidean algorithm at my […]
[…] method, as well as the extended Euclidean algorithm in Algorithm X. I describe (with code) the original Euclidean algorithm, the modern Euclidean algorithm, the binary algorithm, and the extended Euclidean algorithm at my […]