NTIC Exercises

Exercises 12.7 Exercises

1.

Check the multiplication needed in Lemma 12.1.2.

2.

Prove the statement of Lemma 12.1.2 in the case that $\ell$ is odd. Hint: the factorization you find will be similar, but have a subtle change.

🔗

3.

Explain why the extension to Fermat's Little Theorem just before Fact 12.2.2 (or Exercise 9.6.3) is true.

🔗

4.

Check that $1729$ and $2821$ are Carmichael numbers.

🔗

5.

Find a Carmichael number of the form $7\cdot 23 \cdot p$ for a prime $p\text{;}$ include all reasoning.

🔗

6.

Use either the Fermat or Mersenne coprime facts 12.1.4,12.1.9 to provide a different proof that there are infinitely many primes.

🔗

7.

Prove that if $n$ is composite then so is $M_n\text{.}$ Hint: Exercise 12.7.2.

🔗

For the next two exercises, pick some 4-6 digit numbers that don't share a factor with

$30030=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\text{.}$

🔗

8.

Find factors of the numbers you picked using trial division (Algorithm 12.5.6).

🔗

9.

Find factors of the numbers you picked using Fermat Factorization (Algorithm 12.5.9).

🔗

10.

Try to create a number that takes five steps to factor using both Fermat and trial division. (Can you do seven steps?)

🔗

11.

Verify the last bit of the proof of The Fermat factorization algorithm.

🔗

12.

Try using the Pollard Rho factoring algorithm on a large number you create out of a few big primes (not too big!) with different seeds. Can you get it to take longer than a few turns? Get your prize numbers; now try factoring again with this method where you have changed the polynomial to $x^3+1$ or something else other than $x^2+1\text{.}$

🔗

There are many, many methods of factoring to explore! Try looking up some of them in the following exercises. Be warned that some of these are pretty deep, though there are good undergraduate-focused explanations out there for all of them.

🔗

13.

Investigate the Pollard $p-1$ algorithm. How is it similar to the methods mentioned in this chapter, how is it different? (See [C.4.19] or [C.2.10] for connecting it to Lenstra's elliptic curve algorithm.)

🔗

14.

(Hard.) Find out what a continued fraction is. Then investigate the continued fraction factorization algorithm. How is it similar to the methods mentioned in this chapter, how is it different?

🔗

15.

(Quite hard.) Find out what quadratic number field is. Then investigate the quadratic sieve factorization algorithm. How is it similar to the methods mentioned in this chapter, how is it different?