Math 110 Homework 3 Solutions

1 math 110 Homework 3 SolutionsJanuary 29, 20151. (a) Describe the method in Section for efficiently computing exponentialsab(modn), and verifythe book s claim that this can be done in at most 2 log2(b) multiplications.(b) Use this method to compute 3172(mod 191).Solution:(a) The basic idea is thata2mcan be calculated inm 1 multiplications, asa2m a2m 1 a2m 1(modn) so you can multiply the exponent by two by doing one multiplication. In general, writeb=cm 2m+cm 1 2m 1+..+c12 +c0whereci {0,1}. Then computea,a2,a4,..,a2m(modn)by multiplying the previous element in this list with itself. This takesm 1 multiplications. Finallycomputeacm2m acm 12m 1 .. a2c1 ac0 ab(modn)This requires at mostmmultiplications, as each term is either 1 or one of the precomputeda2i. Notethatmis the integer part of log2(b), so we need at most 2 log2(b) multiplications.(b) For example, 172 = 128 + 32 + 8 + 4, and34 81 (mod 191)38 67 (mod 191)316 96 (mod 191)332 48 (mod 191)364 12 (mod 191)3128 144 (mod 191)Therefore we combine these to see that3172 144 48 67 81 170 (mod 191).

2 2. (a) State Fermat s Little Theorem. Define Euler s totient function , and state Euler s Theorem.(b) Use the theorems to describe how we can further simplify the computation ofab(modn) whenbis larger than (n).(c) Noting that 101 is prime, compute337,123,878,237,982,731,602(mod 101)Show your :Your solution should be very short.(d) Describe how Fermat s Little Theorem can be used as aprimality test. Explain why it can sometimesbe used to verify that an integernis composite, but it cannot guarantee that a prime integer :(a) Here are the theorem statements and definition as they appear when typesetting usingtheorem environment in 1(Fermat s Little Theorem).Letpbe a prime andabe an integer which is not a multiple ofp. Thenap 1 1 (modp).Definition a positive integer. The Euler totient ofn, denoted (n), is the number ofpositive integers less thannwhich are relatively prime ton.

3 Equivalently, (n) is the number of 3(Euler s Theorem).Letnbe a positive integer andaan integer relatively prime ton. Thena (n) 1 (modn).(b) This allows simplifications of the computation ofab(modn), because ifb b (mod (n)),ab ab (modn). To see this, just writeb=b +t (n) for an integert, and computeab ab +t (n) ab (a (n))t ab (modn).This means we can replace a generalbwith its least residue modulo (n), an integer between 0 and (n),which will potentially be much smaller thanb.(c) In the case thatn= 101, the exponent matters only modulo 100. Since the exponent is congruentto 2 (mod 100), the answer is 32 9 (mod 101).(d) Taking the contrapositive of Fermat s little theorem, if there anaandpsuch thatap 16 1 (modp),it would follow thatpis not prime. So to test whether a number is not prime, one can simply search foranawhere this happens;a= 2 is a good starting place.

4 If you find one, it is not prime. If you can tfind any, then it is highly likely thatpis prime, but not guaranteed. In fact, there are integers that arenot prime and where no suchaexists: they are called Carmichael Letn >0 be an integer. Recall that we proved that if [a] is a unit modulon, then multiplication by[a] is a one-to-one function on the setZ/nZ.(a) Prove that if [a] and [b] are units modulon, then their product is also a unit. Conclude that multiplication by [a] is bijective map from the set of units inZ/nZto the set of units :Given that [a] has an inverse [a] 1and [b] has an inverse [b] 1modulon, can you write downan inverse for the product [a][b]?(b) Prove Euler s :You can prove it in a way very similar to our proof in lecture of Fermat s Little can also take a look at the proof on pages 82-83 on the textbook, but be sure to write yoursolution in your own :(a) Since [a] and [b] have inverses, consider the congruence class [a] 1[b] 1.

5 Then[a][b]([a] 1[b] 1) = [a][a] 1[b][b] 1= [1],and the same computation shows that ([a] 1[b] 1)[a][b] = 1. Hence [a][b] is a the multiplication by [a] map: it sends [b] [a][b]. By Part(a), if [b] is a unit then [a][b] is aswell. It is injective because iff([b]) =f([b ]) then [a][b] = [a][b ]. Multiplying by [a] 1, we see [b] = [b ].It is surjective because given a unit [b],f([a] 1[b]) = [b]. We conclude thatfgives a bijective map fromthe set of units inZ/nZto 2(b) Now letnbe a positive integer and letabe relatively prime ton. This means [a] is a unit. Let(Z/nZ) denote the set of units modulon. Remember that it contains (n) elements as having aninverse modulonmeans an integer is relatively prime ton. Consider the productP= b (Z/nZ) [b]Becausefis a bijection, the elements [a][b] =f([b]) forb (Z/nZ) are exactly the units modulon,just in a different order.

