time complexity: running time w.r.t. input size
算到bit級別

f(x)=O(g(x)) f(x)以g(x)為上界, 差個常數(shù)倍
f(x)=Omega(g(x)) f(x)以g(x)為下界, 查個常數(shù)倍
f(x)=Theta(g(x)) f(x)與g(x)同階, 即g(x)限住了f(x)的上下界
Remark:
tildeO(關(guān)于n的函數(shù))=O(關(guān)于n的函數(shù)本身×關(guān)于logn的函數(shù))
家用PC可以跑2^60的input size

整數(shù)上的基本運算時間復(fù)雜度

input: a, b
input size: len(a)+len(b)
let n = max(len(a), len(b))

addition/subtraction
O(len(a)+len(b))

multiplication
O(len(a)*len(b))=O(n^2)
可以提高到O(nlogn)

division
a = bq + r
O(len(除數(shù))*len(商))=O(n^2)

gcd
property: gcd(a,b)=min{ abs(ax+by) : ax+by!=0 }
說的是最大公因子=bezout式子的最小絕對值
三種初等變換不改變gcd的值
設(shè)r0=a, r1=b, rk=gcd.
由k往前倒i次的值r_k-i>=fai^i, 這里fai=0.5*(1+根號五) ≈ 1.62
證明: induction on i.
往前倒0次, 就是gcd本身, 這個值大于等于1=fai^0
往前倒1次, r_k-1 > rk, 所以這個值>=2
假設(shè)往前倒2,3,...,i-1次都有這個不等式成立
倒i次 = 倒i-1次 商(i-1次)+倒i-2次>= 倒i-1次 + 倒i-2次>=fai^(i-1)+fai(i-2)=fai^i
現(xiàn)在我們可以估計k是多少
因為r0=倒k次>=fai^k, 故可以推出有k<=log_fai(r0)=O(logr0)
ri=r_i+1*q_i+1+r_i+2這一步的復(fù)雜度是O(log^2 r0)
這樣共作了k步, ∴O(log^3 r0)
實際上, 輾轉(zhuǎn)相除法要更快
ri=ri+1qi+1+ri+2
復(fù)雜度=O(len(ri+1)len(qi+1))
注意到對于a=bq+r, 有l(wèi)en(商)<=len(被除數(shù))-len(除數(shù))+1

另外的方法:
a=2的次冪部分*奇數(shù)部分
b=2的次冪部分*奇數(shù)部分
除以2是數(shù)整體向右移位1
求a,b的gcd就變成求奇數(shù)部分的gcd
對于奇數(shù), gcd(奇數(shù),奇數(shù))=gcd(奇數(shù),奇數(shù)-奇數(shù))-對于后面那個shift得到新的奇數(shù)->gcd(奇數(shù), 奇數(shù))
如此循環(huán)往復(fù)
粗略估計所需步數(shù)是O(奇數(shù)bit維數(shù))

對于bezout等式, ax+by里的x和y可以用擴展的歐幾里得算法求出/

Z_n上的基本運算時間復(fù)雜度

• a+b mod n
  a, b在Z_n中取, 此時算a+b-n即可, 所以復(fù)雜度為O(模數(shù)的位數(shù))
• a-b mod n O(模數(shù)的位數(shù))
• ab mod n O(模數(shù)位數(shù)的平方)
  ab=nq+r, ab用時O(模數(shù)位數(shù)的平方), nq用時O(模數(shù)位數(shù)的平方)
• a/b mod n O(模數(shù)位數(shù)的平方)
  用擴展的歐幾里得算法gcd(n,b)得到1/b mod n, 用時O(模數(shù)位數(shù)的平方), 再算模下的乘法, 也用時O(模數(shù)位數(shù)的平方)
• power a^b mod n O(模數(shù)位數(shù)的平方*上標(biāo)位數(shù))
  把b寫成2進制的形式,
  take a look at a simple example
  a^{(系數(shù)2}3+系數(shù)2^2+系數(shù)2+系數(shù))=
  a^{系數(shù)*a}(系數(shù)2^{3+系數(shù)2}2+系數(shù)2)=
  a^{系數(shù)*square(a}(系數(shù)2^{2+系數(shù)2}1+系數(shù)))
  power n results in scaling the superscript by n
  square results in doubling the superscript

Z中算乘法的加速

(re1+im1 I)*(re2+im2 I)
originally, we need performance 4 times multiplication
actually, we just perform 3 times multiplication
A=(re1+im1)(re2+im2)
B=re1re2
C=im1im2
(re1+im1 I)*(re2+im2 I)=(B-C)+(A-B-C)I

We can borrow this idea to calculate the mul in Z
assume len(a)=len(b)=2n,
a=高位1 2^(n) + 低位1
b=高位2 2^(n) + 低位2
ab=高位1高位2 2^(2n) + (高位1低位2+高位2低位1) 2^n +低位1低位2
A=(高位1+低位1)(高位2+低位2)
B=高位1高位2
C=低位1低位2
ab=B2^(2n) + (A-B-C)2^n + C