# NSA hacks our emails

How did the NSA hack our emails?
Using Math in Elliptic curve…

NSA Surveillance (an extra bit) – Numberphile:

# Shimura-Taniyama-Weil Conjecture (Modularity Theorem)

Shimura and Taniyama are two Japanese mathematicians first put up the conjecture in 1955, later the French mathematician André Weil re-discovered it in 1967.

The British Andrew Wiles proved the conjecture and used this theorem to prove the 380-year-old Fermat’s Last Theorem (FLT) in 1994.

It is concerning the study of these strange curves called Elliptic Curve with 2 variables cubic equation:

Example:
$\boxed {y^{2} + y = x^{3} - x^{2} }$(I)

There are many solutions in integers N, real R or complex C numbers, but solutions in modulo N hide the most beautiful gem in Mathematics.

For modulo 5, the above equation has 4 solutions:
(x, y) = (0, 0)
(x, y) = (0, 4)
(x, y) = (1, 0)
(x, y) = (1, 4)

Note 1: the last solution when y=4,
Left-side = 16 + 4 = 20 = 4×5 = 0 (mod 5).
Right-side = 1-1= 0 (mod 5).

Note 2: We call the equation (I) a “Curve over a finite field” since {0, 1,2,.. p-1} is a Field with finite p elements.

Mathematicians for some time have known that if N is a prime number (p), there will be roughly p solutions.

However, the most interesting number is $a_{p} =$ the difference between p and the actual number of solutions.

For N = p = 5, the above equation has actually 4 solutions,
$\boxed {a_{5} = 5 - 4 = 1}$

Note: $a_{p}$ can be positive or negative.

There is a ‘general rule’ (generating function) to predict $a_{p}$, and it is inspired from the ubiquitous Fibonacci numbers.

Recall:
Definition of the Fibonacci sequence as a recurrence relation:
$\boxed{ F_{n}= \begin{cases} 0, & \text{for }n=0\\ 1, & \text{for }n=1\\ F_{n-2} + F_{n-1} , & \text{for } n \geq { 2} \end{cases} }$

Alternatively there is also a generating function for Fibonacci numbers:
$q + q(q+q^{2})+ q(q+q^{2})^{2} + q(q+q^{2})^{3} + q(q+q^{2})^{4} + ...$

Let’s expand it we get the infinite series:
$q + q^{2} + 2q^{3} + 3q^{4 } + 5q^{5} + 8q^{6} + 13q^{7} +...$

The above coefficients coincide with
Fibonacci sequence: {0, 1, 1, 2, 3, 5, 8, 13…}

In 1954, the genius German mathematician Martin Eichler took the cue from the above, discovered another generating function:

$\boxed {q(1-q^{1})^{2} (1-q^{11})^{2} (1-q^{2})^{2} (1-q^{22})^{2}(1-q^{3})^{2} (1-q^{33})^{2}(1-q^{4})^{2} (1-q^{44})^{2} ... }$ — (II)

Let’s expand it, we get:
$q-2q^{2} -q^{3}+ 2q^{4} + q^{5}+2 q^{6}-2q^{7} -2q^{9} -2q^{10}+ q^{11} -2q^{12}+ 4q^{13}$
Let $b_{m}$ denotes the coefficient of the term $q^{m}$:
$b_{1} = 1, b_{2} = -2, b_{3} = -1, b_{4} = 2, b_{5} = 1, ...$

Eichler discovered that for any prime p,
$\boxed { b_{p} = a_{p}}$

Check: $b_{5} = 1 = a_{5}$

The random numbers of solutions in the elliptic curve equation (I) lies on the generating function (II).

If we view q as a point inside a unit disc on the complex plane, there is a group of symmetries and the function (II) is invariant under this group. The function (II) is called a modular form.

The advanced generalisation of the Shimura-Taniyama-Weil Conjecture : we replace each cubic equation by a Representation of the Galois Group; and the modular form generalised by the generating function the “automorphic” function.:

Remarks:
1. The Shimura-Taniyama-Weil Conjecture is a special case of Langlands Program.

2. Weil’s “Rosetta stone”:
Number Theory -> Curves over Finite Fields -> Riemann Surfaces

References:

http://en.m.wikipedia.org/wiki/Modularity_theorem

Click below for more free loan at the Singapore National Library Branches: http://www.nlb.gov.sg/mobile/searches/view_availability/200154975

# Elliptic Curve

Elliptic Curve (E):

$y^{2}= x^{3} + Ax + B$

1. Every E(Q) over Q is Modular

2. Δ = -16(4A³ + 27B²)

# Elliptic Curve

Elliptic Curve (E):

$y^{2}= x^{3} + Ax + B$

1. Every E(Q) over Q is Modular

2. Δ = -16(4A³ + 27B²)

# Modular Form

Modular Form (MF):
Is a function which takes Complex numbers from the upper half-plane as inputs and gives Complex numbers as outputs.

MF are notable for their high level of symmetry, determined not by a single number (2π for sine) but by 2×2 Matrices of Complex numbers.

Uses:
1. Proof of the FLT
2. Investigation of Monster Group.
3. Elliptic curve = MF
4. L-function provides dictionary for translating between Analysis and Number Theory.