Number theory studies properties including: parity,divisibility,primality,
additivity, and multiplicativity
Sub-branches of number theory:

Elementary
Algebraic
Analytic (multiplicative/additive)
Geometric
Probabilistic
Combinatorial
Logic
Algorithmic/Computational
Arithmetic Algebraic Geometry

Z/nZ = {0,1,2,...,n-1}
Group - set together with an operation that is closed, associative,has
an identity, and has inverses.
Semigroup - only has to satisfy closure and associativity
Monoid - Semigroup with identity
Abelian Group - group with commutativity
Ring - abelian group with closure, associative, and distributive laws
for a second operation
Commutative Ring - second operation is commutative
Ring with identity - second operation has identity element
Integral Domain - commmutative ring with identity with second operation 
satisfying ab=0 implies a=0 or b=0
Division Ring - ring with identity with inverses in second operation
for all nonzero elements
Field - Division ring with second operation commutative

Theorem: A number is irrational if and only if it can be written as an 
infinite simple continued fraction.(A simple continued fraction has a 1 in
every numerator, and an integer everywhere else.
Fermat's Little Theorem: If p is prime and gcd(a,p)=1, then a^(p-1) ~= 1 (mod p)
more general form: If p is prime, then a^p ~= a (mod p)

Elliptic Curves - class of algebraic curves given by y^2 = x^3+ax+b
Also known as an Abelian Variety of dimension one or non-singular cubic curve
They get their name from the fact that they result from a rational chage
of variables in solving elliptic integrals.

A special operation is defined on the set of lattice points on an elliptic curve
that takes two points and returns a third point. The third point is obtained
by connecting the two points in the argument with a straight line and finding
where this line intersects the curve, and then negating the y coordinate. This
is known as the chord and tangent method.
The operation can be algebraicly computed by:
Let P1=(x1,y1) P2=(x2,y2) E: y^2=x^3+ax+b
P1 (+) P2 = { (point at infinity) if x1=x2 and y1=-y2
	    ([(3*x1^2+a)/(2*y1)]^2-x1-x2,[(3*x1^2+a)/(2*y1)]*(x1-x3)-y1) if P1=P2
	    ([(y2-y1)/(x2-x1)]^2-x1-x2,[(y2-y1)/(x2-x1)]*(x1-x3)-y1) otherwise
The fundamental computation on elliptic curves is kP=P(+)P(+)...(+)P where
there are k P's on the right hand side.

Fast Modular Exponentiation (Method of successive squaring)
- key that makes many pseudo-primality tests tractable

Fermat Pseudoprimality Test - the converse of Fermat's Little Theorem is very
nearly true, meaning that there are very few composites that satisfy the 
congruence. Checking the congruence by the method of successive squaring
will either tell you that it is definitely composite, or probably prime.

Carmichael Number - satisfies b^(n-1) ~= 1 (mod n) for all b such that gcd(b,n)=1 
First 10: 561,1105,1729,2465,2821,6601,8911,10585,15841,29341 (there are infinitely many)

Practical Test: First do Strong Pseudoprimality Test (similar to Fermat) 
and Lucas Pseudoprimality Test since these two tend have non-overlapping 
pseudoprimes. Then for any probable primes, use the Elliptic Curve Method
to prove that the number is prime.

Residue Computers - ALU stores numbers in residues mod a set of numbers
rather than in digits. This way, arithmetic operations of addition, subtraction,
and mutliplication can be performed in parallel (divide and conquerer) with the
results combined at the end using the chinese remainder theorem. Residue 
Computers have found applications in digital signal processing, and have
often been implemented in software on binary computers.

Hard problems used for cryptography (sources of trapdoor functions):
 Factoring, discrete logarithm, quadratic roots, elliptic curve points

To use a secret key cryptosystem while still having public keys, you can
use a hybrid crytosystem that first exchanges secret keys in the payload
of a public key message, then proceeds using the secret key cryptosystem, which
usually has the benefit of increased speed.

Quantum Crytography: A set of photons are sent that are polarized with one of
{0,45,90,135} where {0,90} is type 1 and {45,135} is type 2. 
The receiver randomly chooses either a type 1 or type 2
filter to measure the polarizations and then announces the types that he
received. The first sender then announces which ones were of the correct type
and then they encode the correct ones as 0 if first element of the type set, or
1 for the second element, and use the resulting string as their key. This works
because the ones that were verified have to be the exact same polarity because
there is no chance of the photons going through a polarizer that has a 90 degree
phase difference. There is a chance of going through a 45 degree phase
difference, but this causes a change in the type, so they will be eliminated in
the verification process.