91Ó°ÊÓ

Decrypt these messages encrypted using the shift cipher \(f(p)=(p+10) \bmod 26 .\) a) CEBBOXNOB XYG b) LO WIPBSOXN c) DSWO PYB PEX

Show that if \(a\) and \(m\) are relatively prime positive integers, then the inverse of \(a\) modulo \(m\) is unique modulo \(m .[\text { Hint: Assume that there are two solutions } b \text { and } c \text { of }\) the congruence \(a x \equiv 1(\bmod m) .\) Use Theorem 7 of Section 4.3 to show that \(b \equiv c(\bmod m) . ]\)

Express in pseudocode the trial division algorithm for determining whether an integer is prime.

Prove or disprove that if \(a | b c,\) where \(a, b,\) and \(c\) are positive integers and \(a \neq 0,\) then \(a | b\) or \(a | c .\)

Write an algorithm in pseudocode for generating a sequence of pseudorandom numbers using a linear congruential generator. The middle-square method for generating pseudorandom numbers begins with an \(n\) -digit integer. This number is squared, initial zeros are appended to ensure that the result has 2\(n\) digits, and its middle \(n\) digits are used to form the next number in the sequence. This process is repeated to generate additional terms.

Show that an inverse of \(a\) modulo \(m,\) where \(a\) is an integer and \(m > 2\) is a positive integer, does not exist if \(\operatorname{gcd}(a, m) > 1\)

Prove that if \(a\) and \(b\) are nonzero integers, \(a\) divides \(b,\) and \(a+b\) is odd, then \(a\) is odd.

Show that if \(2^{m}+1\) is an odd prime, then \(m=2^{n}\) for some nonnegative integer \(n .[\text { Hint: First show }\) that the polynomial identity \(x^{m}+1=\left(x^{k}+1\right)\left(x^{k(t-1)}-\right.\) \(x^{k(t-2)}+\cdots-x^{k}+1 ) \quad\) holds, where \(m=k t\) and \(t\) is odd. \(]\)

What is the decryption function for an affine cipher if the encryption function is \(c=(15 p+13) \bmod 26 ?\)

Convert \((1100001100011)_{2}\) from its binary expansion to its hexadecimal expansion.