@Lin--
2019-09-04T06:01:09.000000Z
字数 8275
阅读 742
根据华南师范大学计算机学院斌头老师的课件整理
整理者:0.H.P
计算机数学
设a,b ,,那么,使得其中,且这对整数q,r为上述a,b所唯一确定。
证明:
(1).证r的范围:
将实数轴分为左闭右开的长度均为b的无穷个小区间,即
求两个数的最大公约数
直到
对于,且,运用带余除法表达式,有
假设,且不全为0,且有.
若a与b的公因数为d,且
即d也是b与c的公约数
以此计算,有
证毕.
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def gcd(a,b):
while b!=0:
y=b
b=a%b
a=y
return a
求线性方程组的一组解
def egcd(a,b):
r0,r1,s0,s1=1,0,0,1
while b:
q,a,b=a//b,b,a%b
r0,r1=r1,r0-q*r1
s0,s1=s1,s0-q*s1
print(a,r0,s0)
p是素数时,
有
取
由消去律得
故得
所以
解:
得
所以
故
设集合
与条件矛盾,故得
所以
性质:
0.满足封闭性;
1.满足结合律;
2.存在单位元;
3.存在逆元。
设亦为G的单位元
那么有:
所以
设
存在性:在群操作中,运算满足封闭性,h恒存在
唯一性:设有另一个逆元h,使得
那么:,由消去律得
满足
群,阶为,生成元个数,生成元,有
群,阶为,生成元个数,生成元:
若存在正整数k,使得 ,当且仅当k整除n.
证:
充分性:令
必要性:令
由消去律得:
证:
设有正整数m,使得
故
故
H是G的子群,对于
左陪集:
右陪集:
设
遍历:
H是G的subgroup,则有
所有左陪集构成一个划分,所有右陪集构成一个划分
证:
由
由于每个陪集不同,得:
群G的阶为n,所有
G是素数阶群,则存在
群
满足one-to-one(单射) and onto(满射)映射
称φ为一个同构(isomorphic)
1.构造映射;
2.证明阶相同;
3.满足群操作;
4.双射
5.群操作保持:
即先映射后计算等于先计算后映射(证同态)
群,φ是两者间的一个映射,对于所有
(即左右陪集相等)
若同态,则
1.
2.
3.
4.
则
商群的阶等于陪集元素的个数
即
得
一种求一次同余式组的算法
有一次同余式组:
#algorithm of egcd
def egcd(a,b):
r0,r1,s0,s1=1,0,0,1
while b:
q,a,b=a//b,b,a%b
r0,r1=r1,r0-q*r1
s0,s1=s1,s0-q*s1
return r0
#algorithm of CRT
def CRT(a,m):
M,x=1,0
b=list()
b_=list()
for n in range(len(m)):
M=M*m[n];
for i in range(len(m)):
b.append(M//m[i])
'''
compute b_
because b_[i]*b[i]=1(mod m[i])
so b[i]*b_[i]-1=c1*m[i]
than b[i]*b_[i]+c2*m[i]=1
use egcd to compute the result
'''
b_.append(egcd(b[i],m[i]))
'''
when the result is a negative number
let it become a positive number which is a Equivalence class about b_[i]
'''
if b_[i]<0:
b_[i]=b_[i]%m[i]
x=(a[i]*b[i]*b_[i]+x)%M
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)
解:由题得:
令:
所以
求合数N的数因子
1.设数字m,且,p是素数且为N的因子
那么,由费马小定理得:
故有;
2.令;
3.计算;
4.若结果为1或者N,n自增1,重复步骤2-3,否则,,即为答案;
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def Pollard_PM1(N):
a=2
for i in range(2,N):
a=(a^i)%N
divisor=gcd(a-1,N)
if divisor!=1 and divisor!=N:
return divisor
return 1
求合数N的数因子
1.假设N有两个数因子x和y
令
2.设有函数
令
,,d即为答案
#伪代码
def PollardRho(N):
x1 = x2 = Random_ZN_Star(N)
for i in range(1, 2^(N.nbits()//2)):
x1 = F(x1, N)
x2 = F(F(x2, N), N)
p = gcd(x1 − x2, N)
if p != 1 and p != N:
return p
设
import random
import cmath
def F(x):
return x^2-1
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def PollardRho(N):
i,k=1,2
x=random.randint(0,N-1)
y=x
while True:
i=i+1
x=F(x)%N
divisor=gcd(y-x,N)
if divisor!=1 and divisor !=N:
return divisor
if i==k:
y,k=x,2*k
g是群G的生成元,|G|=p-1,,求y
1.令
为求x,构造一组一次同余式组,以CRT求解。
那么,每个可以用p-1的各个因子去构造。
#Problem: Given base g, y \in <g>, y = g^x mod p, to find x.
def Pohlig_Hellman(y, g, p):
prime_list = factor(p − 1)
n = len(prime_list)
q_list = [prime_list[i][0]^prime_list[i][1] for i in range(n)]
G = [ g^((p − 1) // q_list[i]) for i in range(n) ]
Y = [ y^((p − 1) // q_list[i]) for i in range(n) ]
val_list = [discrete_log(Y[i], G[i]) for i in range(n)]
modulus_list = [q_list[i] for i in range(n)]
x = crt(val_list, modulus_list) # solve the CRT problem.
return x
令
那么有
令
有
得
故
# Input: g,y,n where g is the base, y = g^x mod p,
def BGS(g, y, p):
s = floor(sqrt(p))
A = [(y*(g^r) % p) for r in range(0, s)] #Baby Step.
B = [(g^(t*s) % p) for t in range(1, s+1)] #Giant Step.
r,t = 0,0
for u in A:
for v in B:
if u == v: #Collision.
r, t = A.index(u), B.index(v)
return ((t+1)*s − r) % p # Return x
1.设置变量:
2.设置随机函数F()
令
直到出现
3.那么
#Input: y = g^x mod p; Output: x
def PollardRhoDLOG(y):
lefta, lg, ly = 1, 0, 0 # lefta = g^lg * y^ly
righta, rg, ry = y, 0, 1 # righta = g^rg * y^ry
while lefta != righta:
lefta, lg, ly = F(lefta, lg, ly)
righta, rg, ry = F(righta, rg, ry)
righta, rg, ry = F(righta, rg, ry)
s, t = lg − rg, ry − ly
if s == 0:
return ’fail’
return s * (t^(−1))
Pollard suggests:
Θ(√q)