6 006 Introduction to Algorithms Lecture 23 Prof Patrick Jaillet Outline Numerics II algorithms for operations on large numbers Today quick review irrationals large number operations addition multiplication division cryptography CLRS 31 motivations primality testing modular exponentiation integer factorization 2 3 5 7 11 13 17 31 37 41 43 47 53 59 73 79 83 89 97 101 103 127 131 137 139 149 151 157 179 181 191 193 197 199 211 233 239 241 251 257 263 269 283 293 307 311 313 317 331 353 359 367 373 379 383 389 419 421 431 433 439 443 449 467 479 487 491 499 503 509 547 557 563 569 571 577 587 607 613 617 619 631 641 643 661 673 677 683 691 701 709 739 743 751 757 761 769 773 811 821 823 827 829 839 853 877 881 883 887 907 911 919 947 953 967 971 977 983 991 19 61 107 163 223 271 337 397 457 521 593 647 719 787 857 929 997 23 67 109 167 227 277 347 401 461 523 599 653 727 797 859 937 29 71 113 173 229 281 349 409 463 541 601 659 733 809 863 941 Computing h to lots of digits why 1 2 1 1 414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 question pattern Computing h to lots of digits why B geometry problem 1 BD 1 what is AD C D A 1000 000 000 000 AD AC CD 500 000 000 000 500 000 000 000 2 1 question first non trivial digits Taylor s expansion 1 1 2 1 3 5 4 1 x 1 x x x x 2 8 16 128 AD 10 12 10 36 2 10 60 5 10 84 Cryptography long history modern development public key cryptography some designed as early as 1973 UK but classified top secret and revealed publicly in 1998 RSA 1978 for Rivest Shamir and Adleman is the first algorithm suitable for signing and encryption widely used in electronic commerce protocols Public key cryptography key generation public key private key encryption decryption RSA key generation choose two prime number p and q compute n pq compute f n p 1 q 1 choose e 1 e f n and gcd e f n 1 e and f n are co prime e is released as the public key exponent find d e 1 mod f n d is kept as the private key exponent RSA encryption Alice transmits her public key n e to Bob Bob wishes to send a message Hello Alice to Alice he turns the message into an integer m 0 m n using an agreed upon protocol a padding scheme he computes c me mod n he transmits c to Alice RSA decryption Alice can recover m from c by using her private key exponent d as follows m cd mod n Given m she can recover the message Hello Alice by reversing the padding scheme RSA example key generation choose p 61 and q 53 compute n pq 3233 compute f n p 1 q 1 3120 choose a prime number e not a divisor of 3120 say e 17 find d e 1 mod f n 2753 the public key is n e 3233 17 the private key is n d 3233 2753 encryption m 65 is encrypted as c 6517 mod 3233 2790 decryption c 2790 is decrypted as m 27902753 mod 3233 65 RSA when does it work keys generation n pq needs to be very large e g at least 200 digits so that both the public and private key exponents are large enough p and q should come out of a random process i e not easily guessed needs an efficient way to check if such generated p and q are indeed primes encryption given large n e and any m needs an efficient way of computing c me mod n decryption given large n d and any c needs an efficient way of computing m cd mod n given large n e should be hard to find d given large n e c should be hard to find m Modular exponentiation Given n c d calculate m cd mod n How divide and conquer raising powers with repeated squaring efficient when using the binary representation of d e g d 560 1 0 0 0 1 1 0 0 0 0 Modular exponentiation II Given n c d calculate m cd mod n procedure computes ci mod n as i is increased by doublings incrementing from 0 to d i 0 m 1 let d dk dk 1 d0 for j k downto 0 i 2i m m m mod n if dj 1 i i 1 m m c mod n return m Modular exponentiation III Given n c d calculate m cd mod n i 0 m 1 let d dk dk 1 d0 for j k downto 0 i 2i m m m mod n if dj 1 i i 1 m m c mod n return m if n c d are k bits number total number of bit operations is O k3 Primality testing Given an integer p is p a prime number Wilson s theorem p is prime if and only if p divides p 1 1 is nice but useless for our purpose computing p 1 1 and testing if p divides p 1 1 become computationally prohibitive for large p Primality testing I Given an integer p is p a prime number Basic Algorithm check whether any integer m from 2 to p divides p skipping even integers If none of them do p is prime complexity p exponential in the length of p Primality testing II Given an integer p is p a prime number Randomization to the rescue Pseudoprimes def p is a base a pseudoprime if p is composite and ap 1 1 mod p Thm if p is prime then ap 1 1 mod p for all 1 a p 1 from Fermat converse is almost true Primality testing III Given an integer p is p a prime number randomization to the rescue pseudo prime testing input p if 2p 1 1 mod p then return composite else return prime definitely we hope Primality testing IV input p if 2p 1 1 mod p then return composite else return prime definitely we hope will make a mistake only if p is a base 2 pseudoprime and this is rare only 22 values of p less than 10 000 for which it makes a mistake 341 561 645 probability of a mistake for a randomly chosen 1024 bit number is 10 41 Primality testing V A randomized testing input p choose a random number 2 a p 2 if ap 1 1 mod p then return composite definitely else return prime almost surely Integer factorization Given an integer n decompose it into a product of primes Unless P NP this seems to be a computationally hard problem and a good …
View Full Document
Unlocking...