Exam 4: Number Theory and Cryptography

Find the prime factorization of 510,510.

Prove or disprove: $\text { If } p \text { and } q \text { are primes ( } > 2 \text { ), then } p q + 1 \text { is never prime. }$

Find $50 ! \bmod 49 ! .$

Decrypt the message "AHFXVHFBGZ" that was encrypted using the shift cipher $f ( x ) = ( x + 19 ) \bmod 26 .$

Find $a \operatorname { div } m \text { and } a \bmod m \text { when } a = - 33 , m = 67$

Explain in words the difference between a|b and $\frac { b } { a }$

Encrypt the message "just testing" using the function $f ( x ) = ( 5 x + 3 ) \bmod 26$

Encrypt the message WATCH OUT using blocks of four letters and the transposition cipher based on the permutation of {1,2,3,4} with $\sigma ( 1 ) = 3 , \sigma ( 2 ) = 4 , \sigma ( 3 ) = 2 ,$ and $\sigma ( 4 ) = 1$ .

Prove or disprove: For all integers a, b, c, d, if a|b and c|d, then $( a + c ) \mid ( b + d )$

Find the two's complement of 9.

Suppose that a computer has only the memory locations 0, 1, 2, . . . , 19. Use the hashing function h where $h ( x ) = ( x + 5 ) \bmod 20$ to determine the memory locations in which 57, 32, and 97 are stored.

Find the sequence of pseudorandom numbers generated by the power generator $x _ { n + 1 } = x _ { n } ^ { 3 } \bmod 23$ and seed x0 = 3. The numbers in question 130-133 refer to an 8-digit student id at a large university. The eighth digit is a check digit equal to the sum of the first seven digits modulo 7.

Find the prime factorization of 45,617.

Use the Euclidean Algorithm to find gcd(580, 50).

Convert (6253)₈ to base 2 .

find the sum and product of each of these pairs of numbers. Express your answer as an octal expansion. - $( 371 ) _ { 8 } , ( 624 ) _ { 8 }$

Suppose that the lcm of two numbers is 400 and their gcd is 10. If one of the numbers is 50, find the other number.

Find an inverse of 2 modulo 31.

suppose that a and b are integers, $a \equiv 4 ( \bmod 7 ) , \text { and } b \equiv 6 ( \bmod 7 ) . \text { Find the integer } c \text { with } 0 \leq c \leq 6$ such that - $c \equiv 3 a ( \bmod 7 )$

Find an inverse of 6 modulo 7.