python gcd算法
时间: 2023-11-07 10:16:17 浏览: 58
Python 中求两个数的最大公约数可以使用 math 模块中的 gcd 函数。例如:
```python
import math
a = 15
b = 25
gcd = math.gcd(a, b)
print(gcd) # 输出 5
```
如果不想使用 math 模块,也可以自己实现 gcd 算法。最常见的实现方式是使用辗转相除法,也叫欧几里得算法。其原理是:设 a、b 为两个正整数,gcd(a, b) 表示 a 和 b 的最大公约数,则有:
- 如果 a % b == 0,则 gcd(a, b) = b;
- 如果 a % b != 0,则 gcd(a, b) = gcd(b, a % b)。
根据这个递归定义,可以写出 Python 代码:
```python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
a = 15
b = 25
gcd_value = gcd(a, b)
print(gcd_value) # 输出 5
```
这个函数首先判断 b 是否为 0,如果是,则 a 和 b 的最大公约数就是 a;否则,根据递归定义,将 b 和 a % b 的最大公约数作为结果返回。
相关问题
python rsa算法
RSA算法是一种非对称加密算法,它使用一对公钥和私钥来进行加密和解密。下面是一个基于Python实现RSA算法的例子:
```python
import random
# 判断一个数是否为素数
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
# 判断两个数是否互为素数
def is_coprime(a, b):
return gcd(a, b) == 1
# 欧几里得算法求最大公约数
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 扩展欧几里得算法求模逆
def mod_inverse(a, m):
if gcd(a, m) != 1:
return None
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m
# 产生公私钥
def generate_keys(p, q):
if not (is_prime(p) and is_prime(q)):
return None
n = p * q
phi = (p - 1) * (q - 1)
e = random.randrange(1, phi)
while not is_coprime(e, phi):
e = random.randrange(1, phi)
d = mod_inverse(e, phi)
return ((e, n), (d, n))
# 加密明文
def encrypt(plaintext, public_key):
e, n = public_key
ciphertext = [pow(ord(char), e, n) for char in plaintext]
return ciphertext
# 解密密文
def decrypt(ciphertext, private_key):
d, n = private_key
plaintext = [chr(pow(char, d, n)) for char in ciphertext]
return ''.join(plaintext)
# 代码测试
p = 61
q = 53
keys = generate_keys(p, q)
public_key, private_key = keys
plaintext = "Hello, RSA!"
ciphertext = encrypt(plaintext, public_key)
decrypted_text = decrypt(ciphertext, private_key)
print("Public key:", public_key)
print("Private key:", private_key)
print("Ciphertext:", ciphertext)
print("Decrypted text:", decrypted_text)
```
这段代码实现了RSA算法的各个步骤,包括判断素数、判断互为素数、欧几里得算法求最大公约数、扩展欧几里得算法求模逆、产生公私钥、加密明文和解密密文。你可以根据需要修改其中的参数和明文来进行测试。
python 欧几里得算法
欧几里得算法,也称为辗转相除法,用于求两个非负整数的最大公约数(Greatest Common Divisor,简称GCD)。在Python中,可以使用递归或循环来实现欧几里得算法。以下是一个示例:
```python
def euclidean_algorithm(a, b):
if b == 0:
return a
else:
return euclidean_algorithm(b, a % b)
# 示例用法
num1 = 48
num2 = 36
gcd = euclidean_algorithm(num1, num2)
print("最大公约数:", gcd)
```
这段代码中,`euclidean_algorithm` 函数使用了递归来实现欧几里得算法。首先判断 `b` 是否为0,若是,则返回 `a` 作为最大公约数;否则,继续递归调用函数,并将 `b` 作为新的 `a`,`a % b` 作为新的 `b`。通过不断取两数的余数直至其中一个数为0,最后返回的非零数即为最大公约数。
在上面的示例中,输入的数字分别是48和36,它们的最大公约数为12。