pebble8888 https://blog.hatena.ne.jp/pebble8888/ Pebble Coding https://pebble8888.hatenablog.com/ 暗号 DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。 www.pebblewind.com DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、 を満たすxを求める問題です。 ここで、解はただ一つのみ必ず存在することは前提とします。 なので、解が存在するかどうかを調べる必要はありません。 問題はどうやって計算量を少なく求めるかです。 xは{0, 1, 2, ..., n-1}のいずれかです。 xをある数の倍数に小さい数を加えたものとして計算できれば、少ない計算量で求めることができるんじゃね？ ってのがこのアルゴリズムのアイデアです。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpebble8888.hatenablog.com%2Fentry%2F2018%2F05%2F29%2F222655" title="BabyStep GiantStep法(BSGS法) - Pebble Coding" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%7Bg%7D%5E%7Bx%7D%20%3D%20a Hatena Blog https://hatena.blog 2018-05-29 22:26:55 rich https://pebble8888.hatenablog.com/entry/2018/05/29/222655 1.0 100%