Scribd
Upload
5 views2 pages

Homework 14

The document is an exercise sheet for a course on Number Theory and Cryptography, containing seven exercises that cover various topics such as divisibility, modular arithmetic, and the Diffie-Hellman key exchange. Exercises include proving divisibility properties, solving modular equations, and applying Shor's algorithm for factoring specific numbers. The document is intended for review purposes in a mathematics course at a New York institution.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Homework 14

The document is an exercise sheet for a course on Number Theory and Cryptography, containing seven exercises that cover various topics such as divisibility, modular arithmetic, and the Diffie-Hellman key exchange. Exercises include proving divisibility properties, solving modular equations, and applying Shor's algorithm for factoring specific numbers. The document is intended for review purposes in a mathematics course at a New York institution.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Number Theory and Cryptography

Math UN3020
New York, 2023/04/26

Exercise Sheet 14

Review exercises

Exercise 1. Prove that, for all n ∈ Z, n ≥ 0, we have

3 | 22n+1 + 1 .

Exercise 2. Solve the following equation

x21 ≡ 1 (mod 31)

Exercise 3. Alice and Bob are exchanging a key using the Diffie-Helmann algorithm. Eve
spies their communications. Assume they use p = 47, g = 5. They exchange the numbers
X = 38, Y = 3. What is the key k?

1
Exercise 4. Use Shor’s algorithm to factor the number 7097.
(Hint: 2 has order 345 modulo 7097. 3 has order 1150 modulo 7097.)

Exercise 5. Use Shor’s algorithm to factor the number 3551.


(Hint: 2 has order 1716 modulo 3551, 3 has order 572 modulo 3551.)

Exercise 6. Show that, if p > 3 is a prime, then

p2 ≡ 1 (mod 24) .

(Hint: Use the Chinese remainder theorem, 24 = 23 3.)

Exercise 7. Prove that there exists infinitely many positive integers n such that 4n2 + 1 is
divisible both by 17 and 29.
(Hint:) use modular arithmetic.

You might also like