Practice Exam 2 PDF

Preview

Summary

Practice Exam 2...

Description

Practice Questions April 2, 2021 1.

Given that 31 is of order 343 = 73 in F1373 , solve 31x ≡ 331 (mod 1373) using the following data. 317 ≡ 751 3115 ≡ 249 3149 ≡ 428 249−1 ≡ 783 4282 ≡ 575,

(mod (mod (mod (mod

4283 ≡ 333,

3317 ≡ 703 33115 ≡ 1213 33149 ≡ 428 751−1 ≡ 1075

1373) 1373) 1373) 1373)

4284 ≡ 1105,

1

4285 ≡ 628,

(mod 1373) (mod 1373) (mod 1373) (mod 1373)

4286 ≡ 1049 (mod 1373)

2.

Bob publishes his RSA public key (N, e) = (187, 7). (a) Alice wants to send Bob the message m = 8. What ciphertext does Alice send to Bob?

(b) Find Bob’s decryption exponent d.

(c) Bob receives the ciphertext c = 15, write down the expression that yields the plaintext. (You do not need to calculate the plaintext completely.)

2

3.

(a) The following congruence holds: 789495 ≡ 8154

(mod 15841)

Using the data above, check whether a = 789 is a Miller-Rabin witness for n = 15841. What can you conclude about the primality of 15841?

(b) The following congruences hold: 12313001 ≡ 123 56713001 ≡ 567

34513001 ≡ 345 78913001 ≡ 789

(mod 13001) (mod 13001)

(mod 13001) (mod 13001)

Using the data above, apply Fermat’s Primality Test to n = 13001. What can you conclude about the primality of 13001?

3

4.

The number 3827 = p · q is a product of two primes. Given that (p − 1)(q − 1) = 3696, use this information to determine p and q .

4

5.

The integer p = 1277 is prime and g = 31 is primitive modulo 1277. Suppose we have found that 3187 ≡ 180

(mod 1277)

278

31 ≡ 600 31714 ≡ 15

(mod 1277) (mod 1277)

19 · 311002 ≡ 540

(mod 1277)

Use the above data and the Index Calculus Method to solve 31x ≡ 19 (mod 1277).

5

6.

Use Pollard’s p − 1 Factorization Algorithm with a = 2 to factor N = 17653. Stop at 7 factorial even if you have not found the answer.

6

7.

The integer N = 125449 is a product of two distinct primes. Suppose we have found that 4932 ≡ 25 · 3 · 52 · 72 2

6

(mod 125449)

2

778 ≡ 2 · 3 · 7 · 11 10792 ≡ 27 · 52 · 11

(mod 125449) (mod 125449)

11772 ≡ 2 · 5 · 72 · 11 14582 ≡ 22 · 5 · 72 · 112

(mod 125449) (mod 125449)

(a) Find positive integers a and b such that a2 ≡ b2 (mod 125449) and a 6≡ ±b (mod 125449).

(b) Use your findings in part (a) to factor N = 125449.

7...