6 Therefore b (Z/nZ) [b] =P= b (Z/nZ) [a][b] = [a] (n) b (Z/nZ) [b]Canceling out theP, we seea (n) 1 (modn).4. A function :Z Zis calledmultiplicativeif (mn) = (m) (n) whenever gcd(m,n) = 1. In thisquestion we will show that Euler s totient function is multiplicative, and use this fact to derive Euler sproduct formula for (N).(a) Letp,b Z, letpbe prime andd >0. Use the definition of to compute (p), and compute (pd).(b) Letm,n Zsuch that gcd(m,n) = 1. One way to phrase the Chinese Remainder Theorem is tosay that the map(Z/mnZ) (Z/mZ) (Z/nZ)c(modnm)7 (c(modm), c(modn))is a bijection between the set (Z/mnZ) and the product of sets (Z/mZ) (Z/nZ).Show that this map also defines a bijection between the units in (Z/mnZ) and the set of pairs ofunits in (Z/mZ) (Z/nZ). In other words, show thatcis invertible modulonmif and only if it isinvertible both modulonand modulom.

7 (c) Use the result of part (b) to show that is multiplicative: if gcd(m,n) = 1, then (mn) = (n) (m).(d) Combine the results of parts (a) and (c) to show that ifNfactors as a product of primesN=pd11pd22 pdkkthen (N) =(pd1 11(p1 1))(pd2 12(p2 1)) (pdk 1k(pk 1))(e) Conclude that (N) =N(1 1p1)(1 1p2) (1 1pk)Solution:(a) First letpbe prime. Every positive integer less thanpis relatively prime top, so (p) =p 1. Likewise, the only positive integers less thanpdthat share a factor withpdare themultiples ofp:p,2p,3p, ..(pd 1)pWe countpd 1of these multiples. Therefore (pd) =pd pd 1=pd 1(p 1).(b) Recall thatais a unit modulonif and only if gcd(a,n) = 1. So ifais a unit modulomn, it doesnot share any divisors withmandnand hence is a unit modulomandn. Conversely, supposeais notinvertible modulomn. This means there is a common divisor, which we may take to be prime.

8 ThusPage 3p|aandp|mn. But this meansp|morp|naspis prime, henceashares a common divisor meansais not invertible alternative way to prove this fact: Assume that gcd(a,nm) = 1. This means that there exist integersu,vso thatau+mnv= 1. Any common divisordofaandmdivides both terms on the left-handside of this equation, and soddivides 1. Similarly any common divisor ofaandndivides 1, and weconclude that gcd(a,m) = 1 = gcd(a,n) = 1. Conversely, if gcd(a,m) = 1 and gcd(a,n) = 1 then thereare integersu,v,x,yso thatau+mv= 1andax+ny= these equations together, we find1 = (ax+ny)(au+mv) =axau+axmv+nyau+nymv=a(xau+xmv+nyu) + (mn)(yv)and we conclude that gcd(a,mn) = the Chinese Remainder Theorem, we already knew that the map(Z/mnZ) (Z/mZ) (Z/nZ)c(modnm)7 (c(modm), c(modn))is one-to-one and onto. Now we know that it maps every unitc(modmn) to a pair of units(c(modm), c(modn)),and conversely that every pair of units is in the image of a unitc(modmn).

9 We conclude that the map re-stricts to a bijection between the set of units in (Z/mnZ) and the set of pairs of units in (Z/mZ) (Z/nZ).(c) Denote the units modulonby (Z/nZ) . Since there is a bijection(Z/nmZ) '(Z/nZ) (Z/mZ) ,the two sets have the same number of elements. As an integer is a unit if and only if it relatively prime tothe modulus, (Z/nmZ) has (mn) elements while (Z/nZ) (Z/mZ) has (m) (n) elements. Notethis relied on the isomorphism given by the Chinese remainder theorem, which requiresmandnto berelatively prime.(d) Now we combine the previous parts. WriteN=pd11pd22 pdkk. Then using that is multiplicative,we see (N) = (pd11) ( ) =..= (pd11) (pd22).. (pdkk).Now using the first part about prime powers on each of the terms, we see (N) =pd1 11(p1 1)..pdk 1k(pk 1).(e) Finally pulling out apdiifrom each term, we see (N) = 11(p1 1)p 12(p2 1)..p 1k(pk 1)=N(1 p 11)(1 p 12).

10 (1 p 1k).5. (a) Definepublic key cryptography, and describe the RSA cryptosystem. Explain why the decryptionmethod will successfully recover the message in the case that gcd(m,n) = 1.(b) Explain the basis for the security of the cipher: which computations are relative efficient, and whichare computationally intractable?Page 4 Solution:(a) This is discussed in full detail at the beginning of Chapter 6 of the textbook. The keypoints are that public key cryptography is a way for Alice and Bob to communicate without having toshare any common secret and without an eavesdropper Eve being able to learn anything about whatthey are saying. RSA is the most famous example of this. Bob picks two large primespandq, andcomputesn=pq. Furthermore, Bob picks an integerewhich is invertible modulo (n) = (p 1)(q 1),and computes a multiplicative inversedmodulo (n). Bob tells everyonenande, but keepsp,q, can send a numberM(modn) to Bob by computingMe(modn).