Python数论基础

# Python数论基础 - 完整代码示例
# 数论研究整数的性质，在密码学中扮演关键角色

import sympy as sp
from sympy import gcd, lcm, factorint, isprime, nextprime, primerange, mod_inverse
import math
import random

# 1. 最大公约数 (GCD) 和最小公倍数 (LCM)
a, b = 84, 462
gcd_val = gcd(a, b)
lcm_val = lcm(a, b)
print(f"最大公约数: gcd({a}, {b}) = {gcd_val}")
print(f"最小公倍数: lcm({a}, {b}) = {lcm_val}")
# 验证关系: a * b = gcd * lcm
print(f"验证: a*b = {a*b}, gcd*lcm = {gcd_val * lcm_val}")

# 2. 欧几里得算法（辗转相除法）- 手动实现
def euclidean_gcd(m, n):
"""使用欧几里得算法计算最大公约数"""
while n != 0:
m, n = n, m % n
return m

def extended_euclidean(a, b):
"""扩展欧几里得算法：返回 (gcd, x, y) 满足 ax + by = gcd"""
if b == 0:
return a, 1, 0
g, x1, y1 = extended_euclidean(b, a % b)
x = y1
y = x1 - (a // b) * y1
return g, x, y

g, x, y = extended_euclidean(a, b)
print(f"\n扩展欧几里得: {a}*({x}) + {b}*({y}) = {g}")
print(f"验证: {a*x + b*y} = {g}")

# 3. 质因数分解
n_factor = 1234567890
factors = factorint(n_factor)
print(f"\n质因数分解 {n_factor}:")
for prime, exp in factors.items():
print(f" {prime}^{exp}")
print(f"验证乘积: {sp.prod([p**e for p, e in factors.items()])} = {n_factor}")

# 4. 素数检测
test_numbers = [17, 21, 97, 101, 111, 7919]
print(f"\n素数检测:")
for n in test_numbers:
result = isprime(n)
print(f" {n:5d} -> {'是素数' if result else '不是素数'}")

# 5. 素数生成
print(f"\n下一个素数:")
for n in [10, 50, 100, 1000]:
print(f" nextprime({n}) = {nextprime(n)}")

print(f"\n指定范围内的素数 (50 到 100):")
primes_in_range = list(primerange(50, 101))
print(f" {primes_in_range}")

# 6. 模逆元 (mod_inverse)
# 计算 a 在模 m 下的乘法逆元 a⁻¹ mod m
a_mod, m_mod = 3, 11
inv = mod_inverse(a_mod, m_mod)
print(f"\n模逆元: {a_mod}⁻¹ mod {m_mod} = {inv}")
print(f"验证: {a_mod} * {inv} mod {m_mod} = {(a_mod * inv) % m_mod}")

# 7. 中国剩余定理 (CRT)
def chinese_remainder_theorem(remainders, moduli):
"""中国剩余定理：求解 x ≡ r_i (mod m_i)"""
total_mod = sp.prod(moduli)
result = 0
for r, m in zip(remainders, moduli):
M = total_mod // m
inv = mod_inverse(M, m)
result += r * M * inv
return result % total_mod

# 求解 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]
x_crt = chinese_remainder_theorem(remainders, moduli)
print(f"\n中国剩余定理:")
print(f" 解: x ≡ {x_crt} (mod {sp.prod(moduli)})")
for r, m in zip(remainders, moduli):
print(f" 验证: {x_crt} mod {m} = {x_crt % m} (应为 {r})")

# 8. RSA 加密数学基础
# 生成 RSA 参数（小规模演示）
# 选择两个大素数
p = 61
q = 53
n_rsa = p * q
phi_n = (p - 1) * (q - 1)

# 选择公钥指数 e（与 phi_n 互质）
e = 17 # 常见的公钥指数
# 验证互质
print(f"\nRSA 参数:")
print(f" p = {p}, q = {q}")
print(f" n = p*q = {n_rsa}")
print(f" φ(n) = {phi_n}")
print(f" gcd(e, φ(n)) = {gcd(e, phi_n)}")

# 计算私钥 d = e⁻¹ mod φ(n)
d = mod_inverse(e, phi_n)
print(f" 公钥: (e={e}, n={n_rsa})")
print(f" 私钥: (d={d}, n={n_rsa})")

# 加密解密演示
message = 42 # 消息（必须是小于 n 的整数）
ciphertext = pow(message, e, n_rsa) # 加密: c = m^e mod n
decrypted = pow(ciphertext, d, n_rsa) # 解密: m = c^d mod n
print(f"\nRSA 加密演示:")
print(f" 原始消息: {message}")
print(f" 密文: {ciphertext}")
print(f" 解密后: {decrypted}")
print(f" 验证: {message == decrypted}")

# 9. 欧拉函数
def euler_phi(n):
"""计算欧拉函数 φ(n)：小于等于 n 且与 n 互质的正整数的个数"""
result = n
temp = n
for p in range(2, int(math.sqrt(n)) + 1):
if temp % p == 0:
while temp % p == 0:
temp //= p
result -= result // p
if temp > 1:
result -= result // temp
return result

print(f"\n欧拉函数:")
for n_test in [5, 10, 12, 20, 100]:
print(f" φ({n_test}) = {euler_phi(n_test)}")
# 验证：使用 sympy 的 totient
sympy_phi = sp.totient(n_test)
print(f" sympy 验证: φ({n_test}) = {sympy_phi}")

# 10. 模指数运算
def mod_pow(base, exp, modulus):
"""快速模指数运算（平方乘算法）"""
result = 1
base = base % modulus
while exp > 0:
if exp & 1: # 如果当前位为 1
result = (result * base) % modulus
base = (base * base) % modulus
exp >>= 1
return result

base, exp, mod = 7, 13, 41
fast_result = mod_pow(base, exp, mod)
py_result = pow(base, exp, mod)
print(f"\n快速模指数:")
print(f" {base}^{exp} mod {mod} = {fast_result}")
print(f" Python 内置验证: {py_result}")

# 11. 素性检测：Miller-Rabin 算法
def miller_rabin(n, k=10):
"""Miller-Rabin 概率素性检测"""
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# 将 n-1 写成 d * 2^s 形式
s, d = 0, n - 1
while d % 2 == 0:
s += 1
d //= 2
# 进行 k 轮检测
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True

test_primes = [101, 103, 107, 109, 113, 1000003]
print(f"\nMiller-Rabin 素性检测:")
for n_test in test_primes:
mr_result = miller_rabin(n_test)
sp_result = isprime(n_test)
print(f" {n_test:7d} -> Miller-Rabin: {mr_result}, sympy: {sp_result}")

print("\n数论总结：sympy 提供全面的数论函数库")
print("GCD、素性检测、模逆元是密码学的核心数学基础")