### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CSCI 124 with Professor Vora at GW (3)

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Department

This 3 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 26 views.

## Reviews for Class Note for CSCI 124 with Professor Vora at GW (3)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/07/15

CSCI 124224 Discrete Structures 11 Fast Modular Exponentiation Poorvi L Vora So far we have studied encryption functions that are constructed from addition and multiplication mod m These encryption functions are however not secure enough to use today Among the encryption functions in use today two of the most popular ones are based ontaking the power of an element in Zm In this section we study a fast algorithm for nding a power mod m We will not pursue the encryption functions based on exponentiation any further in this course though These are taught in more detail in the cryptography courses CSci 162 undergraduate Cryptography CS ci 284 graduate introductory Cryptography and CS ci 381 graduate Advanced Cryptography Consider how one might compute xk mad m for large values of z k and m If one actually performed k 7 l multiplications z X z X X I that could be a large number of multiplications On the other hand one might use the squareand multiply rule which is considerably more ef cient Let s consider an example with small enough numbers to compute results by hand 513 mod 17 513 mod 17 522 X 522 X 5 which involves only 5 multiplications instead of 12 Or another example 515 mod 17 522 gtlt 522 X 52 X 5 which involves 6 multiplications This can be formalized as follows exponentiationbc I m 117 mod m z 1 bi W bit in biliary representation of b forz39 l 7 l downto O 2 I 22 mod n ifbilzzzgtltzm0dn endfor retun1z Example 551 mod 7 CSCI 124 and CSCI 297VoIaGWU 2 51 110011 Example 729 mod 11 29 11101 i Zsecond 4 7 3 2 2 6 1 3 O 8 Why do we believe this algorithm works Suppose you wish to determine 1 mod m You rst express n in binary form Let the binary expression for n be 21641216411120 where n is of length k bits Then kil n EEO 1212 Hence kil 7k71 39I 39I kil k72 0 In IZo 172 I I 11712 zbk gtlt zbk gtlt X 1502 10 where H represents the product as 2 represents the sum The above expression is I H 121 121 as the terms with 12 0 reduce to the number 1 The algorithm introduces a factor of 1 every time the bit 12 is 1 Additionally at each step the algorithm squares the number If one follows a single value of I after is introduced into the loop it gets squared as many times as there are 239 loops left I2222w2 1f the I value is introduced in the loop for 239 i0 it is squared 2390 times and hence the factor it introduces into the nal computed value is 210 The nal computed value is the product of all these values hence it is the value desired It will be easier to understand if one sees an example Example 1 39215 m0d121 215110101111X271X250gtlt251X240gtlt231gtlt221gtlt211gtlt20 Hence 39215 391x27 X 391x26 X 390x25 X 391x24 X 390w3 X 391w2 X 391x21 X 391x20 392quot X 3926 X 392 1 X 3922 X 3921 X 392 CSCI 124 and CSCI 297VoIaGWU 3 i bi Zfim Zsecond 7 1 1 39 z 6 1 69 12 29 12 X z 5 0 115 122 X 12 115 122 X 12 4 1 36122 X122 73123m22m 3 0 5124Xz23X12 5124X123X12 2 1 25125xz24X122 7125Xz24X122xz 1 1 49126X125X122Xz2 96126X125X123X12XI 0 1 20127X126X124X122Xz2 54125X126X124X122X12XI 39215 mod121 54 Finally one can use recursion to show that it is correct Consider the W loop Let the value of 2 input to the loop be 2141 it is the value of 2 at the end of loop 239 1 The output after the W loop is 2139 Then 21 zal gtlt II 20 is the output and 2k 1 Further one can check that 71 ji is a correct expression for 2139 and 6 1 6 1 6 1 77171 772 772 Zial X 11quot I I 1572 2 X 1quot I I 1572 X 1quot I I 1572 2i ji1 ji1 ji Hence the nal value of z is 6 1 7 20 H 1572 I j0

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.