【密码学作业001 学号__________姓名___________】
1. **非递归版本的欧几里得算法（Euclidean Algorithm）**
欧几里得算法是用来求两个正整数最大公约数（Greatest Common Divisor, GCD）的方法。非递归版本的算法通常使用迭代方式实现：
```markdown
function euclideanNonRecursive(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return a
```
这个算法的基本思想是每次用较大的数除以较小的数，并用余数替换较大的数，直到余数为0，此时较小的数即为最大公约数。
2. **递归版本的欧几里得算法**
递归版本的欧几里得算法利用了欧几里得定理的性质，即`gcd(a, b) = gcd(b, a mod b)`，通过不断递归调用自身来找到最大公约数：
```markdown
function euclideanRecursive(a, b):
if b == 0:
return a
else:
return euclideanRecursive(b, a % b)
```
3. **非递归版本的扩展欧几里得算法（Extended Euclidean Algorithm）**
扩展欧几里得算法不仅求出最大公约数，还能找到两个数的最大公约数的线性组合形式`ax + by = gcd(a, b)`：
```markdown
function extendedEuclideanNonRecursive(a, b):
x = 1
y = 0
xLast = 0
yLast = 1
while b ≠ 0:
q = a // b
a, b = b, a % b
x, xLast = xLast - q * x, x
y, yLast = yLast - q * y, y
return gcd(a, b), x, y
```
4. **递归版本的扩展欧几里得算法**
同理，递归版本的扩展欧几里得算法也是基于`gcd(a, b) = gcd(b, a mod b)`，但还需要记录每次的系数：
```markdown
function extendedEuclideanRecursive(a, b, x=1, y=0, xLast=0, yLast=1):
if b == 0:
return a, x, y
else:
gcd, xNew, yNew = extendedEuclideanRecursive(b, a % b, xLast, yLast, x, y)
return gcd, xNew - (a // b) * xLast, yNew - (a // b) * yLast
```
5. **扩展欧几里得算法的用途**
扩展欧几里得算法可以用于：
- 计算模逆元（用于模运算中的乘法逆）
- 解线性同余方程
- 简化有理数
- 计算RSA密钥对的解密指数
6. **欧几里得算法的时间复杂度**
欧几里得算法的时间复杂度是对数量级，具体来说是O(log min(a, b))，因为每次迭代都将至少一个数减半。
7. **直接的幂算法或模幂算法的时间复杂度**
直接的幂算法（如快速幂算法）的时间复杂度是O(log n)，其中n为指数。模幂算法是在快速幂基础上进行模运算，同样保持O(log n)的时间复杂度。
8. **证明：gcd(a, b) = d**
假设存在整数x和y使得`ax + by = d`，其中d是最小正整数，那么任何其他形式`ax' + by'`都可以表示为`d + k*lb`，其中k是整数。因此，d是最小正整数，gcd(a, b) = d。
9. **证明：gcd(a, b) = gcd(b, r)**
根据欧几里得定理，`a = bq + r`，有`gcd(a, b) = gcd(b, a mod b)`。这里，`a mod b`即为r，所以`gcd(a, b) = gcd(b, r)`。
以上就是关于欧几里得算法及其扩展版的详细解释，以及它们在密码学中的应用和相关证明。在实际的密码学作业中，理解并掌握这些概念对于理解和设计安全的加密算法至关重要。
评论0