# write by 2021/6/28
DIC = "abcdefghijklmnopqrstuvwxyz"
# 辗转相除法
def gcd(a, b):
a, b = b, a % b
# print(a, b)
if b == 0:
return a
else:
return gcd(a, b)
# 扩展欧几里得算法
def exgcd(a, b):
if b == 0:
return 1, 0
x, y = exgcd(b, a % b)
return y, x-(a//b)*y
def encrypt_affine(string, a, b):
ciphertext = ""
if gcd(a, 26) != 1 and gcd(a, 26) != -1:
return -1
for i in string.lower():
if i not in DIC:
ciphertext += i
else:
ciphertext += DIC[(a*DIC.index(i)+b) % 26]
return ciphertext
# 直接遍历所有26可能，找到为止
def decrypt2_affine(string, a, b):
plaintext = ""
if gcd(a, 26) != 1 and gcd(a, 26) != -1:
return -1
for i in string.lower():
if i not in DIC:
plaintext += i
# (x*7+3)%26 = 4
else:
for x in range(26):
if (x*a + b) % 26 == DIC.index(i):
# print("x=", x)
plaintext += DIC[x]
break
return plaintext
# 根据扩展欧几里得算法找到乘法逆元，在求解
def decrypt_affine(string, a, b):
plaintext = ""
if gcd(a, 26) != 1 and gcd(a, 26) != -1:
return -1
a_26_inv = exgcd(a, 26)[0]
for i in string:
if i not in DIC:
return -1
plaintext += DIC[a_26_inv*(DIC.index(i)-b) % 26]
return plaintext
if __name__ == '__main__':
# print(exgcd(3, 26))
a, b = 2, 21
ciphertext_ = encrypt_affine("AFFINECIPHER", a, b)
plaintext_ = decrypt_affine(ciphertext_, a, b)
plaintext_2 = decrypt2_affine(ciphertext_, a, b)
print(f"{plaintext_}: {ciphertext_}")
print(f"{plaintext_2}: {ciphertext_}")
