MATH 470 Lecture 12

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

Homework Questions

$\sqrt{11}(\mathrm{mod}10949)$

$\left(\frac{11}{10949}\right)=\left(\frac{10949}{11}\right)=\left(\frac{4}{11}\right)=1$

Tonelli:

Use $g=2$ as non-square.

$p-1=2^2\cdot 2737$, so $(s,t)=(2,2737)$

Only one iteration of loop with $e=0$

$11\cdot 2^{-0}{)}^{\frac{p-1}{4}}=-1$, so $e=2$

$h=\frac{11}{2^2}=2740(\mathrm{mod}10949)$

$\sqrt{11}=\pm g^{\frac{e}{2}}{h}^{\frac{t+1}{2}}=2\cdot 2740^{1369}(\mathrm{mod}10949)=\pm 234$

Riemann Hypothesis

$|\pi (x)-\mathrm{L}\mathrm{i}(x)|=O(\sqrt{x}\ln x)$ $|\pi (x)-\mathrm{L}\mathrm{i}(x)|<\frac{\sqrt{x}\ln x}{4\tau }\mathrm{\forall }x\ge 2657$

Generalized Riemann Hypothesis

For primes in arithmetic progression

$|\pi (x;n,a)-\frac{\mathrm{L}\mathrm{i}(x)}{\varphi (n)}|<\sqrt{x}(\ln x+2\ln n)\mathrm{\forall }x\ge 2$

Rabin's Variant of RSA

Provably as hard to break as factoring certain integers (RSA might be easier to break than factoring, but just don't know this for sure).

Rabin's variant makes for good midterm and homework questions!!

1. Pick distinct primes $p$ and $q$ with roughly the same number of digits
2. Compute $n$ and publish it, but keep $p$ and $q$ secret
3. Bob encrypts a message $m\in (\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}})$ via $c=m^2(\mathrm{mod}n)$ —simple!
4. Alice solves $\{\begin{array}{l}{x}^2\equiv c(\mathrm{mod}p)\\ x^2\equiv c(\mathrm{mod}q)\end{array}$ using $c^{\frac{p+1}{4}}$, Tonelli's, and the Chinese Remainder Theorem.
5. Message will be one of square roots.

Proof

As hard to break as factoring because:

Proposition: If you can break Rabin's variant in randomized time poly in $\ln n$, then you can factor $n$ in randomized time poly in $\ln n$ too!

Suppose you can break Rabin's variant for $n=301377$. Find the square roots of 1 mod 301337: {1, -1, 113070, -113070}

Consider $\mathrm{G}\mathrm{C}\mathrm{D}(113070-1,n)=541$, so $541\mid n$, and so does 557 (!)

Works because if you have $x_1,x_2,y_1,y_2$ with $x_1\equiv x_2\equiv y_1\equiv y_2(\mathrm{mod}n)$, the n $x_1^2-y_1^2\equiv (x_1-y_1)(x_1+y_1)\equiv 0(\mathrm{mod}n)$

If $x_1\ne y_1$, then $x_1-y_1\in \{-n+1,\dots ,n-1\}$ and $\mathrm{G}\mathrm{C}\mathrm{D}(x_1-y_1,n)>1$ implies $x_1-y_1$ is $p$ or $q$!

So as long as $x_1,y_1,x_2,y_2\equiv ̸0(\mathrm{mod}p)$ (or mod $q$), you're good!

Shor's Algorithm

In 1994, Peter Shor (AT&T → MIT → Microsoft) found a quantum Randomized Polynomial Time Algorithm for factoring and (and discrete logarithms)!!

As far as we know, no one has a quantum computer large enough to implement this algorithm efficiently.

Involves continued fractions and the Quantum Fourier Transform

Decision Classes

A complexity class is a family of sets of bit strings

More practically, it can be thought of as a family of computational problems.

Our model of computation is the Turing Machine

P: Polynomial

The family of decision problems doable in time polynomial in the input size.

Legendre Symbol

Given the $n$-bit binary expansions for $a\in \mathbb{\mathbb{Z}}$ and a prime $p$, decide whether $\sqrt{a}(\mathrm{mod}p)$ exists. That is, evaluate $a^{p-1}2(\mathrm{mod}p)$. This is in P

Stable Marriage Problem

$n$ men and $n$ women with list of preferences. A "stable marriage" is where the man and women are at the same position in their preference list.

It turns out that stable marriages always exists, so its actually in constant time. Finding one takes a bit longer.

ZPP: Zero-Error Probability Polynomial

The family of decision problems where an answer, correct with probability 1/2, can be found in time polynomial in input size

Algorithms (return IDK or an answer with 50% probability) of this class are called "Las Vegas" algorithms: You are never cheated.

RP: Randomized Polynomial

The family of decision problems admitting an algorithm where a "yes" answer is always correct, but a "no" is wrong with probability ≤ 1/2

Compositeness

Given $n\in \mathbb{\mathbb{N}}$, decide if it's composite. In particular, compare $\left(\frac{a}{n}\right)$ with $a^{\frac{n-1}{2}}(\mathrm{mod}n)$ for random $a$: if equal, then probably prime; if not equal, then composite.

Thanks to the Solovay-Strassen Theorem, Compositeness is in RP.