はじめに これは RSA完全理解 Advent Calendar 2021 の16日目の記事です。 前回は多倍長整数の四則演算をやりました。乗法は だったので、少し効率の良いアルゴリズムを紹介します karatsuba法 桁数nの整数 があったとします。 これらをそれぞれ ずつに分割…

はじめに これは RSA完全理解 Advent Calendar の14日目の記事です 以前 p, qと互いに素なmでのRSAの証明 をやりましたが、今回はp, qと互いに素でないときも含めた証明をやろうと思います。 探しても と が互いに素でないときに言及する証明は少ないので、…

はじめに これは RSA完全理解 Advent Calendar の13日目の記事です RSAの証明は以前フェルマーの小定理を用いてやりましたが、オイラーの定理を利用した証明も多いです。 勉強やりはじめると、理解のために肌に合う証明を探し求めたりすると思うので、ファイ…

はじめに これは RSA完全理解 Advent Calendar の10日目の記事です いままででユークリッド互除法でベズーの等式の解が探索できることと、剰余環とかの言葉の意味がわかるようになりました。 ここまでくると剰余環の逆元を求める処理の説明ができるのでやっ…

はじめに これは RSA完全理解 Advent Calendar の9日目の記事です。 前回までで拡張ユークリッド互除法でベズーの等式の解を探索できることがわかったので、それで剰余環の逆元がだせることを知るために言葉の整理をしよう！という回です。 (というか説明で…

はじめに これは RSA完全理解 Advent Calendar の8日目の記事です。 さて、同カレンダーの過去の記事にて ユークリッド互除法 ベズーの等式 について紹介したので、今回はユークリッド互除法をつかってベズーの等式の解を探索する方法について紹介します。 …

はじめに これは RSA完全理解 Advent Calendar の7日目の記事です RSAにおける秘密鍵の生成である を理解するための一環として、前回はユークリッド互除法について説明しました。 今回はベズーの等式と、関連する定理について説明しようと思います。 次回は…

はじめに これは RSA完全理解 Advent Calendar の6日目の記事です RSAの話は一旦お休みして、今回からは剰余環の逆元をもとめるための前提知識をまとめていきたいと思います おおまかな流れとしては、 ユークリッド互除法の紹介 ベズーの等式と関連する定理…

はじめに これは RSA完全理解 Advent Calendar の3日目の記事です フェルマーの小定理の証明 をやったので、それを使ってRSAの暗号化/復号が成り立つ証明をやります なお、秘密鍵の生成方法についてはベズーの等式や拡張ユークリッド互除法の知識が必要なの…

はじめに これは RSA完全理解 Advent Calendar の2日目の記事です(遅刻した) なんでRSAの話なのにいかにも数学っぽい定理の証明をやるかというと、 RSAの暗号化/復号の操作の証明にはこいつをつかうからです なんならそのうちベズーの等式とかも証明しないと…