Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

Finish all investigations from in-class activities.

2.

Use Exercise 5.6.10 to construct two different number tricks mod 73. That is, find two different pairs of \(s\) and \(d\) such that \((x^s)^d \equiv x \pmod{31}\) for all \(x\) mod 73.

3.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that

1. \(x^a=x \pmod{14}\) for all \(x\) mod 14.
2. \(x^a=x \pmod{26}\) for all \(x\) mod 26.
3. \(x^a=x \pmod{34}\) for all \(x\) mod 34.
4. \(x^a=x \pmod{38}\) for all \(x\) mod 38.
5. \(x^a=x \pmod{46}\) for all \(x\) mod 46.
6. Make a conjecture!

4.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that

1. \(x^a=x \pmod{15}\) for all \(x\) mod 15.
2. \(x^a=x \pmod{21}\) for all \(x\) mod 21.
3. \(x^a=x \pmod{33}\) for all \(x\) mod 33.
4. \(x^a=x \pmod{39}\) for all \(x\) mod 39.
5. \(x^a=x \pmod{51}\) for all \(x\) mod 51.
6. Make a conjecture!

5.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that \(x^a=x \pmod{35}\) for all \(x\) mod 35. (This means try enough values of \(a\) until you can identify the pattern. )

6.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that

1. \(x^a=x \pmod{55}\) for all \(x\) mod 55.
2. \(x^a=x \pmod{77}\) for all \(x\) mod 77.
3. \(x^a=x \pmod{143}\) for all \(x\) mod 143.
4. \(x^a=x \pmod{221}\) for all \(x\) mod 221.
5. \(x^a=x \pmod{323}\) for all \(x\) mod 323.

7.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that \(x^a=x \pmod{105}\) for all \(x\) mod 105. (This means try enough values of \(a\) until you can identify the pattern. ) This is a different case from most of your other examples. Why? Can you expand your conjecture to include this case?

8.

Use the Sage code in Sage Computation 5.11.2 to list all \(n\) between 6 and 35 where there is NO \(a>1\) such that \(x^a=x \bmod{n}\) for all \(x\) mod n. Make a conjecture!

9.

Use the Sage code in Sage Computation 5.11.2 to answer the following.

1. Can you find an \(a>1\) such that \(2^a=2 \bmod{9}\) for all \(x\) mod 9?
2. Can you find an \(a>1\) such that \(3^a=3 \bmod{9}\) for all \(x\) mod 9?
3. Can you find an \(a>1\) such that \(4^a=4 \bmod{9}\) for all \(x\) mod 9?
4. Can you find an \(a>1\) such that \(5^a=5 \bmod{9}\) for all \(x\) mod 9?
5. Can you find an \(a>1\) such that \(6^a=6 \bmod{9}\) for all \(x\) mod 9?
6. Can you find an \(a>1\) such that \(7^a=7 \bmod{9}\) for all \(x\) mod 9?
7. Can you find an \(a>1\) such that \(8^a=8 \bmod{9}\) for all \(x\) mod 9?
8. What do you notice?

10.

Use Theorem 5.5.8 to prove that if \(p\) is a prime and \(a=1+(p-1)k\) for an integer \(k\) then \(x^a \equiv x \pmod{p}\) for all \(x\text{.}\) There should be two cases for \(x\text{.}\) Case 1: \(\gcd(x,p)=1\text{.}\) Case 2: \(\gcd(x,p) \neq 1\text{.}\)

11.

Write a small program (using a for loop) in Sage with a variable, \(p\) for a prime number that checks the factorization of \(1+(p-1)k\) for at least 10 different values of \(k\text{.}\) For example, the command factor(10) will factor 10 into prime factors. You may initialize \(p\) with a prime number of your choice.

12.

Explain how to use Exercise 5.6.10 to construct number tricks mod \(p\) for a prime \(p\text{.}\) Give an example of creating your own number trick for a prime \(p\) of your choice.

13.

In the computational exercises, you explored many cases for when there are values for \(a>1\) such that \(x^a=x \bmod{n}\) for all \(x\) mod \(n\) and what the pattern for those \(a\) values are when \(n\) is not prime. Write up the conjectures you have. Try to combine them into a single conjecture if possible!

14.

Here's a new number trick algorithm. The encryption algorithm is \(E(x):y \equiv x^7 \bmod 55\text{.}\) The decryption algorithm is \(D(y):x=y^{23} \bmod 55\text{.}\) Explain why the number trick works. (Remember that you found all \(a\) such that \(x^a \equiv x \bmod 55\) above.)

15.

Recall that \(\phi(n)\) counts all the numbers, \(a\) between 1 and \(n\) such that \(\gcd(a,n)=1\text{.}\) Compute \(\phi(2*3)\text{,}\) \(\phi(2*5)\text{,}\) \(\phi(2*7)\text{,}\) \(\phi(2*11)\text{,}\) \(\phi(2*13)\text{.}\) Make a conjecture for a formula for \(\phi(2q)\) where \(q\) is an odd prime. Prove it.

16.

Compute \(\phi(3*5)\text{,}\) \(\phi(3*7)\text{,}\) \(\phi(3*11)\text{,}\) \(\phi(3*13)\text{.}\) Make a conjecture for a formula for \(\phi(3q)\) where \(q\) is a prime other than 3. Prove it.

17.

Create your own examples and calculate \(\phi(pq)\) when \(p>3\) and \(q>3\) are distinct primes. Make a conjecture!

18.

Read the article by Diffie-Hellman providing the foundation for public key cryptography http://ee.stanford.edu/~hellman/publications/24.pdf and write a paragraph about something interesting you learned.