この記事では、RSA暗号への攻撃の中で恐らく最も有名であろうWiener's Attackについて取り上げる。多くは原論文を参考にしているが、証明の省略やアルゴリズムの一部改変等があるので、この記事を読んで氣になったのであればぜひとも原論文を読んで実際に実装してみて欲しい。 連分数 連分数とは、次の形で表される分数の一種である。 \[ \left. \cfrac{a_1}{q_1 + \cfrac{a_2}{q_2 + \cfrac{a_3}{\ddots\cfrac{}{q _ {m - 1} + \cfrac{a_m}{q_m}}}}}\right. = a_1/(q_1 + a_2/(q_2 + a_3/(\ldots/(q _ {m - 1} + a_m/q_m)))) \] 我々が興味があるのは、連分数の中でも \(a_i\)が全て1と等しいような連分数だ。扱いやすくするために、