TMA4155 – Exercise 4

2011-10-17

1 – Square roots modulo primes

Find out which of the numbers 2, 5, 18, 21 have square roots modulo 23. Also find the square roots, when possible.

2 – Square roots modulo composites

Exercise 25 on page 108 in T&W.

Also, find all solutions to \(x^2 \equiv 2 \pmod{33333333333333333333333333333}\)

3 – Factorization

10001 is the product of two primes not very far apart. Find these primes. Do the same for 5688209.

4 – Factorization

With \(n=2487607\) it is a fact that \[ \begin{split} 2733^2&\equiv2^2\cdot3\cdot 7^2\cdot11\pmod{n},\\ 16007^2&\equiv2^4\cdot3\cdot11\pmod{n}. \end{split} \] Use these congruences to find a nontrivial factor of \(n\).

5 – Pollard's p−1

Read about Pollard's \(p-1\) algorithm on page 182 of T&W. Apply it to factor 253.