MATH 470 Lecture 10

« previous | Thursday, February 14, 2013 | next »

Happy feast of St. Valentine!

Homework 5 out tonight

Cyclic Groups

We've heard twice that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/p \mathbb{Z})^*} for prime Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is a cyclic group since it has a generator.

EX: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = 17} : 3 and 5 work as generators in that their powers give all elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/17\mathbb{Z})^*} .

How many generators are there?

Subgroup

A subgroup Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} of our group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is any subset closed under multiplication.

EX: {powers of 3²} form a subgroup of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/p \mathbb{Z})^*} (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{3^2, 3^4, 3^6, 3^8, 3^10, 3^12, 3^14, 3^16 \equiv 1 \}} ; 8 elements)

Observe that 3 is a generator for $(\mathbb {Z} /p\mathbb {Z} )^{*}$, 9 = 3² produces a subgroup with 8 elements 5 = 3⁵ is also a generator for $(\mathbb {Z} /p\mathbb {Z} )^{*}$

How many different powers does an element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/p \mathbb{Z})^*} …?

The multiplicative order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} in any group is the least positive Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^k} equal to the identity mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p}

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = 17} , we get

1. ORD₁₇ 3 = 16
2. ORD₁₇ 5 = 16
3. ORD₁₇ 9 = 8

Note: Number of elements in subgroup {powers of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} } of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/p \mathbb{Z})^*} is exactly the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} .

Why Care?

1. Understanding cyclic subgroups clarifies square roots mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n}
2. El Gamal cryptosystem is based on cyclic groups
3. More complicated cryptosystems (and methods for breaking them) are based on more general groups.

Returning to last lecture, we wanted to compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{11} \mod{104729}} . We found that 104729 is prime and equivalent to 1 mod 4, and thus had to use Tonelli's Algorithm:

p = 104729 g = 42 (non-square mod p) p - 1 = 2^3 \cdot 13091 e = 0: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\,g^{-e} \equiv 11^{\frac{104729-1}{2}} \equiv 1 \pmod{p} e = 0 + 2^2 = 4 h = a\,g^{-e} \equiv 11 \cdot 42^{-4} \equiv 41237 \sqrt{a} = \pm 42^2 \cdot 41237^{\frac{17092}{2}} In relation to generators, <math>(\mathbb{Z}/104729 \mathbb{Z})^*} can be broken into two subgroups: {gen^{even power}} and {gen ^{odd power}}. Even powers are squares, odd powers are non-squares.

(ZZ/pZZ)*
  |-- {gen ^ (even power)}
  |   |-- {gen ^ (multiple of 4)}
  |   |   |-- {gen ^ (multiple of 8)}
  |   |   |-- ...
  |   |   `-- {gen ^ (k + multiple of 8)}, where k in {1,...,7}
  |   `-- {gen ^ (2 + multiple of 4) }
  `-- {gen ^ (odd power)}
      |-- {gen ^ (1 + multiple of 4)}
      |   `-- ...
      `-- {gen ^ (3 + multiple of 4)}
          `-- ...

Generating Random Prime Numbers

Fundamental Theorem of Arithmetic: There are infinitely many primes

The Prime Number Theorem: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x \to \infty} \frac{\pi(x)}{\frac{x}{\ln{x}}} = 1}

We can do better:

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{Li}(x) = \int_2^x \frac{\mathrm{d}t}{\ln{t}}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x \to \infty} \frac{\mathrm{Li}(x)}{\frac{x}{\ln{x}}} = 1}

And Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| \mathrm{Li}(x) - \pi(x) \right|} is actually tighter than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| \frac{x}{\ln{x}} - \pi(x) \right|} .

In 1901, Von Koch showed that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{x}{\ln{x}} < \pi(x) < 1.25506 \, \frac{x}{\ln{x}}}

That is, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x) \in \Theta\left(\frac{x}{\ln{x}}\right)}

This implies an easy way to generate random primes: Pick random numbes in {1, …, N} and check primality!

Analysis

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{uniformly random } x \in \{1, \ldots, n\}] = \frac{\text{number of primes in range}}{n} = \frac{\pi(n)}{n}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to \infty} \frac{\pi(n)}{n} = \frac{1}{\ln{n}}} , so we actually have a pretty good chance.

Pr[\text{random non-square} a \in \{1, \ldots, p-1\}] = \frac{1}{2}

In Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} trials, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{picking a prime in } \{1, \ldots, n\}] = 1 - \frac{n}{k}}

Testing Primality

How do you test primality?

Primality vs. factoring :: decision vs. enumeration

We know how to decide primality for any integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\ln^6{n})} . However, we still do not know how to factor any faster than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{e}^{O\left( \sqrt{3}{\ln{n}} \, (\ln{(\ln(\ln{n}))})^{\frac{2}{3}} \right)}}

By Fermat's Little Theorem, we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{p-1} \equiv 1 \pmod{p}} if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is prime and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \nmid a} .

If the converse holds, maybe we can use it as a primality test—sometimes works

• Carmichael numbers break this (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = 561} yields Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{560} \equiv 1 \pmod{561}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \{1,\ldots,560\}} , but 561 = 3 &midot; 11 · 17

Solovay-Strassen Theorem

(1977; maybe Kraitchick & Lehmer earlier...)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} odd and composite → more than half of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \{1, \ldots, n-1\}} satisfy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \frac{a}{n} \right) \ne a^{\frac{n-1}{2}}}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \frac{a}{n} \right)} is the Jacobi symbol: it allows Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} to be composite (non-prime)

This theorem yields a fast (randomized) primality check:

1. pick a few random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \{1, \ldots, n\}}
2. check whether Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \frac{a}{n} \right) = a^{\frac{n-1}{2}}} .
3. If any are not equal, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is composite.
4. Otherwise, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is probably prime