CMU CS 15251 - Lecture (50 pages)

Previewing pages 1, 2, 3, 24, 25, 26, 27, 48, 49, 50 of 50 page document View the full content.
View Full Document

Lecture



Previewing pages 1, 2, 3, 24, 25, 26, 27, 48, 49, 50 of actual document.

View the full content.
View Full Document
View Full Document

Lecture

83 views


Pages:
50
School:
Carnegie Mellon University
Course:
Cs 15251 - Great Theoretical Ideas in Computer Science
Great Theoretical Ideas in Computer Science Documents

Unformatted text preview:

15 251 Great Theoretical Ideas in Computer Science Raising numbers to powers Cyrptography and RSA Lecture 14 October 7 2010 p 1 p 1 How do you compute 58 using few multiplications First idea 5 52 53 54 55 56 57 58 52 5 5 5 How do you compute 58 Better idea 5 5 52 5524 54 5 5 5 5 2 4 8 Used only 3 mults instead of 7 Repeated squaring calculates 2k a in k multiply operations compare with 2k 1 multiply operations used by the na ve method How do you compute 513 Use repeated squaring again 5 52 54 58 516 too high what now assume no divisions allowed How do you compute 513 Use repeated squaring again 5 52 54 58 Note that 13 8 4 1 1310 1101 2 So a13 a8 a4 a1 Two more multiplies To compute am Suppose 2k m 2k 1 a a2 a4 a8 2k a This takes k multiplies Now write m as a sum of distinct powers of 2 say m 2k 2i1 2i2 2it a a m 2k a 2i1 a 2it at most k more multiplies Hence we can compute am while performing at most 2 log2 m multiplies How do you compute 513 mod 11 First idea Compute 513 using 5 multiplies 5 52 54 58 512 513 1 220 703 125 4 12 5 58 55 then take the answer mod 11 1220703125 mod 11 4 How do you compute 513 mod 11 Better idea keep reducing the answer mod 11 5 52 25 11 3 54 11 58 512 513 11 81 11 36 11 15 9 11 4 11 3 11 4 Hence we can compute am mod n while performing at most 2 log2 m multiplies where each time we multiply together numbers with log2 n 1 bits How do we implement this Let s use my favorite programming language Ocaml It s a functional language that automatically infers the types of variables It compiles to fast code It has an interactive shell so that you can play with the functions you ve written Similar to SML which you will learn about in 15 212 or 15 150 compute a to the pth power modulo n let rec powermod a p n let sq x x x mod n in if p 0 then 1 else let x sq powermod a p 2 n in if p mod 2 0 then x else a x mod n How do you compute 5121242653 mod 11 The current best idea would still need about 54 calculations answer 4 Can we exponentiate any faster



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?