[关闭]
@Lin-- 2019-09-04T06:01:09.000000Z 字数 8275 阅读 310

CINTA重点

根据华南师范大学计算机学院斌头老师的课件整理
整理者:0.H.P

计算机数学


可除性和带余除法

定理:

设a,b ,,那么,使得其中,且这对整数q,r为上述a,b所唯一确定。

证明:

证明:
(1).证r的范围:
将实数轴分为左闭右开的长度均为b的无穷个小区间,即


可得a必定落在某一区间内,故,使得.令,则,又因为,故得.
(2).证q与r的唯一性:
首先证a所在区间的唯一性:运用反证法。
假设,其中,那么假设.得
那么假设,那么有:

故得:a所在区间唯一。又由于,得q唯一。又a=qb+r,得r唯一。
证毕。

欧几里得算法(gcd)

目的:

求两个数的最大公约数

公式:

直到

方法:

对于,且,运用带余除法表达式,有


可得除第一与第二式外,其余都是用后一个余数除前一个余数的余数,即
以此计算,直到余数为0,即
即为结果。

证明:

假设,且不全为0,且有.
若a与b的公因数为d,
即d也是b与c的公约数
以此计算,有
证毕.

时间复杂度:

递归算法:

  1. def gcd(a,b):
  2. if b==0:
  3. return a
  4. else:
  5. return gcd(b,a%b)

迭代算法:

  1. def gcd(a,b):
  2. while b!=0:
  3. y=b
  4. b=a%b
  5. a=y
  6. return a

拓展欧几里得算法(egcd)

目的:

求线性方程组的一组解

方法:



以此循环

  1. def egcd(a,b):
  2. r0,r1,s0,s1=1,0,0,1
  3. while b:
  4. q,a,b=a//b,b,a%b
  5. r0,r1=r1,r0-q*r1
  6. s0,s1=s1,s0-q*s1
  7. print(a,r0,s0)

费马小定理

公式:

p是素数时,

证明:



由消去律得
故得
所以


例题:


解:

所以


欧拉公式

公式:

证明:


设集合



与条件矛盾,故得
所以


由消去律得


性质:

0.满足封闭性;
1.满足结合律;
2.存在单位元;
3.存在逆元。

单位元唯一性:

亦为G的单位元
那么有:


所以

逆元唯一性:


存在性:在群操作中,运算满足封闭性,h恒存在
唯一性:设有另一个逆元h,使得
那么:,由消去律得

子群(subgroup):

循环群(cyclic group):

阶:

满足

例子:

,阶为,生成元个数,生成元,有
,阶为,生成元个数,生成元:

定理1:

若存在正整数k,使得 ,当且仅当k整除n.

证:
充分性:令
必要性:令

由消去律得:

定理2:

证:
设有正整数m,使得




所以

陪集(coset)

定义:

H是G的子群,对于
左陪集:
右陪集:

例子:


遍历:


得①③,②④分别相等,所以左陪集有俩:
同理可求右陪集

性质1:

H是G的subgroup,则有

性质2:划分

所有左陪集构成一个划分,所有右陪集构成一个划分

拉格朗日定理

定义:

证:

由于每个陪集不同,得:

推论一:

群G的阶为n,所有

推论二:

G是素数阶群,则存在


同构(Isomorphisms)

定义:


满足one-to-one(单射) and onto(满射)映射
称φ为一个同构(isomorphic)

证明方法:

1.构造映射;
2.证明阶相同;
3.满足群操作;
4.双射


5.群操作保持:
即先映射后计算等于先计算后映射(证同态)

同态(Homomorphisms)

定义:

,φ是两者间的一个映射,对于所有

正规子群(normal subgroup)

定义:

(即左右陪集相等)

性质:

同态,则
1.
2.
3.
4.

商群(quotient group)

定义:


性质:

商群的阶等于陪集元素的个数

例子:




满足


中国剩余定理

概念:

一种求一次同余式组的算法

算法:

有一次同余式组:


解:
令:

(乘法逆元)

  1. #algorithm of egcd
  2. def egcd(a,b):
  3. r0,r1,s0,s1=1,0,0,1
  4. while b:
  5. q,a,b=a//b,b,a%b
  6. r0,r1=r1,r0-q*r1
  7. s0,s1=s1,s0-q*s1
  8. return r0
  9. #algorithm of CRT
  10. def CRT(a,m):
  11. M,x=1,0
  12. b=list()
  13. b_=list()
  14. for n in range(len(m)):
  15. M=M*m[n];
  16. for i in range(len(m)):
  17. b.append(M//m[i])
  18. '''
  19. compute b_
  20. because b_[i]*b[i]=1(mod m[i])
  21. so b[i]*b_[i]-1=c1*m[i]
  22. than b[i]*b_[i]+c2*m[i]=1
  23. use egcd to compute the result
  24. '''
  25. b_.append(egcd(b[i],m[i]))
  26. '''
  27. when the result is a negative number
  28. let it become a positive number which is a Equivalence class about b_[i]
  29. '''
  30. if b_[i]<0:
  31. b_[i]=b_[i]%m[i]
  32. x=(a[i]*b[i]*b_[i]+x)%M
  33. return x

证明:

假设x0为解,且唯一。
的定义可知,恒有:


而由于


且由于两两互素,故得

证毕。

例题:

Using CRT to solve the system of congruence:
x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 9)
x ≡ 4 (mod 11)

