### 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 (12)

### View Full Document

## 30

## 0

## Popular in Course

## Popular in Department

This 4 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 30 views.

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

### 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 Groups De nition and Examples Poorvi L Vora In this module we attempt to look at the similarities between the af ne and shift ciphers using the notion of a group 1 A Group De nition 2 A group is a set C with an associated operation ltgt such that the following hold 0 Closure G is closed under the operation ie I y E G 1 ltgt y E G o Associativity The operation is associative ie z ltgt y ltgt 2 z ltgt y ltgt 2 0 Identity There is an element e E G such that z ltgt e e ltgt 1 z The element e is known as the identity 0 Inverses exist Every element has an inverse in G ie V g E G 3 g E G such that g ltgt 9 g ltgt g e Notice that the operation is very much like addition however it is not always commutative Examples of a group include R the real numbers with addition as the operation Q the rational numbers with addition as the operation Z the integers with addition as the operation 72 0 the real numbers without the number 0 under multiplication n X m matrices for any integers m n under addition any vector space under vector addition including for example the integer lattice the complex n h roots of one under multiplication All the above examples are abelian groups that is the operation ltgt is also commutative a ltgt b b ltgt a The set of invertible n X n matrices is a nonabelian group under multiplication 2 An Example To see that R with ltgt is a group we check each of the requirements of a group 0 Closure Suppose I y E R ie z and y are real numbers Their sum 1 y is also real ie z y E R Hence the closure condition holds CSCI 124 and CSCI 224VoIaGWU 2 o Associativity Addition is associative ie z y z z y 2 so associativity holds 0 Identity Consider the element 0 0 E R and z 0 0 z 1 Hence the identity exists 0 Inverses exist Given T E R consider T 77 It is a member ofR too and To T 77 T 0 e Hence inverses exist You should similarly show that the other examples above are groups 3 Zn as a group under addition mod m An example of a group is the set of remainders Tnod Tn Zm 07 17 7 1 under addition modulo Tn Foran E Zmaob nb MODTn To see that it is a group we check each of the requirements of a group 0 Closure Suppose I y E Zm Their sum 1 y MOD Tn is also in Zm Hence the closure condition holds 0 Associativity Addition over the integers is associative ie z y z z y 2 and hence it is also associative modulo Tn and so associativity holds 0 Identity Consider the element 0 E Zm and z 0 MOD Tn 0 z MOD Tn z MOD Tn Hence the identity exists 0 Inverses exist Givenz E Zm consider i m7 z MOD Tn It is a member of Zm andioz TnMOD Tn 0 MOD Tn e Hence inverses exist The shift cipher now is as follows EKZZmHZm K9 QOK dxzzmHZm dKggltgtK 4 Zn as a group under multiplication mod m Consider the set of remainders modulo m under multiplication Is this a group CSCI 124 and CSCI 224VoIaGWU 3 0 Closure Suppose I y E Zm Their product z X y MOD m is also in Zm Hence the closure condition holds 0 Associativity Multiplication over the integers is associative ie z X y X z z X y X 2 and hence it is also associative modulo m and so associativity holds 0 Identity Consider the elementl E Zm and z X l MOD m l X z MOD m z MOD m Hence the identity exists 0 Inverses Given 1 E Zm i is that integer 0 g i lt m such that If 1 Such a value does not always exist If it were a group the af ne cipher for b 0 could be expressed as EKZZmHZm Ky goK dKzZmHZm dKggltgtK where ltgt is multiplication MOD m 5 When does a 6 Zn have a multiplicative inverse Consider the encryption function f 1 Z25 A Z25 31 MOD 26 Its inverse 9 would be such that Q 1 Z25 A Z25 391 z MOD 26 We have seen that 91 y because that might not always be an element of Z25 However as mentioned by one of the students in the class in the Fall 2006 semester maybe we could get an element in Z25 if we added multiples of 26 to 1 before dividing by 3 For example ifz 10 fz 30 MOD 26 4 and 94 y g However 94 4132 5 10 We use the same idea when determining if z E Zm has a multiplicative inverse If I has an inverse we denote it as i Then If l MOD m and 1 ifiMODm I CSCI 124 and CSCI 224VoIaGWU 4 However 3 k E Z such that and This idea leads to the following more formal statement Theorem I is invertible modulo m if and only if 3 a b E Z such that am 12m 1 Proof We need to show that i exists ltgt 3 a b E Z siti ax 12m l 1 iezists 3i 6 stitizilMODm i k E Zsitizilkm i k E Zsitiziikml ai E Z7andb7k E Zsitiazbml 1 3a 6 Zsitiazbml 3a b E ZsitiaMODmzlmzbm1whereaaMODmlm iaMODmEstitiizlMODm If we had a means of determining whether such values of a and b exist we could answer questions such as how many keys for the af ne cipher exist for a particular value of m In the next section we address an algorithm for determining if such a and b exist

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

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

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

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

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

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