前回の続きです。一般化されたBSGSはまとまりをよくするために次回に回し、今回は、 Pohlig-Hellman algorithm BSGS, Pohlig-Hellman algorithmの実装 について書いていきたいと思います。 Pohlig-Hellman algorithm を素因数分解したときの指数が大きい場合に有効なアルゴリズムであるPohlig-Hellman algorithmを紹介します。ようやくここで群論が登場します。 ここでもとが互いに素である必要があります。ところで、これはが成り立つことを意味しますが、はを満たすものの中で最小ではない可能性があります。しかし、このは…