MATH 470 Lecture 12

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

Homework Questions

${\sqrt {11}}{\pmod {10949}}$

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

Tonelli:

Use $g=2$ as non-square.

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-1 = 2^2 \cdot 2737} , so 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 (s,t) = (2,2737)}

Only one iteration of loop with $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 11 \cdot 2^{-0} )^{\frac{p-1}{4}} = -1} , so $e=2$

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 = \frac{11}{2^2} = 2740 \pmod{10949}}

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} = \pm g^{\frac{e}{2}} \, h^{\frac{t+1}{2}} = 2 \cdot 2740^{1369} \pmod{10949} = \pm 234}

Riemann Hypothesis

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| \pi(x) - \mathrm{Li}(x) \right| = O(\sqrt{x} \, \ln{x})} 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| \pi(x) - \mathrm{Li}(x) \right| < \frac{\sqrt{x} \, \ln{x}}{4 \tau} \quad \forall x \ge 2657}

Generalized Riemann Hypothesis

For primes in arithmetic progression

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| \pi(x;n,a) - \frac{\mathrm{Li}(x)}{\phi(n)} \right| < \sqrt{x} (\ln{x} + 2 \ln{n}) \quad \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!!

Pick distinct primes 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} 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 q} with roughly the same number of digits
Compute $n$ and publish it, but keep 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} 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 q} secret
Bob encrypts a message 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 m \in (\mathbb{Z}/n \mathbb{Z})} via 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 c = m^2 \pmod{n}} —simple!
Alice solves 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 \begin{cases}x^2 \equiv c \pmod{p} \\ x^2 \equiv c \pmod{q}\end{cases}} using $c^{\frac {p+1}{4}}$ , Tonelli's, and the Chinese Remainder Theorem.
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 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 \ln{n}} , then you can factor 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 randomized time poly 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 \ln{n}} too!

Suppose you can break Rabin's variant 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 n = 301377} . Find the square roots of 1 mod 301337: {1, -1, 113070, -113070}

Consider 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{GCD}(113070-1, n) = 541} , so 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 541 \mid n} , and so does 557 (!)

Works because if you have 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 x_1, x_2, y_1, y_2} with $x_{1}\equiv x_{2}\equiv y_{1}\equiv y_{2}{\pmod {n}}$ , the 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 x_1^2 - y_1^2 \equiv (x_1 - y_1)(x_1 + y_1) \equiv 0 \pmod{n}}

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 x_1 \ne y_1} , then 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 x_1 - y_1 \in \{-n+1, \ldots, n-1 \}} and $\mathrm {GCD} (x_{1}-y_{1},n)>1$ implies 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 x_1-y_1} 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 p} or 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 q} !

So as long as 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 x_1, y_1, x_2, y_2 \not\equiv 0 \pmod{p}} (or 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 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 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} -bit binary expansions 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 a \in \mathbb{Z}} and a 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} , decide 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 \sqrt{a} \pmod{p}} exists. That is, evaluate 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}{2} \pmod{p}} . This is in P

Stable Marriage Problem

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} men 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 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 {N}$ , decide if it's composite. In particular, compare 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)} 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^{\frac{n-1}{2}} \pmod{n}} for 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} : if equal, then probably prime; if not equal, then composite.

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