×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

14

0

2

# Class Note for CSCI 162 with Professor Vora at GW

Marketplace > George Washington University > Class Note for CSCI 162 with Professor Vora at GW

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
2
WORDS
KARMA
25 ?

## Popular in Department

This 2 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 14 views.

×

## Reviews for Class Note for CSCI 162 with Professor Vora at GW

×

×

### What is Karma?

#### 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 162 and CSCI 284NoIaGWU l CSCI 162284 Cryptography Euclidean Algorithm for the Multiplicative Inverse The euclidean algorithm for the gcd of two elements may be extended to determine the multiplicative inverse as follows If the gcd of two elements is one that is if gcdm a 1 then the euclidean algorithm can be modi ed to provide integers s and t such that 5m ta 1 t mod m is then the multiplicative inverse of a mod m 1 Modi ed Euclidean Algorithm The modi ed euclidean algorithm is as follows Modi edEuclideanm a m gt a l Part I Keep track of the quotient 239 z 0 Initialize X0Y0 m a Initialize while Y 9 0 While GCD has not been found qi Keep track of quotient XI1 YiH Yi Xi rem Yi Recursion step i I i l i I i 7 l X Y Keep value of Yi it is GCD Part II Go back up s t O 1 Initialize while 239 y 0 While not at top i i1 s t z t s 7 t X 41 Recursion step returnX st Example Use the euclidean algorithm to determine 2652 1 mod 8855 The rst round gives XmYomo 8855265213 hi12341 265289912 X27Y27i742 89985421 X37Ysz qg 85445318 X47Y47m4 454441 CSCI 162 and CSCI 284NoIaGWU 2 X57Y57i745 447175744 XyYyi 1706 Going back up X0Y0iq0st 88552652135972075937197 X1Y1z39qlst 2652899127201977202 59 X2Y2z39q2st 8998542119717191720 X3Y3iqgst 8544531871177118 19 X4Y4iq4st 4544411071171 X5Y5iq5st 44154401 nyyi 17076 TetuTn1 59 7197 Hence 59 X 8855 7197 X 2652 1 Hence 2652 1 mod 8855 7197 mod 8855 8658 mod 8855 2 Correctness of Algorithm We know that the above algorithm retunis the correct god We show that it retunis the correct values of s and t Theorem X s t retunied by ModifiedEuclideanm a are such that X 5m ta Proof We show that 5k gtlt Xk tk gtlt Yk gcdXkYk for 0 g k g N 7 1 by induction Hence in particular this implies that so gtlt X0 to X Y0 gcdX0 Y0 which we have shown is X Hence this implies that 5m ta X Base Case 5N4L XXN1tN1 XYN1 0gtlt XN11gtltYN1 YN1 gcdXN1YN1 As YN1XN1 Hence the inductive hypothesis is true for k N 7 1 Inductive Case Assume the hypothesis is true for k n such that 1 g n g N 7 1 Then 3 X Xn tn gtlt Yn gcdXnYn gt 3 X Yn1 tn gtlt X7171 7 qnil gtlt Yn71 ngXn717Yn71 tn gtlt Xn1 3n 7 tnqn71 gtlt Yn1 gcdXn1Yn1 gt 3W1 gtlt Xn1 tn1 gtlt Yn1 gcdXn1Yn1 This implies the hypothesis is true for k n 7 1 Hence it is true for k 0 D

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

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

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### 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