Intro To Cryptography - Chapter 1

Problem 1.19

Suppose that $g^a \equiv 1 \mod m$ and that $g^b \equiv 1 \mod m$. Prove that

$$ g^{\gcd(a,b)} \equiv 1 \mod m.$$

Proof: By Theorem 1.11 we know there exist $u, v \in \mathbb{Z}$ such that
$$\gcd(a,b) = au + bv.$$
Therefore
$$g^{\gcd(a,b)} \ = \ g^{au + bv} \ = \ g^{au}\cdot g^{bv} \ = \ (g^a)^u\cdot(g^b)^v $$
and, repeatedly applying the multiplication rule in Proposition 1.13.a, we find that
$$g^{\gcd(a,b)} \ = \ (g^a)^u \cdot (g^b)^v \ \equiv \ 1^u \cdot 1^v \ \equiv \ 1 \mod m.$$

Problem 1.20

Prove that if $a_1$ and $a_2$ are units modulo $m$, then $a_1a_2$ is a unit modulo $m$.

Proof: Suppose $a_1, a_2$ are units modulo $m$. Then there exist inverses $a_1^{-1}, a_2^{-1}$ such that
$$a_1 \dot a_1^{-1} \equiv 1 \mod m \qquad \text{and} \qquad a_2 \dot a_2^{-1} \equiv 1 \mod m.$$
It follows that
$$(a_1a_2)(a_1^{-1}a_2^{-1}) \ = \ (a_1a_1^{-1})(a_2a_2^{-1}) \ \equiv \ 1 \cdot 1 \ \equiv \ 1 \mod m,$$
where the congruences modulo $m$ follow again from Proposition 1.13.a. Since we have found an inverse $a_1^{-1}a_2^{-1}$, we conclude that $a_1a_2$ is a unit modulo $m$.

Citing Proposition 1.13.a is getting old fast. Let's assume it implicitly from here on out.

Problem 1.23

Let $m$ be an odd integer and $a$ be any integer. Prove that $2m + a^2$ can never be a perfect square.

Proof: First, a small lemma: if $s$ is a perfect square, then $s \mod 4 \in \{0, 1\}$. To see why, let $s = n^2$. Of course, $n \mod 4 \in \{0, 1, 2, 3\}$, so if we consider each case:

$$ n \equiv 0 \mod 4 \implies n^2 \equiv 0 \mod 4 $$

$$ n \equiv 1 \mod 4 \implies n^2 \equiv 1 \mod 4 $$

$$ n \equiv 2 \mod 4 \implies n^2 \equiv 0 \mod 4 $$

$$ n \equiv 3 \mod 4 \implies 3^2 \equiv 1 \mod 4 $$

and we see that $n^2 \mod 4 \in \{0, 1\}$, proving the lemma.
Next, since $m$ is odd, let $m = 2k + 1$ for some $k \in \mathbb{Z}$. Then

$$ 2m \ = \ 2(2k + 1) \ = \ 4k + 2 \ \equiv \ 2 \mod 4.$$

and it follows that

$$ 2m + a^2 \ \equiv \ 2 + a^2 \mod 4.$$

We also know $a^2 \mod 4 \in \{0, 1\}$ from the lemma, hence

$$ 2m + a^2 \mod 4 \in \{2, 3\}.$$

However, notice the contrapositive of the lemma now implies that $2m + a^2$ is not a perfect square, thus completing the proof.

Problem 1.32

For each of the following primes $p$ and numbers $a$, compute $a^{-1} \mod p$ in two ways: (i) the extended Euclidean algorithm and (ii) the fast power algorithm & Fermat's little theorem.

(a): $p = 47$ and $a = 11$

(i) Euclidean algorithm:

1. $11 = 47(0) + 11$
2. $47 = 11(4) + 3$
3. $11 = 3(3) + 2$
4. $3 = 2(1) + 1$
5. $2 = 1(2)$

Working backwards from the fourth step,

1. $1 = -2(1) + 3$
2. $1 = -(11-3\cdot3)(1) + 3$
3. $1 = -(11-(47-11\cdot4)^2) + (47-11\cdot4)$
4. $1 = -11 + 47^2 - 2\cdot47\cdot11\cdot4 + 11^2\cdot4^2 + 47 - 11\cdot4$
5. $1 = 47(47 - 2\cdot11\cdot4 + 1) + 11(-1 + 11\cdot4^2 - 4)$
6. $1 \equiv 11\cdot171 \mod 47$
7. $11^{-1} = 171 \equiv 30 \mod 47$

