RSA 暗号に使われるべき乗計算の時間比較を行います。 鍵サイズはいくつにしますか( 10 以上 )? 15 鍵サイズ = 15 n = 21709 ( 15 bit ) e = 12215 x = 12824 反復2乗法 : mod(x^e,n) = 6848 計算時間 = 0.0 x を掛けて n で剰余をとる操作を e 回繰り返す : mod(x^e,n) = 6848 計算時間 = 0.0150001049042 ここから先はメモリを食い尽くす恐れがあります。 [ 続行 : Enter / 終了 : 1 ] python のべき乗命令で x^e を求めて最後に n で剰余をとる : mod(x^e,n) = 6848 計算時間 = 0.0460000038147 1回ずつ x を掛けて最後に n で剰余をとる : mod(x^e,n) = 6848 計算時間 = 0.53200006485 -------------------------------------------------- 鍵サイズ = 20 n = 820669 ( 20 bit ) e = 136097 x = 34970 反復2乗法 : mod(x^e,n) = 536389 計算時間 = 0.0 x を掛けて n で剰余をとる操作を e 回繰り返す : mod(x^e,n) = 536389 計算時間 = 0.265000104904 ここから先はメモリを食い尽くす恐れがあります。 [ 続行 : Enter / 終了 : 1 ] python のべき乗命令で x^e を求めて最後に n で剰余をとる : mod(x^e,n) = 536389 計算時間 = 2.17199993134 1回ずつ x を掛けて最後に n で剰余をとる : (断念) -------------------------------------------------- 鍵サイズ = 23 n = 6204091 ( 23 bit ) e = 2681661 x = 1990058 反復2乗法 : mod(x^e,n) = 1776064 計算時間 = 0.0 x を掛けて n で剰余をとる操作を e 回繰り返す : mod(x^e,n) = 1776064 計算時間 = 5.7349998951 ここから先はメモリを食い尽くす恐れがあります。 [ 続行 : Enter / 終了 : 1 ] 1 (断念) -------------------------------------------------- 鍵サイズ = 25 n = 29378147 ( 25 bit ) e = 21190723 x = 12424876 反復2乗法 : mod(x^e,n) = 15769401 計算時間 = 0.0 x を掛けて n で剰余をとる操作を e 回繰り返す : mod(x^e,n) = 15769401 計算時間 = 45.6559998989 ここから先はメモリを食い尽くす恐れがあります。 [ 続行 : Enter / 終了 : 1 ] 1 (断念) -------------------------------------------------- 鍵サイズ = 27 n = 70698421 ( 27 bit ) e = 56668363 x = 36946741 反復2乗法 : mod(x^e,n) = 45356482 計算時間 = 0.0 x を掛けて n で剰余をとる操作を e 回繰り返す : mod(x^e,n) = 45356482 計算時間 = 121.655999899 ここから先はメモリを食い尽くす恐れがあります。 [ 続行 : Enter / 終了 : 1 ] 1 (断念) -------------------------------------------------- 鍵サイズ = 1024 n = 1341973069443429661681614372990861671806516631826323464531277286046791759579 70749076497321865485542261034368383384477884620989518441173130665887706941345806 80198461594050431564458121915441663704530027285637686082365557602407075344274512 6421604718277194550945844510259464171039855685731022414572106250446178889 ( 1024 bit ) e = 1312182521842182543543642331464048720062267274773009223495423321114875751242 66218613390465240148200988482015393733261659489228354369572649816868878841234959 74160808809070573695858150545095910707763320432677239390704996953957843991007512 2543527403355216217984863047969509740638638386632235304906916463107971355 x = 9621609180878534510356018501378078552377082781347525914255725879322133114165 76310299063194628758261841978747133404119113413005598103465626986802017467170178 61077505125974739642783771987648194970751764218988150039558320485568030190843938 780543705992786980779057169261739418275985700236203896778059872106747845 反復2乗法 : mod(x^e,n) = 8498781866499440960076083548687324940004098802556938083076739930845 47115686845669001481095328320978222327419688970419561346432173767671546616480752 36927722745733767930766011245708030631604927549690589323473529676296110142601655 04400716389164335105487901102558329827716751552296817993943368268709715633215913 2 計算時間 = 0.140000104904 x を掛けて n で剰余をとる操作を e 回繰り返す : (断念)