Report

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. CS 312: Algorithm Analysis Lecture #3: Algorithms for Modular Arithmetic, Modular Exponentiation Slides by: Eric Ringger, with contributions from Mike Jones, Eric Mercer, Sean Warnick Announcements HW #1 Due Now Always start of class Always show work FERPA protects your student record Need waiver to return graded work without cover sheet Objectives Add the Max Rule to your asymptotic analysis toolbox Review modular arithmetic Discuss and analyze algorithms for: modular arithmetic modular exponentiation Max. rule Another useful rule for Asymptotic analysis. O( f(n) + g(n) ) = O( max( f(n), g(n) ) ) Examples: Goal for Ch. 1 Appreciate the role of theoretical analysis in the security of RSA. Requires: Solve, analyze, and use (!) two important and related problems: Factoring: Given a number N, express it as a product of its prime numbers Primality Testing: Given a number N, determine whether it is prime Which one is harder? Algorithms for Integer Arithmetic Computing Device: Binary operations are constant time Arithmetic operations on arbitrary length integers may require more time For an integer , we talk about its representation in bits: = log 2 Pad length of to the next power of 2 (using 0s) if necessary. Algorithms for Integer Arithmetic Addition Multiplication Division Algorithms for Integer Arithmetic Addition: Θ() Multiplication: Θ(2 ) Division: Θ(2 ) Modular Arithmetic Congruency An important distinction Congruency Equality, using the modulus operator Properties Associativity: Commutativity: Distributivity: Substitution Rule Useful Consequence xy (x mod z)y (mod z) xy mod z = (x mod z)y mod z Example: Modular Addition Modular Multiplication Goal: Modular Exponentiation We need to compute xy mod N for values of x, y, and N that are several hundred bits long. Can we do so quickly? Sequential Exponentiation Describe a simple algorithm for doing exponentiation: function seqexp (x, y) Input: An n-bit integer x and a non-negative integer exponent y (arbitrarily large) Output: xy if y=0: return 1 r=x for i = 1 to y-1 do r=r⋅x return r Analysis of Sequential Exponentiation function seqexp (x, y) Input: An n-bit integer x and a non-negative integer exponent y (arbitrarily large) Output: xy if y=0: return 1 r=x for i = 1 to y-1 do r=rx return r Modular Exponentiation, Take I function modexp (x, y, N) Input: Two n-bit integers x and N, a non-negative integer exponent y (arbitrarily large) Output: xy mod N if y=0: return 1 r = x mod N for i = 1 to y-1 do r = (r ⋅ x) mod N return r Modular Exponentiation, Take I function modexp (x, y, N) Input: Two n-bit integers x and N, a non-negative integer exponent y (arbitrarily large) Output: xy mod N if y=0: return 1 r = x mod N for i = 1 to y-1 do r = (r ⋅ x) mod N return r New Ideas Represent y (the exponent) in binary Then break down xy into factors using the non-zero bits of y Also: compute the factors using repeated squaring Reduce factors using substitution rule Modular Exponentiation, Take II function modexp (x, y, N) Input: Two n-bit integers x and N, a non-negative integer exponent y (arbitrarily large) Output: xy mod N Recursive call if y=0: return 1 z = modexp(x, floor(y/2), N) if y is even: return z2 mod N else: return x ⋅ z2 mod N Right shift Multiplication Analysis of Modular Exponentiation Each multiplication is Q(n2) Each modular reduction is Q(n2) There are log(y)=m of them Thus, modular exponentiation is in Q(n2 log y) = Q(n2 m) function modexp (x, y, N) if y=0: return 1 z = modexp(x, floor(y/2), N) if y is even: return z2 mod N else: return x z2 mod N Modular Exponentiation (II), Iterative Formulation function modexp (x, y, N) Input: Two n-bit integers x and N, a non-negative integer exponent y (arbitrarily large) Output: xy mod N if y = 0: return 1 i = y; r = 1; z = x mod N while i > 0 if i is odd: r = r ⋅ z mod N z = z2 mod N i = floor(i/2) return r Modular Exponentiation xy mod N Key Insights: 1. Exponent y can be represented in binary 2. Problem can be factored into one factor per binary digit 3. Each factor can be reduced mod N (substitution rule) Example We’re employing same insights and a little more cleverness than the algorithm. Example #2 function modexp (x, y, N) Input: Two n-bit integers x and N, an integer exponent y (arbitrarily large) Output: xy mod N if y = 0: return 1 i = y; r = 1; z = x mod N while i > 0 if i is odd: r = r z mod N z = z2 mod N i = floor(i/2) return r 310 mod10 x 3, y 10, N 10 i 10, r 1, z 3mod10 3 z 32 mod10 9 i5 r 1 9 mod10 9 z 92 mod10 81mod10 1 i2 z 12 mod10 1 i 1 r 9 1mod10 9 z 1 i0 return 9 Strictly tracing the algorithm. Example #2 function modexp (x, y, N) Input: Two n-bit integers x and N, an integer exponent y (arbitrarily large) Output: xy mod N if y = 0: return 1 i = y; r = 1; z = x mod N while i > 0 if i is odd: r = r z mod N z = z2 mod N i = floor(i/2) return r 310 mod10 x 3, y 10, N 10 i 10, r 1, z 3mod10 3 z 32 mod10 9 i5 r 1 9 mod10 9 z 92 mod10 81mod10 1 i2 z 12 mod10 1 i 1 r 9 1mod10 9 z 1 i0 return 9 Example 20 3 mod 10 Needed: two volunteers: Volunteer A: use our final modexp() to compute it. Volunteer B: compute 320 then reduce mod 10 Efficiency The key point is that xy mod N is easy modexp is in Q(n2 log y) In fact, it requires about 1.5 log2 y multiplications for typical y seqexp required y-1 multiplications When x, y, and N are 200 digit numbers Assume 1 multiplication of two 200 digit numbers takes 0.001 seconds modexp typically takes about 1 second seqexp would require 10179 times the Age of the Universe! Only works when y is an integer. Assignment Read: Section 1.4 HW #2: Problem 1.25 using modexp, Then redo 1.25 but replace 125 with 126 for the exponent Implement modular exponentiation now as a step toward finishing Project #1 Next Primality Testing