2015-04-08から1日間の記事一覧

baby-step giant-step part2

part1→baby-step giant-step - sigma425のブログ一般的な話をします. さっきの議論でこのアルゴリズムを使える条件は, ・なんか演算gがあって,元の値aからg(a)がとれる(さっきのだと,g(a)=a*x%mod z) ・その演算gは結合法則が成り立つ(g^nとか書ける) ・gを0…

baby-step giant-step

はい。 PKUです3243 -- Clever Y なるmin kを(あるなら)求めよ、という問題解き方: とりあえずzを素数とします. 自然数Hを適当に取り、kをaH-bと書く(1 の両辺にをかけ、 今zが素数なのでが存在して、上と下は同値になる.よって下のようなaとbを求めれば良い…