×

### Let's log you in.

or

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

×

or

19

0

2

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

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

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 19 views.

×

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

×

×

### 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 GCD The euclidean algorithm for the gcd of two elements is thought to be the oldest existing algorithm It is recursive We describe the main idea behind it as a theorem With proof then the algorithm and then an argument that the algorithm is correct 1 Main Idea Theoremgcdm7 a gcdam Tem a Proof Let g be any common factor ofm and a and T Tn Tem a thenm T go 4 E Z glmy yla m 419 a 129 fOT same 4142 6 Z T 941 7 442 W W Further let h be any common factor of a and T then h a7 h T a 43h T q4h f0T some 43 L14 6 Z m hq4 443 h T him Thus common factors of a and T are exactly the common factors of Tn and a Hence the greatest common factor of a and T is the greatest common factor of a and Tn Note here that any number is considered a factor of 0 so we do not consider the case T 0 separately 2 Algorithm The euclidean algorithm is as follows Algorithmgcd n a Tn gt a X7 Y Tn7 a Initialize While Y y 0 X7 Y 2 Y7 X Tem Y Recursion returnX Example Use the euclidean algorithm to determine gcd5757 299 XY 575299 XY 299276 XY 27623 XY 230 TetuTn 23 CSCI 162 and CSCI 284NoIaGWU 2 Example Use the euclidean algorithm to determine gcd4316 1245 XY 43161245 XY 1245581 XY 58183 XY 830 Teturn83 Example Use the euclidean algorithm to determine gcd2652 8855 XY 88552652 XY 2652899 XY 899854 XY 85445 XY 4544 XY 441 XY 10 return 3 Correctness of Algorithm In each recursion gcdX Y stays the same While X and Y change Further at each step we decrease both X and Y and because both are remainders neither is ever negative Hence the algorithm Will end some time in fact in at most a steps Finally at the last but one recursion because X rem Y is zero X is a multiple of Y and hence gcdX Y Y At the last recursion X Y 2 Y 0 and the retunied value X is the correct god it is the value of Y from the previous recursion A more formal proof is as follows Theorem Algorithmgcdm a returns gcdm a Proof We denote the value of X Y in the W iteration as Xi Yi Then Xi Yi 17371 Xi1 rem Yi1 and X0 Y0 m a Let the total number of iterations be N That is YN 0 and Algo7 ithmgcdm a retunis XN Then from the theorem proved earlier if N is nite 90dm7a 90dX07Y0 90dX17Y1 95dXN717YN71 Further YN11XN1 hence gcdXN1 YN1 YN1 XN Hence gcdm a XN Which is What Algorithmgc m a retunis Further 0 lt Yi lt Yi1 unless Yi 0 Hence Yi is strictly decreasing and nonnegative As the algorithm stops When Y 0 and Y decreases by at least 1 at each step N g a Y0 Hence N is nite

×

×

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

Steve Martinelli UC Los Angeles

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

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

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