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{\mathbb{Z}}/p\mathbb{\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{\mathbb{Z}}/17\mathbb{\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{\mathbb{Z}}/p\mathbb{\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{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$, 9 = 3² produces a subgroup with 8 elements 5 = 3⁵ is also a generator for $(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$

How many different powers does an element of $(\mathbb{\mathbb{Z}}/p\mathbb{\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{\mathbb{Z}}/p\mathbb{\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}mod104729$. 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(\mathrm{mod}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{\mathbb{Z}}/104729\mathbb{\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: $\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)}{\frac{x}{\ln x}}=1$

We can do better:

Let $\mathrm{L}\mathrm{i}(x)=\underset{2}{\overset{x}{\int }}\frac{\mathrm{d}t}{\ln t}$.

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\mathrm{L}\mathrm{i}(x)}{\frac{x}{\ln x}}=1$

And $|\mathrm{L}\mathrm{i}(x)-\pi (x)|$ is actually tighter than $|\frac{x}{\ln x}-\pi (x)|$.

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

That is, $\pi (x)\in \mathrm{\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,\dots ,n\}]=\frac{\text{number of primes in range}}{n}=\frac{\pi (n)}{n}$

$\underset{n\to \mathrm{\infty }}{\lim }\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,\dots ,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(\sqrt{3}\ln n(\ln (\ln (\ln n)){)}^{\frac{2}{3}})}$

By Fermat's Little Theorem, we know that $a^{p-1}\equiv 1(\mathrm{mod}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(\mathrm{mod}561)$ for all $a\in \{1,\dots ,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,\dots ,n-1\}$ satisfy $\left(\frac{a}{n}\right)\ne 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,\dots ,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