curve definition
elliptic curves are symmetric about the x-axis.
group defines addition operation:
group defined on elliptical curve:
need to define corner cases where P+P or P and Q is tangent to the curve

if we reduce the domain of our elliptic curves from real number to finite field, scalar multiplication remains “easy”, while the discrete logarithm becomes a “hard” problem. This duality is the key brick of elliptic curve cryptography.

field definition:
convert into finite field
updated addition definition:
cyclic sub group is foundation of ECC:
There are some classes of elliptic curves that are particularly weak and allow the use of special purpose algorithms to solve the discrete logarithm problem efficiently. For example, all the curves that have p=hn (that is, the order of the finite field is equal to the order of the elliptic curve) are vulnerable to Smart’s attack

ECC: 
secp256k1 is used by bitcoin and ethereum

ECDH is for key exchange, relies on hardness of diffie-hellman problem
ECDSA is for signature sign, requires subgroup has prime order. almost all standardized curves have a prime order, and those that have a non-prime order are unsuitable for ECDSA.

multiplicative gorup is more useful than additive group
group order:
Lagrange theorem:
generator:
cyclic group:
discrete logarithm:
**We will look for groups where computing the group operations is easy (namely, polynomial time) but computing discrete logarithms is hard (namely, exponential or sub-exponential time).** discrete log in additive group is easy, but in multiplicative group it's hard.

finding greatest common divisor:
The multiplicative inverse of a exists if and only if gcd(a, N) = 1

Chinese remainder theorem:

complexity of basic bit operations:

multiplicative group definition:
Euler's theorem:

on multiplicative group for prime P:
isomorphism between additive group and multiplicative group:
proof: just need to prove in additive group N, if x and N is relatively prime, then x is a generator.
since gcd(x, N) = 1, exist y s.t. x * y = 1, if d* x=0(mod N), then d * x * y = 0 * y, then d = 0.

how to test if a given g is a generator:
baby-step giant-step algorithm: faster algorithm for solving discret log on **arbitrary groups**

on quadratic residues:
**square root can be computed in poly time.**
**computational diffie-hellman**:
**decisional diffie-hellman**:
P=2*Q+1 is needed due to quadratic residue check.

DDH to PRG:
DDH to PRF:

## references
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
https://mit6875.github.io/HANDOUTS/numbertheory.pdf