第10回ブルーブリッジカップA組RSA解読
今度のブルーブリッジカップはacmが数学を勉強するのに友好的すぎる.
emmmでも料理ですね
私は最後の問題を埋め尽くして1時間もぶつかった(バカだ)PythonがJavaを書いて自閉症に書いたことがない.
テーマ:
素数ふるいはpを求めることができて、qはユークリッドで互いに素の条件を満たすかどうかを検証して、高速べき乗は直接乗ってlonglongを爆発して、だから高速乗+高速べき乗を使います
どうして私の試験場にPythonがないのですかo(ㄛ゜ㄛ゜)o
emmmでも料理ですね
私は最後の問題を埋め尽くして1時間もぶつかった(バカだ)PythonがJavaを書いて自閉症に書いたことがない.
テーマ:
n=p*q
p,q
d (p-1)*(q-1)
(d*e)%((p-1)*(q-1))=1
c=x^d%n
x=c^e%n
d,c,n
x
素数ふるいはpを求めることができて、qはユークリッドで互いに素の条件を満たすかどうかを検証して、高速べき乗は直接乗ってlonglongを爆発して、だから高速乗+高速べき乗を使います
#Python
p=891234941
q=1123984201
n=1001733993063167141
c=20190324
d=212353
for i in range(1,500000): # d*e%((p-1)*(q-1))=1 (((q-1)*(p-1))*yz+1) %d =0
if(((p-1)*(q-1)*i+1)%d==0):
e=((p-1)*(q-1)*i+1)//212353
print(((p-1)*(q-1)*i+1)//d)
break
def quick_mod(a,b,c):
a=a%c
ans=1
while b!=0:
if b&1:
ans=(ans*a)%c
b>>=1
a=(a*a)%c
return ans
x=quick_mod(c,e,n) #x=c^e%n 579706994112328949
print(x)
print(quick_mod(x,d,n)) #c=x^d%n
どうして私の試験場にPythonがないのですかo(ㄛ゜ㄛ゜)o