(ii) fast power algorithm:
By Fermat's little theorem, we know $11^{-1} \equiv 11^{45} \mod 47$. For the fast powering algorithm, we first decompose $45 = 2^5 + 2^3 + 2^2 + 2^0$. And then we compute:

0. $11^{2^0} \equiv 11$
1. $11^{2^1} \equiv 11^2 \equiv 27$
2. $11^{2^2} \equiv 27^2 \equiv 24$
3. $11^{2^3} \equiv 24^2 \equiv 12$
4. $11^{2^4} \equiv 12^2 \equiv 3$
5. $11^{2^5} \equiv 3^2 \equiv 9$

Then
$$ \begin{align*} 11^{-1} \equiv 11^{45} \equiv 11^{2^5 + 2^3 + 2^2 + 2^0} &\equiv 11^{2^5}\cdot11^{2^3}\cdot11^{2^2}\cdot11^{2^0} \\ &\equiv 9\cdot12\cdot24\cdot11 \\ &\equiv 30 \mod 47 \end{align*} $$

(b): $p = 587$ and $a = 345$

(i) Euclidean algorithm:

1. $345 = 587(0) + 345$
2. $587 = 345(1) + 242$
3. $345 = 242(1) + 103$
4. $242 = 103(2) + 36$
5. $103 = 36(2) + 31$
6. $36 = 31(1) + 5$
7. $31 = 5(6) + 1$

Working backwards,
7. $1 = 31 - 6 \cdot5$
6. $1 = 31 - 6(36 - 31)$
6. $1 = -6\cdot36 + 7\cdot31$
5. $1 = -6\cdot36 + 7\cdot(103 - 2\cdot36)$
5. $1 = 7 \cdot 103 + (-6 - 7\cdot2)\cdot 36$
5. $1 = 7 \cdot 103 - 20\cdot 36$
4. $1 = 7\cdot103 - 20\cdot(242 - 2\cdot103)$
4. $1 = -20\cdot242 + (7+20\cdot2)\cdot103$
4. $1 = -20\cdot242 + 47\cdot103$
3. $1 = -20\cdot242 + 47\cdot(345 - 242)$
3. $1 = 47\cdot345 + (-20-47)\cdot 242$
3. $1 = 47\cdot345 - 67\cdot 242$
2. $1 = 47\cdot345 - 67\cdot (587 - 345)$
2. $1 = (47+67)\cdot345 - 67\cdot 587$
2. $1 = 114\cdot345 - 67\cdot 587$
2. $1 \equiv 114\cdot345 \mod 587$
2. $345^{-1} \equiv 114 \mod 587$.

(ii) fast power algorithm:
By Fermat's little theorem, we know $345^{-1} \equiv 345^{585} \mod 587$. For the fast powering algorithm, we first decompose $585 = 2^9 + 2^6 + 2^3 + 2^0$. And then we compute:

0. $345^{2^0} \equiv 345$
1. $345^{2^1} \equiv 345^2 \equiv 451$
2. $345^{2^2} \equiv 451^2 \equiv 299$
3. $345^{2^3} \equiv 299^2 \equiv 177$
4. $345^{2^4} \equiv 177^2 \equiv 218$
5. $345^{2^5} \equiv 218^2 \equiv 564$
6. $345^{2^6} \equiv 564^2 \equiv 529$
7. $345^{2^7} \equiv 529^2 \equiv 429$
8. $345^{2^8} \equiv 429^2 \equiv 310$
9. $345^{2^9} \equiv 310^2 \equiv 419$

Then
$$\begin{align*}345^{-1} \equiv 345^{585} \equiv 345^{2^9 + 2^6 + 2^3 + 2^0} &\equiv 345^{2^9}\cdot345^{2^6}\cdot345^{2^3}\cdot345^{2^0} \\ &\equiv 419\cdot529\cdot177\cdot345 \\ &\equiv 114 \mod 587. \end{align*}$$

(c): $p = 104801$ and $a = 78467$

(i) Euclidean algorithm:

1. $104801 = 78467(1) + 26334$
2. $78467 = 26334(2) + 25799$
3. $26334 = 25799(1) + 535$
4. $25799 = 535(48) + 119$
5. $535 = 119(4) + 59$
6. $119 = 59(2) + 1$

Working backwards,

