ロシアの農民の方法による乗算と現代の暗号化との関係は何ですか？ 一般に研究されている乗算手順とは異なり、積ではなく度を計算するために簡単に適合させることができます。 一部の暗号システムでは、度の計算が必要です。



この記事は、ロシアの農民がどのようにして地主と密かに情報を交換したかを説明するものではないことをすぐに認めなければなりません。

ロシアの農民の方法による乗算

以前にそれについて知らなかった場合、これは乗算に対するかなり奇妙なアプローチであり、乗算テーブルを記憶する必要はありません-整数を2倍にして半分にする能力で十分です。 彼がロシアの農民とどのように関係しているかはあまり明確ではありません。それはデンマークの「デンマークのペストリー」と同じようです。 この方法は、ロシアの農民よりもはるかに早く住んでいた古代エジプト人にも知られていました。



メソッドの一般的な説明は簡単ですが、あまり情報的ではありません。 しかし、それから始めましょう。



2つの整数を乗算する必要がある場合 $$$m$ そして $$$n$ 、次に、書く1つのタイトルに2つの列を描画します $$$m$ そして他の $$$n$ 。 次に、半分に分割して得られた新しい行を常に追加し始めます $$$m$ （残余は廃棄される）および倍増 $$$n$ 、列内で停止 $$$m$ 残ります $$$1$ 。 最後に、列のすべての要素を追加します $$$n$ ここで、値 $$$m$ 奇数。



例を挙げれば、すべてがより明確になります。 掛け算をしましょう $$$13 \回7$ 。 テーブルを提供します

$$

$$\ begin {array} {| c | c |} \ hline m＆n \\ \ hline 13および7 \\ 6および14 \\ 3および28 \\ 1および56 \\ \ hline \ end {array}$$

次に、左の値が奇数である右の値を追加します。

$$

$$7 + 28 + 56 = 91$$

簡単にわかるように、これが結果です $$$13 \回7$ 。



もちろん、なぜこの不思議な手順が機能するのかと思います。



左の列を見て、一番上に行って、書き留めて $$$1$ 奇数と $$$0$ 出会うと $$$1101$ それは $$$13$ バイナリ形式で（そしてもちろん、これは偶然ではありません）。 実際、これは数値をバイナリ形式に変換するための標準アルゴリズムです 。



次に、見てのとおり、列の繰り返しの倍増 $$$m$ 製品を計算します $$$m$ 適切な程度で $$$2$ 、したがって、列内の対応する奇数値との加算 $$$n$ 追加です $$$m$ これらの度数を掛けます $$$2$ それは合計で与える $$$m$ 。



つまり、この方法では任意の整数を乗算でき、さらにアルゴリズムは非常に効果的です。 現在研究されている列またはテーブルのメソッドほど効果的ではないことを認めなければなりませんが、少なくとも乗算テーブルを記憶する必要はありません。



これは非常に便利ですが、メソッドをわずかに変換してはるかに複雑な計算を実行できることは注目に値します。これは、現代の暗号化（公開鍵）で非常に便利です。

ロシアの農民の方法による絶滅

アルゴリズムに2つの小さな変更を加えます。 両方とも列に触れるだけです $$$m$ 。

• 倍増する代わりに、二乗します
• 最後に追加する代わりに、乗算します。

テーブルの各行に対して、乗算する代わりに $$$m$ 適切な程度に $$$2$ 適切な程度に引き上げます $$$2$ 。 これらすべてを掛け合わせると、 $$$n ^ m$ 。



同じ値でこれがどのように機能するかを見てみましょう。 $$$m$ そして $$$n$ 。

$$

$$\ begin {array} {| c | c |} \ hline m＆n \\ \ hline 13および7 \\ 6および49 \\ 3および2401 \\ 1および5764801 \\ \ hline \ end {array}$$

対応するメンバーの乗算は、

$$

$$5764801 \回2401 \回7 = 96889010407$$

本当に等しいもの $$$7 ^ {13}$ 。



しかし、乗算とは異なり、このような方法は十分な効果があるだけでなく、非常に効果的です。



見つけたいなら $$$n$ 程度に $$$m$ その後、乗算することでこれを行うことができます $$$m$ 回数 $$$n$ 。 これが計算方法です $$$m \回n$ 加算 $$$m$ 回数 $$$n$ ：あなたはそうすることができますが、 $$$m$ もっと $$$3$ 、それから費やされた時間をより大きな利益で処分できます。



ただし、このアルゴリズムのおかげで、必要な平方の数は最大で約 $$$3$ より多くの桁数 $$$n$ （2進数の10進数は約 $$$3$ 10進数の桁数の倍のビット数）、その後に同じ数の乗算が続きます。



もちろん、このためには乗算できる必要がありますが、それは私たちに適しています：乗算アルゴリズムでは、2倍と加算で乗算でき、適応バージョンでは、2乗と乗算で累乗できます。 これはお買い得です。

