ksnctf #17 Math II
問題
ksnctf.sweetduet.info xを満たすyがFLAGらしい。
解き方
問題を見たときはモジュロ演算なんて言葉は知らなかったけど、取りあえず累乗根を単純に計算するだけだと思った。
ささっと計算してみたらオーバーフローしてうまく動かない。
多分これは私の書き方とかそもそも論で何か間違っているのだろう。
y = pow (x,(1.00/101.00)) OverflowError: long int too large to convert to float
どうすればいいのか調べていたら二分探索で解を得るのがベターらしい。
二分探索をやってみる
二分探索はここを参考にした。 codezine.jp
二分探索と聞いたときは「基本情報でなんか見たかも」ぐらいな感じで、使ったことは一回もなかった。
# python3 import math x = ここに問題文の値を入れる y_min = 0 y_max = 10 ** 300 #ここは適当 y_jou = 101 for num in range(0,2000): # 2000も適当 mid = ( y_min + y_max ) // 2 dy = pow (mid , y_jou) if dy == x: print (mid) break elif dy > x: y_max = mid print ("大きすぎ") elif dy < x: y_min = mid print ("小さすぎ") keta = int(math.log10(mid)+1) print (str(num) + ": " + str(keta) + "桁")
なんとなくやっていることを理解して、雰囲気で実装してみたけど一応答えはでた。
その他
問題に書かれていたモジュロ演算はRSA暗号で使われているらしい。
※RSA暗号は公開鍵暗号の一つ
参考
はやわかり RSA
法とモジュロ – まいとう情報通信研究会
RSA暗号
- 作者: 辻真吾
- 出版社/メーカー: 技術評論社
- 発売日: 2016/10/12
- メディア: Kindle版
- この商品を含むブログを見る