Great Theoretical Ideas In Computer Science Anupam Gupta CS 15 251 Lecture 15 Oct 17 2006 Fall 2006 Carnegie Mellon University Algebraic Structures Groups Rings and Fields The RSA Cryptosystem Rivest Shamir and Adelman 1978 RSA is one of the most used cryptographic protocols on the net Your browser uses it to establish a secure session with a site Zn 0 1 2 n 1 Zn x 2 Zn GCD x n 1 Quick raising to power Zn n 1 Closed 2 Associative 3 0 is identity 4 Additive Inverses Fast and 5 Cancellation 6 Commutative Zn n 1 Closed 2 Associative 3 1 is identity 4 Multiplicative Inverses Fast and 5 Cancellation 6 Commutative Fundamental lemma of powers Suppose x2 Zn and a b n are naturals If a n b Then xa n xb Equivalently xa n xa mod n Euler Phi Function n size of Zn p prime Zp 1 2 3 p 1 p p 1 pq p 1 q 1 if p q distinct primes The RSA Cryptosystem Rivest Shamir and Adelman 1978 RSA is one of the most used cryptographic protocols on the net Your browser uses it to establish a secure session with a site Pick secret random large primes p q Publish n p q n p q p 1 q 1 Pick random e Z n Publish e Compute d inverse of e in Z n Hence e d 1 mod n Private Key d p q random primes e random Z n n p q e d 1 mod n n e is my public key Use it to send me a message p q prime e random Z n n p q e d 1 mod n n e me mod n me d n m messa ge m An even simpler system Today we are going to study the abstract properties of binary operations Rotating a Square in Space Imagine we can pick up the square rotate it in any way we want and then put it back on the white frame In how many different ways can we put the square back on the frame R90 R180 R270 R0 F F F F We will now study these 8 motions called symmetries of the square R90 R180 R270 R0 F F F F Symmetries of the Square YSQ R0 R90 R180 R270 F F F F Composition Define the operation to mean first do one symmetry and then do the next For example R90 R180 means first rotate 90 clockwise and then 180 R270 F R90 means first flip horizontally and then rotate 90 F Question if a b YSQ does a b YSQ Yes R0 R90 R180 R270 F F F F R0 R0 R90 R180 R270 F F F F R90 R90 R180 R270 R0 F F F F R180 R180 R270 R0 R90 F F F F R270 R270 R0 R90 R180 F F F F F F F F F R0 R180 R90 R270 F F F F F R180 R0 R270 R90 F F F F F R270 R90 F F F F F R0 R90 R270 R180 R180 R0 Some Formalism If S is a set S S is the set of all ordered pairs of elements of S S S a b a S and b S If S has n elements how many elements does S n2S have Formally is a function from YSQ YSQ to YSQ YSQ YSQ YSQ As shorthand we write a b as a b Binary Operations is called a binary operation on YSQ Definition A binary operation on a set S is a function S S S Example The function f defined by f x y xy y is a binary operation on Associativity A binary operation on a set S is associative if for all a b c S a b c a b c Examples Is f defined by f x y xy y associative ab b c c a bc c bc c NO Is the operation on the set of symmetries of the square associative YES Commutativity A binary operation on a set S is commutative if For all a b S a b b a Is the operation on the set of symmetries of the square commutative NO R90 F F R90 Identities R0 is like a null motion Is this true a YSQ a R0 R0 a a YES R0 is called the identity of on YSQ In general for any binary operation on a set S an element e S such that for all a S e a a e a is called an identity of on S Inverses Definition The inverse of an element a YSQ is an element b such that a b b a R0 Examples R90 inverse R270 R180 inverse R180 F inverse F Every element in YSQ has a unique inverse R0 R90 R180 R270 F F F F R0 R0 R90 R180 R270 F F F F R90 R90 R180 R270 R0 F F F F R180 R180 R270 R0 R90 F F F F R270 R270 R0 R90 R180 F F F F F F F F F R0 R180 R90 R270 F F F F F R180 R0 R270 R90 F F F F F R270 R90 F F F F F R0 R90 R270 R180 R180 R0 Groups A group G is a pair S where S is a set and is a binary operation on S such that 1 is associative 2 Identity There exists an element e S such that e a a e a for all a S 3 Inverses For every a S there is b S such that a b b a e If is commutative then G is called a commutative group Examples Is a group Is associative on YES Is there an identity YES 0 Does every element have an inverse NO is NOT a group Examples Is Z a group Is associative on Z YES Is there an identity YES 0 Does every element have an inverse YES Z is a group Examples Is YSQ a group Is associative on YSQ YES Is there an identity YES R0 Does every element have an inverse YES YSQ is a group Examples Is Zn a group Is associative on Zn YES Is there an identity YES 0 Does every element have an inverse YES Zn is a group Examples Is Zn a group Is associative on Zn YES Is there an identity YES 1 Does every element have an inverse YES Zn is a group Identity Is Unique Theorem A group has at most one identity element Proof Suppose e and f are both identities of G S Then f e f e Inverses Are Unique Theorem Every element in a group has a unique inverse Proof Suppose b and c are both inverses of a Then b b e b a c b a c c A group G S is finite if S is a finite set Define G S to be the order of the group i e the number of elements in the group What is the group …
View Full Document
Unlocking...