密码学与信息安全基础-数论

1、Euclidian algorithm

最大公因数(Greatest Common Divisor)
(gcd(a,b)=gcd(b,a\%b))

//recursive version
int gcdr(int a,int b){
  return (b==0)?(a):gcdr(b,a%b);
}

//iterative version
int gcdi(int a,int b){
  while (b!=0) {
    int r=a%b;//a=q*b+r
    a=b;
    b=r;
  }
  return a;
}

2、扩展欧几里得算法

定理：
(if d=gcd(a,b), then exists s,t d=s*a+t*b)
因此如果(gcd(a,b)=1)即a,b互素，那么(1=s*a+t*b)恒成立

void gcde(int a,int b){
	int s1=1,s2=0,s3;
	int t1=0,t2=1,t3;
	while(b!=0){
		int q=a/b;
		int r=a%b;
		a=b;
		b=r;
		s3=s1-q*s2;
		t3=t1-q*t2;
		s1=s2;
		s2=s3;
		t1=t2;
		t2=t3;
	}
	printf("%d %d %d",a,s1,t1);
}

应用：扩展欧几里得算法解丢番图方程

丢番图方程(ax+by=c (x,y in Z))
解法：

1. d=gcd(a,b)
2. if d|c, then infinite solutions.else no solution.
3. 方程两边同除d，得到(a_1*x+b_1*y=c_1)
4. 此时(gcd(a_1,b_1)=1)，故(a_1*s+b_1*t=1)
5. 显然方程有特解(x=c_1*s,y=c_1*t)
6. 于是通解为(x=c_1*s-k*b_1,y=c_1*t+k*a_1)

3、加法逆元，乘法逆元

3.1关系relation

设R是非空集合X上的二元关系

1. (R是自反的Leftrightarrow(forall x)(xin X ightarrow xRx))
2. (R是反自反的Leftrightarrow(forall x)(xin X ightarrow xoverline{R}x))
3. (R是对称的Leftrightarrow(forall x)(forall y)(x in X land y in Xland xRy ightarrow yRx))
4. (R是反对称的Leftrightarrow(forall x)(forall y)(x in X land y in Xland xRyland yRx ightarrow x=y))
5. (R是传递的Leftrightarrow(forall x)(forall y)(forall z)(x in X land y in X land zin X land xRyland yRz ightarrow xRz))

等价关系R
设R是非空集合X上的二元关系，如果R是自反的，对称的和传递的，则称R是等价关系。

同余关系

(adiv n=qcdots rRightarrow amod n=r)

a和b同余于m

[ left{ egin{aligned} amod m=r \ bmod m=r end{aligned} ight}Leftrightarrow aequiv b (mod m). ]

模m同余是整数集上的一个等价关系

[egin{aligned} proof&:\ &1. aequiv a(mod m)Rightarrow自反性\ &2. aequiv b(mod m) ightarrow bequiv a(mod m)Rightarrow对称性\ &3. aequiv b(mod m)land bequiv c(mod m) ightarrow aequiv c(mod m) Rightarrow传递性\ end{aligned} ]

3.2 加法逆元

(if a+b=0 mod m ightarrow -a=b)
即a的加法逆元-a是b

3.3 乘法逆元

(if a*b=1 mod m ightarrow a^{-1}=b)
即a的乘法逆元是b
(iff. gcd(a,m)=1 ightarrow exists a^{-1})
当 (a^{-1}) 存在时，使用扩展欧几里得算法求乘法逆元：

[egin{aligned} &ecause gcd(m,a)=1\ & herefore exists s,t 1=s*m+t*a\ & 1mod m=(s*m+t*a)mod m=t*amod m end{aligned} ]

可知(a^{-1}=t) 很容易用扩展欧几里得求得乘法逆元