RSAの簡単な紹介

この点は、RSA公開キー暗号化（Rivest-Shamir-Adleman）（および他のいくつか）を実装する方法は、メッセージの暗号化および復号化の程度を計算する必要があることを意味するということです。



手順は次のように機能します：素数の閉じたペアを選択します $$$p$ そして $$$q$ 、そして世界に意味を伝える $$$N = pq$ 。 （値 $$$p$ そして $$$q$ 私たちは秘密を守ります：アルゴリズムは分解問題という事実に基づいています $$$N$ 要因によって複雑です。）



次に、番号を取得します $$$e$ そして見つける $$$d$ そのような $$$ed$ に $$$1$ 仕事以上 $$$（p-1）（q-1）$ 。 世界に知らせる $$$e$ 。 （数 $$$d$ 秘密にしておきます。 アルゴリズムは発見に基づいています $$$d$ 知識なしで $$$p$ そして $$$q$ 挑戦的です。）



ここで、メッセージを整数として表示します $$$M \ lt N$ 。 暗号化されたメッセージフォーム $$$E$ 除算の残り $$$M ^ e$ に $$$N$ 。



数論の魔法（実際、これは魔法ではなく、 フェルマーの小さな定理 ）のおかげで、元のメッセージは除算の残りの部分になります $$$E ^ d$ に $$$N$ 。



原則として、これで十分です。インターネットには他にも多くの説明があり、多くの場合、意味が示されています $$$N$ すべての算術計算を追跡できるほど小さい。



そして、ここで1つの問題が発生します。



実際には、値 $$$M$ そして少なくとも $$$e$ 、または $$$d$ とても素晴らしい。 繰り返し乗算を実行する必要がある場合、終了する前に宇宙は死にます。 このアルゴリズムは、作業量をかなり許容可能な割合に減らします。 乗算 $$$e$ （または $$$d$ ）は、桁数の小さな除数である乗算の数に削減されます $$$e$ （または $$$d$ ）



しかし、これが唯一の問題ではありません。



価値 $$$M ^ N$ ほとんど信じられないほど素晴らしい。 私たちが知っている宇宙の各素粒子を1桁ずつ格納していたとしても、それを記録することはできません。 どのように機能しますか？



答えは再び数論になります。 残差の計算の非常に便利な特性の1つは、計算のどの段階でそれらを見つけるかは重要ではないということです。 で割ったときに特定の値の残りを知る必要がある場合 $$$N$ 、それから整数を計算し、それで割ることができます $$$N$ 、またははるかに論理的で、すべてを段階に分割し、処理された値が超えたときに残りを取得できます $$$N$ 。 最終的に、同じ結果が得られることが保証されます。

RSAロシア農民

これで、暗号化されたメッセージの計算方法がわかりました。 ロシアの農民の方法に従って適応乗算を使用できますが、今度は最終的なタッチを追加できます-数の二乗が超えたとき $$$N$ ）、除算の残りの部分を $$$N$ 。



除算の残りを見つける例を使用して、これがどのように機能するかを見てみましょう $$$7 ^ {13}$ に $$$59$ 。

$$

$$\ begin {array} {| c | c |} \ hline m＆n \\ \ hline 13および7 \\ 6および49 \\ 3および2401 \ rightarrow 41 \\ 1および1681 \ rightarrow 29 \\ \ hline \ end {array}$$

私たちに与えるもの

$$

$$29 \回41 \回7 = 8323 \右矢印4$$

そして、これは実際です（えっ！）部門の残りの部分です $$$96889010407$ に $$$59$ 。



しかし、これは予想外の非難です。 これは次数計算アルゴリズムであり、通常、べき乗（繰り返し）2乗と呼ばれます。 実際、このアルゴリズム（またはその小さなバリエーション）は、次数計算を使用する公開キー暗号化（RSAなど）の実装で使用されます。



これが私たちがやってきたことです。 乗算テーブルを知らない人々が使用していた乗算アルゴリズムは、最新の暗号化手法の基礎となるパワービルディングアルゴリズムに変わりました。

謝辞

MathsJam Gathering 2017で、ヘレン・スミスとリンダ・ゴールデンバーグは、ロシアの農民の方法を含む乗算技術についてプレゼンテーションを行いました。 そのとき、再二乗アルゴリズムはロシアの農民の増殖の適応であり、この認識を読者と共有する価値があることに気付きました。 20分後、オリバーマスターズはフィボナッチ行列について話し、行列をべき乗するための再二乗アルゴリズムに言及しました。 幸いなことに、彼はそれを乗算アルゴリズムと関連付けませんでした。 5分後、Colin Wright（@ColinTheMathmo）はレポートを要約し、この関係について言及しました。 しかし、その時までに、私はまだこの記事を書くことにしました。