convto https://blog.hatena.ne.jp/convto/ ちりもつもればミルキーウェイ https://convto.hatenablog.com/ アルゴリズム/データ構造 数値演算 数学 はじめに これは RSA完全理解 Advent Calendar 2021 の16日目の記事です。 前回は多倍長整数の四則演算をやりました。乗法は だったので、少し効率の良いアルゴリズムを紹介します karatsuba法 桁数nの整数 があったとします。 これらをそれぞれ ずつに分割して の上位の桁のほうを の下位の桁のほうを の上位の桁のほうを の下位の桁のほうを とします。 そうすると は と表せます。 このとき計算コストがたかい乗法が4回必要ですが、ここで について以下のように整理すると乗法の回数が3回で済みます。このときの操作自体は計算結果が となるような式を当てはめただけです。計算す… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fconvto.hatenablog.com%2Fentry%2F2022%2F01%2F01%2F121236" title="karatsuba法 - ちりもつもればミルキーウェイ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2022-01-01 12:12:36 rich https://convto.hatenablog.com/entry/2022/01/01/121236 1.0 100%