解:由题得:
令:
所以





因为


由拓展欧几里得算法解得


解得


大整数分解

pollard's p-1算法

目的:

求合数N的数因子

思路及算法:

1.设数字m,且,p是素数且为N的因子
那么,由费马小定理得:

故有;
2.令;
3.计算;
4.若结果为1或者N,n自增1,重复步骤2-3,否则,,即为答案;

  1. def gcd(a,b):
  2. if b==0:
  3. return a
  4. else:
  5. return gcd(b,a%b)
  6. def Pollard_PM1(N):
  7. a=2
  8. for i in range(2,N):
  9. a=(a^i)%N
  10. divisor=gcd(a-1,N)
  11. if divisor!=1 and divisor!=N:
  12. return divisor
  13. return 1

pollard's rho算法

目的:

求合数N的数因子

思路及算法

1.假设N有两个数因子x和y

2.设有函数

,,d即为答案

  1. #伪代码
  2. def PollardRho(N):
  3. x1 = x2 = Random_ZN_Star(N)
  4. for i in range(1, 2^(N.nbits()//2)):
  5. x1 = F(x1, N)
  6. x2 = F(F(x2, N), N)
  7. p = gcd(x1 x2, N)
  8. if p != 1 and p != N:
  9. return p

  1. import random
  2. import cmath
  3. def F(x):
  4. return x^2-1
  5. def gcd(a,b):
  6. if b==0:
  7. return a
  8. else:
  9. return gcd(b,a%b)
  10. def PollardRho(N):
  11. i,k=1,2
  12. x=random.randint(0,N-1)
  13. y=x
  14. while True:
  15. i=i+1
  16. x=F(x)%N
  17. divisor=gcd(y-x,N)
  18. if divisor!=1 and divisor !=N:
  19. return divisor
  20. if i==k:
  21. y,k=x,2*k

离散对数

g是群G的生成元,|G|=p-1,,求y

Pohlig-Hellman 算法

1.令


2.

那么:
由于
故得

思路:

为求x,构造一组一次同余式组,以CRT求解。
那么,每个可以用p-1的各个因子去构造。

  1. #Problem: Given base g, y \in <g>, y = g^x mod p, to find x.
  2. def Pohlig_Hellman(y, g, p):
  3. prime_list = factor(p 1)
  4. n = len(prime_list)
  5. q_list = [prime_list[i][0]^prime_list[i][1] for i in range(n)]
  6. G = [ g^((p 1) // q_list[i]) for i in range(n) ]
  7. Y = [ y^((p 1) // q_list[i]) for i in range(n) ]
  8. val_list = [discrete_log(Y[i], G[i]) for i in range(n)]
  9. modulus_list = [q_list[i] for i in range(n)]
  10. x = crt(val_list, modulus_list) # solve the CRT problem.
  11. return x

大步小步算法

1.大步


那么有

2.小步


3.算x


  1. # Input: g,y,n where g is the base, y = g^x mod p,
  2. def BGS(g, y, p):
  3. s = floor(sqrt(p))
  4. A = [(y*(g^r) % p) for r in range(0, s)] #Baby Step.
  5. B = [(g^(t*s) % p) for t in range(1, s+1)] #Giant Step.
  6. r,t = 0,0
  7. for u in A:
  8. for v in B:
  9. if u == v: #Collision.
  10. r, t = A.index(u), B.index(v)
  11. return ((t+1)*s r) % p # Return x

pollard's rho算法

算法

1.设置变量:

2.设置随机函数F()

直到出现
3.那么

  1. #Input: y = g^x mod p; Output: x
  2. def PollardRhoDLOG(y):
  3. lefta, lg, ly = 1, 0, 0 # lefta = g^lg * y^ly
  4. righta, rg, ry = y, 0, 1 # righta = g^rg * y^ry
  5. while lefta != righta:
  6. lefta, lg, ly = F(lefta, lg, ly)
  7. righta, rg, ry = F(righta, rg, ry)
  8. righta, rg, ry = F(righta, rg, ry)
  9. s, t = lg rg, ry ly
  10. if s == 0:
  11. return fail
  12. return s * (t^(−1))

关于随机函数

Pollard suggests:

时间开销

Θ(√q)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注