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 $(\mathbb {Z} /p\mathbb {Z} )^{*}$ for prime $p$ is a cyclic group since it has a generator.

EX: $p=17$: 3 and 5 work as generators in that their powers give all elements in $(\mathbb {Z} /17\mathbb {Z} )^{*}$.

How many generators are there?

Subgroup

A subgroup $H$ of our group $G$ is any subset closed under multiplication.

EX: {powers of 3²} form a subgroup of $(\mathbb {Z} /p\mathbb {Z} )^{*}$ ($\{3^{2},3^{4},3^{6},3^{8},3^{1}0,3^{1}2,3^{1}4,3^{1}6\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 $(\mathbb {Z} /p\mathbb {Z} )^{*}$ …?

The multiplicative order of $a$ in any group is the least positive $k$ with $a^{k}$ equal to the identity mod $p$

For $p=17$, we get

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

Note: Number of elements in subgroup {powers of $a$} of $(\mathbb {Z} /p\mathbb {Z} )^{*}$ is exactly the order of $a$ mod $p$.

Why Care?

1. Understanding cyclic subgroups clarifies square roots mod $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 ${\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: $a\,g^{-e}\equiv 11^{\frac {104729-1}{2}}\equiv 1{\pmod {p}}e=0+2^{2}=4h=a\,g^{-e}\equiv 11\cdot 42^{-4}\equiv 41237{\sqrt {a}}=\pm 42^{2}\cdot 41237^{\frac {17092}{2}}Inrelationtogenerators,<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: $\lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\ln {x}}}}=1$

We can do better:

Let $\mathrm {Li} (x)=\int _{2}^{x}{\frac {\mathrm {d} t}{\ln {t}}}$.

$\lim _{x\to \infty }{\frac {\mathrm {Li} (x)}{\frac {x}{\ln {x}}}}=1$

And $\left|\mathrm {Li} (x)-\pi (x)\right|$ is actually tighter than $\left|{\frac {x}{\ln {x}}}-\pi (x)\right|$.

In 1901, Von Koch showed that ${\frac {x}{\ln {x}}}<\pi (x)<1.25506\,{\frac {x}{\ln {x}}}$

That is, $\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

$Pr[{\text{uniformly random }}x\in \{1,\ldots ,n\}]={\frac {\text{number of primes in range}}{n}}={\frac {\pi (n)}{n}}$

$\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 $k$ trials, $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 $n$ in time $O(\ln ^{6}{n})$ . However, we still do not know how to factor any faster than $\mathrm {e} ^{O\left({\sqrt {3}}{\ln {n}}\,(\ln {(\ln(\ln {n}))})^{\frac {2}{3}}\right)}$

By Fermat's Little Theorem, we know that $a^{p-1}\equiv 1{\pmod {p}}$ if $p$ is prime and $p\nmid a$.

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

• Carmichael numbers break this (e.g. $p=561$ yields $a^{560}\equiv 1{\pmod {561}}$ for all $a\in \{1,\ldots ,560\}$, but 561 = 3 &midot; 11 · 17

Solovay-Strassen Theorem

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

$n$ odd and composite → more than half of the $a\in \{1,\ldots ,n-1\}$ satisfy $\left({\frac {a}{n}}\right)\neq a^{\frac {n-1}{2}}$

Where $\left({\frac {a}{n}}\right)$ is the Jacobi symbol: it allows $n$ to be composite (non-prime)

This theorem yields a fast (randomized) primality check:

1. pick a few random $a\in \{1,\ldots ,n\}$
2. check whether $\left({\frac {a}{n}}\right)=a^{\frac {n-1}{2}}$.
3. If any are not equal, $n$ is composite.
4. Otherwise, $n$ is probably prime