0%

拓展欧拉算法及GF($2^n$)多项式应用

在学习网络安全及密码学的时候,“很难避免”需要学习一些数论的知识。而今天恰好看到了域中的多项式运算,就顺带复习下欧拉算法吧。

一、拓展欧拉算法(Extended Euclidean Algorithm)

1. 欧拉算法(Euclidean Algorithm)

在说拓展欧拉算法前,先说下基本的欧拉算法。

这个算法是关于最大公约数(gcd),

Fact 1: gcd(a,0) = a Fact 2: gcd(a,b) = gcd(b,r), where r is the remainder of dividing a by b

这个算法我们估计在很多小学奥数中就会学到,也是我们常说的辗转相除法。

而利用这个算法,我们可以求出两个数的最大公约数。 如36和10的最大公约数:

gcd(36,10) = gcd(10,6) = gcd(6,4) = gcd(4,2) = gcd(2,0) = 2

2. 拓展欧拉算法(Extended Euclidean Algorithm)

而拓展的欧拉算法,如下:

sa+tb = gcd(a,b)

拓展部分更关注gcd(a,b)与a和b两个变量的线性关系,最终通过迭代的方式求出s和t的值,期间利用q(商)来更新s和t,以达到收敛状态。

3. 代码实现(Python 2.X)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# -*- coding:utf-8 -*-
# Author: Jason Ye
# Time: 2016/03/22

def extendedEucliean(a, b):
"""
Inputs:
Two number a and b
Ouputs:
gcd: Greatest common divisor of a and b
s, t: s and t are integers that satifies gcd(a,b) = s*a+t*b
"""
# Initialization
r1, r2 = a,b
s1, s2 = 1,0
t1, t2 = 0,1

# Iteration
while(r2 > 0):
q = r1 / r2
r = r1 - q * r2
r1, r2 = r2, r

s = s1 - q * s2
s1, s2 = s2, s

t = t1 - q * t2
t1, t2 = t2, t
gcd, s, t = r1, s1, t1
return [gcd, s, t]

def main():
print extendedEucliean(36,10)

if __name__ == "__main__":
main()

二、\(GF(2^n)\)的多项式乘法(Multiplication of Polynomials in \(GF(2^n)\)

看到这个标题,需要搞懂这几个名词,\(GF(2^n)\)和多项式乘法到底是什么吧。

1. \(GF(2^n)\)

在学习了群(Group)、环(Ring)和域(Field)相关的数论知识后,我们能够简单地用下表将这几个概念给区分开来。

Algebraic Structure Supported Typical Operations Supported Typical Sets of Integers
Group (+ -) or (\(\times \div\)) \(Z\_n or Z{\_n}{^*}\)
Ring (+ -) and (\(\times\)) \(Z\)
Field (+ -) and (\(\times \div\)) \(Z\_p\)

至于GF域指的是Galois fields,由Galois提出,提出有限域元素的个数是\(p^n\),其中\(p\)是质数,\(n\)是正整数。而与原文是:

A Galois field, \(GF(p^n\)), is a finite field with \(p^n\) elements.

在密码学中,我们主要用到四种运算(加减乘除),那么我们的操作的范围就是一个域。而对于我们的计算机而言,计算时用的数据都是n比特的数据,n常为8,16,32,64。这意味着数的范围为\(0 到 2^n-1\),溢出或者操作时的模运算中模大小为\(2^n\),因此我们常有两种方式去利用选择域: 1. \(GF(p)\):我们可以选择一个质数p,p是小于\(2^n\)的最大的质数。但是这种方法使得数域中的数利用率降低,如n=4时,我们选择\(p=13 \le 2^4\), 这使得13,14,15这几个数不能使用。 2. \(GF(2^n)\): 这样的话,我们就可以利用数的个数为\(2^n\),对于n是个很小的数时,我们可以通过画图的方式简单地定义一些操作结果,但是当n足够大的时候,我们就很难再去处理运算,所以我们运用我们熟悉的多项式的计算法则来实现我们的域操作。

2. 多项式乘法

对于多项式的操作,首先我们是这样定义多项式的:

\[f(x) = a\_{n-1}x^{n-1} + a\_{n-2}x^{n-2} + \cdots + a\_{1}x^{1} + a\_{0}x^{0}\]

其中\(x^i\)是第i项,对应的系数为\(a\_i\),分别表示n-bit数的第i位以及第i位的值(\(a\_i的值为0或1\)

然后类似于我们的数域中的模运算需要有模,对于多项式中,我们也需要定义一个模,这个模成为质数多项式(prime polynomial),简单来说这个多项式不能够被自己次数更低的多项式分解;

在上面两项的基础上,我们可以定义我们的操作: a. 加减法:对于我们的加减法,实际就是我们GF(2)中的对系数\(a\_i\)异或运算。如 \(x^5+x^2+x \oplus x^3+x^2+1\)\(GF(2^8)\)中,我们经过异或可得\(x^5+x^3+x+1\)。 而减法亦是一样。

  1. 乘除法:在乘法中,可以先利用我们代数中的多项式乘法。显然,积中的项可能有大于n-1的,不同于加减法中的项都是限定在了n-1内。因此,对于这些项,我们需要用我们上面说的质数多项式进行取模,使得其余数落于n-1的最高指数项内。

例子:在\(GF(2^6)\)中,寻找出\(x^2+1\)关于模\(x^4+x+1\)的逆。

这里,我们就可以利用我们上述的拓展欧拉算法:

q r1 r2 r t1 t2 t
\((x^2+1)\) \((x^4+x+1)\) \((x^2+1)\) \(x\) \((0)\) \((1)\) \((x^2+1)\)
\(x\) \((x^2+1)\) \(x\) \((1)\) \((1)\) \((x^2+1)\) \((x^3+x+1)\)
\(x\) \(x\) \((1)\) \((0)\) \((x^2+1)\) \((x^3+x+1)\) \((0)\)
\((1)\) \((0)\) \((x^3+x+1)\) \((0)\)

所以结果是: \[[(x^2+1)\oplus(x^3+x+1)]mod(x^4+x+1) = 1\]