Transcript Modular Arithmetic - svmoore

Modular Arithmetic
Shirley Moore
CS4390/5390 Fall 2013
http://svmoore.pbworks.com/
September 5, 2013
1
Agenda
• Intro to Matlab by Rogelio Long (cont.) (15
min)
• Discuss homework from last class (15 min)
• Modular arithmetic (20 min)
• Fermat’s Little Theorem (20 min)
• Wrap-up and preparation for next class (5
min)
2
Modular Arithmetic
• The number X (mod Y) is the remainder when
X is divided by Y.
– For example: 7 (mod 3) is 1 because 7 = 2 * 3 + 1.
That is, when you divide 7 by 3, you get a
remainder of 1.
– The "modulo Y" terminology can also be used in
the following way: Z = X (mod Y), meaning that Z
and X have the same remainder when divided by
Y. For example: 7 = 25 (mod 3)because 7 = 2 * 3 +
1 and 25 = 8 * 3 + 1
3
Modular Addition
• Find the units digit of the sum
2403 + 791 + 688 + 4339
i.e., 2403 + 791 + 688 + 4339 (mod 10)
• In general, if a, b, c, and d are integers and m is a
positive integer such that
a = c (mod m) and b = d (mod m)
then
a + b = c + d (mod m)
Proof:
4
Modular Multiplication
• When you take products of many numbers and you
want to find their remainder modulo n, you never need
to worry about numbers bigger than the square of n.
• Pick any two numbers x and y, and look at their
remainders (mod 7):
a = x (mod 7)
b = y (mod 7)
• Compare the remainder modulo 7 of the products xy
and ab:
xy (mod 7) with ab (mod 7)
• For example, try x = 26, y = 80
5
Modular Multiplication of Many
Numbers
• If we want to multiply many numbers modulo
n, we can first reduce all numbers to their
remainders. Then, we can take any pair of
them, multiply and reduce again.
• For example, suppose we want to find
X = 36 * 53 * 91 * 17 * 22 (mod 29)
• What is the largest number we have to
multiply?
6
Modular Exponentiation
• Suppose we would like to calculate 1143 (mod 13).
• The straightforward method would be to multiply
11 by 11, then to multiply the result by 11, and so
forth. This would require 42 multiplications.
• We can save a lot of multiplications if we do the
following:
– First write 43 as a sum of powers of 2:
43 = 32 + 8 + 2 + 1
– That means that 1143 = 1132 * 118 * 112 * 11 .
• How many multiplications are required, and what
is the largest number we have to multiply?
7
Fermat’s Little Theorem
• First stated by Pierre de Fermat in 1640
• First published proof by Leonhard Euler in 1736
• Highly useful for simplifying the computation of exponents
in modular arithmetic
• Corollary by Euler serves as the basis for RSA encryption
• Theorem: If p is a prime number and p does not divide a,
then ap-1 = 1 (mod p)
• Example: p = 5
• Proof: See
http://www.youtube.com/watch?v=w0ZQvZLx2KA
• Use FLT to find 3100,000 (mod 53)
8
Use FLT to prove a number is
composite without factoring it
• To prove n is composite, find some a such that
a is not a multiple of n and an-1 ≠ 1 (mod n).
• Is 91 a prime number? Try a = 2.
• 75 = 1 (mod 6), so is 6 prime?
• True or False: If bn-1 = 1 (mod n) for all b such
that b is not a multiple of n, then n is prime.
9
Modular Arithmetic in Matlab
• http://www.mathworks.com/help/symbolic/m
upad_ug/modular-arithmetic.html
• mod
• mods
• powermod
10
Preparation for Next Class
• Work on Homework 1 (turn in for grade, due
September 12). Ask questions next class.
11