数论基础（Introduction Number theory）

结合斯坦福网课

1. notation

教材 Victor Shoup

符号表示：

• N denotes a positive number
• p denote a prime
• Zn = {0,1,2...N-1}

if N=12

9 + 8 = 5 in Z12

5 * 7 = 11 in Z12

5 - 7 = 10 in Z12

x(y+z) = xy+xz in Zn

Greatest common divisor

gcd(x,y) greatesy common divisor of x,y

gcd(12,18) = 6

for all ints. x,y there exits ints. a,b such that

$ax+by = gcd(x,y)$

$212 - 118=6$

Euclid Algorithm can calculate a and b

if gcd(x,y)=1, we say that x and y are relatively prime.

Modular inversion

the inverse of x in Zn is an element y in Zn: x*y = 1 in Zn?

example:

let N is an odd integer. the inverse of 2 in Zn is (N+1/2)

which element have an inverse in Zn?

x in Zn has an inverse if gcd(x,N)=1

More notation

Z*n = {set of inversion element in Zn}

example:

1. for prime p, Zp = Zp\{0} = {1,2,3......,p-1}
2. Z*12 = {1,5,7,11}

for x in Z*n, can find x-1 using Euclid algorithm

2. Fermat and Euler

2.1 Fermat's theorem

let p is a prime

任意x 属于 (Zp)*: x**(p-1) = 1 in Zp

example:

p = 5.

3**4 = 81 = 1 in Z5

2.2 生成质数方法：

这不是最好的算法

g 是 (Zp)* 的生成元概念

3是（Z7)* 的生成元

2.3 Order

$$是(Zp)*生成元组群

Euler‘s genetalization of Fermat

p是质数

3. Modular e'th roots

3.1 Modular e'th roots

The easy case

When does c1/e in Zp exist? Can we compute it e?ciently?

平方运算， 1的平方mod 11 = 10的平方mod 11 = 1。

1，4，9，5，3是11的二次平方剩余，包括0也是。

3.2 Euler’s theorem（告诉我们，哪些值是二次项剩余的）

3.3 Computing square roots mod p

4. Arithmethic algorithms

4.1 Exponentiation(求大幂运算的方法)

累计

5. Intractable problems

5.1 Intractable problems with prime

2的0次方是1

2的1次方是2

2的4次方是16 mod 11 是 5

5.2 DLOG

没有人能够以不可忽略的概率计算出离散对数

5.3 Application: collision resistance

5.4 Intractable problems with composites

Z2(n) 表示有两个n-bit质数

两个困难问题

Further reading

A Computational Introduction to Number Theory and Algebra, V. Shoup, 2008 (V2), Chapter 1--‐4, 11, 12