#---------------------------------------------------------------
#分解大整数
import math
def moder(n):
	base=2
	while base <math.sqrt(n):
		if(n%base==0):
			fbase=base
			print(base,int(n/base))
		base+=1
	pass
	f=getEuler(fbase,int(n/fbase))
	print('f(n)欧拉函数值：%d'%f)#
	return f
#-------------------------------------
# 求欧拉函数f(n)
def getEuler(prime1, prime2):
    return (prime1-1)*(prime2-1)
#---------------------------------------------------------------------------------------
# 19d - 920071380k= 1
# 求私钥d
def getDkey(e, Eulervalue):#可以辗转相除法
	k = 1
	while True:
		if (((Eulervalue * k) + 1) % e) == 0:
			(d,m)=divmod(Eulervalue * k + 1,e)
			return d#避免科学计数法最后转int失去精度
		k += 1
#------------------------------------------------------
#求明文
def Ming(c,d,n):
	return pow(c,d,n)
#---------------------------------------------------------------------------------------
if __name__=='__main__':
	n=int(input('请输入要分解的质数： '))#920139713
	e=17            #19
	d =getDkey(e, moder(n))
	print('私钥为： %d'%d)
	c=[704796792,752211152,274704164,18414022,368270835,483295235,263072905,459788476,483295235,459788476,663551792,475206804,
	   459788476,428313374,475206804,459788476,425392137,704796792,458265677,341524652,483295235,534149509,425392137,428313374,
	   425392137,341524652,458265677,263072905,483295235,828509797,341524652,425392137,475206804,428313374,483295235,475206804,459788476,306220148]
	L=[]
	for x in c:
		L.append(Ming(x,d,n))
	print(L)#明文ascii表
	for x in L:
		print(chr(x),end='')
 
 """
算法描述：


（1）选择一对不同的、足够大的素数p，q。
（2）计算n=pq。
（3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。
（4）找一个与f(n)互质的数e，且1<e<f(n)。
（5）计算d，使得de≡1 mod f(n)。这个公式也可以表达为(d*e-1)% f(n)=0
     这里要解释一下，≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。
     显而易见，不管f(n)取什么值，符号 右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。
     这就需要计算出d的值，让这个同余等式能够成立。
（6）公钥KU=(e,n)，私钥KR=(d,n)。
（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，
     则加密过程为：C≡M^e(mod n)。
（8）解密过程为：M≡C^d(mod n)。


"""
 
 
 
 