6. $1 = 119 - 2\cdot59$
7. $1 = 119 - 2\cdot(535-4\cdot119)$
8. $1 = -2\cdot535 + 9\cdot119$
9. $1 = -2\cdot535 + 9\cdot(25799-48\cdot535)$
10. $1 = 9\cdot25799 -(2+9\cdot48)\cdot535$
11. $1 = 9\cdot25799 -434\cdot535$
12. $1 = 9\cdot25799 -434\cdot(26334-25799)$
13. $1 = -434\cdot26334 + (9+434)\cdot25799$
14. $1 = -434\cdot26334 + 443\cdot25799$
15. $1 = -434\cdot26334 + 443\cdot(78467-2\cdot26334)$
16. $1 = 443\cdot78467 - (434 + 443\cdot2)\cdot 26334$
17. $1 = 443\cdot78467 - 1320\cdot 26334$
18. $1 = 443\cdot78467 - 1320\cdot (104801 - 78467)$
19. $1 = (443 + 1320)\cdot78467 - 1320\cdot 104801$
20. $1 = 1763\cdot78467 - 1320\cdot 104801$
21. $1 \equiv 1763\cdot78467 \mod 104801$
22. $78467^{-1} \equiv 1763 \mod 104801$

(ii) fast power algorithm:
The program below uses the fast power algorithm and Fermat's little theorem. Given inputs cargo run -- 78467 104801, it correctly outputs inverse: 1763.

pub fn main() {
    if std::env::args().len() != 3 {
        eprintln!("usage: cargo run --bin fast_power <a> <p>");
        return;
    }
    let a: u64 = std::env::args().nth(1).unwrap().parse().unwrap();
    let p: u64 = std::env::args().nth(2).unwrap().parse().unwrap();

    // decompose exponent into powers of 2
    let mut e = p - 2;
    let mut exp = 0;
    let mut power_idx = vec![];
    loop {
        while 2_i32.pow(exp as u32) <= e as i32 {
            exp += 1;
        }
        power_idx.push((exp - 1) as u64);
        e -= 2_i32.pow((exp - 1) as u32) as u64;
        if e == 0 {
            break;
        }
        exp = 0;
    }

    // check decomposition was successful
    let check_e = power_idx
        .iter()
        .fold(0, |tot, i| tot + 2_i32.pow(*i as u32));
    assert_eq!(check_e as u64, p - 2);

    let max_ix = *power_idx.first().unwrap();

    // build out the table
    let mut curr = a;
    let mut powers = vec![curr];
    for _ in 1..=max_ix {
        curr = (curr * curr) % p;
        powers.push(curr);
    }

    let inv = power_idx
        .iter()
        .fold(1, |curr, i| curr * powers[*i as usize] % p);

    assert_eq!(inv * a % p, 1);

    println!("inverse: {}", inv);
}

Problem 1.34

Recall that $g$ is called a primitive root modulo $p$ if the powers of $g$ give all nonzero elements of $\mathbb{F}_p$.

• (a) For which of the following primes is 2 a primitive root modulo $p$?

  1. $p = 7$: false
  2. $p = 13$: true
  3. $p = 19$: true
  4. $p = 23$: false
  • Source:

  pub fn main() {
      let b: i64 = std::env::args().nth(1).unwrap().parse().unwrap();
      let p: u64 = std::env::args().nth(2).unwrap().parse().unwrap();
      for e in 1..p {
          println!("{}^{}: {}", b, e, b.pow(e as u32) % p as i64);
      }
  }
  

• (b) For which of the following is 3 a primitive root modulo $p$?

  1. $p = 5$: true
  2. $p = 7$: true
  3. $p = 11$: false
  4. $p = 17$: true
  • Source: see above

• (c): Find a primitve root for each of the following primes

  1. $p = 23$: $g = 5$
  2. $p = 29$: $g = 2$
  3. $p = 41$: $g = 6$
  4. $p = 43$: $g = 3$
  • Source:

  pub fn main() {
      let p: u32 = std::env::args().nth(1).unwrap().parse().unwrap();
      'generator: for g in 1..p {
          for e in 1..(p - 1) {
              if mod_pow(g, e, p) == 1 {
                  continue 'generator;
              }
          }
          println!("{} is a generator for Z_{}", g, p);
          break;
      }
  }
  
  fn mod_pow(base: u32, exp: u32, modulus: u32) -> u32 {
      let mut out = 1;
      for _ in 0..exp {
          out = out * base % modulus
      }
      out
  }