connecting...
Google translation for articles :
11 NEMBER donated to you!!

【数学】この計算に覚えあり(前編)

nem22.34xem (11) 297 11 1

 

Nem やビットコインをはじめとする通貨は、暗号通貨って呼ばれますよね。

暗号化の技術によって、取引の安全性が保たれる暗号通貨。


今回は、そんな 暗号技術 に応用される 数学 について、二回に渡ってお話したいと思います。


前編:みんなが日常的にやっている剰余計算 (今回)

後編:剰余計算を使って、チョー難しい計算問題を作る!




暗号理論に使われる数学の一つに、剰余計算(じょうよけいさん)と呼ばれるものがあります。
難しい名前ですが、実は僕たち、日常的にこの計算をやっております!


剰余計算は、以下のような計算のことです:


1 + 1 = 2

5 - 2 = 3


7 + 8 = 3


10 + 11 = 9


3 - 5 = 10

 


あれ、最初の二つはいいけど、最後の三つおかしくない?

いえ、これで良いのです。上の計算は、


「計算結果が12以上になったら、12を引いて、0 ~ 11 の間の数字にする」
「計算結果が 0 より小さくなったら、12を足して、0 ~ 11 の間の数字にする」


というルールのもと、成り立っています。

 

7 + 8 = 15 だけど、12 以上になったので、15 から12を引いて 7 + 8 = 3 とする。
10 + 11 = 21 だけど、12以上になったので、21から12を引いて 10 + 11 = 9 とする。
3 - 5 = -2 だけど、0より小さくなったので、12 を足して 3 - 5 = 10 とする。

 

これが剰余計算と呼ばれる計算です。このルール、どこかで聞いたことがありませんか?

そう、これはまさに「時計」のルールと一緒です。


今、1 時だったとしましょう。1 時間後は何時ですか。答えは 1+1 = 2 で、2 時です。

今、5 時だったとしましょう。 2時間前は何時ですか。答えは 5-2 = 3 で、3 時です。


今、朝7時だったとしましょう。 8 時間後は何時ですか。7+8 = 15 で、15時と答えることもできますが、
15時は 3時のことです。これ、7 + 8 = 3 と計算しているということですよね。


今、朝10時だったとしましょう。11時間後は何時ですか。10+11 = 21 で、21 時と答えることもできますが、
これは 9 時のことです。10 + 11 = 9 と考えているということですよね。


今、 3 時だったとしましょう。5 時間前は何時でしょう? -2 時とは言わず、10時と答えますよね。3 - 5 = 10 です!

とても馴染み深い計算ですが、この計算を使うことで、コンピュータでも解くのが難しいような計算問題を作ること
ができます(それについては後編で)。

 

俺が法(ルール)だ

 


「計算結果が 0~11 以外の数字になったら、12を足したり引いたりして、0 ~ 11 の数字にする」
というルールをご紹介しました。このルールて、12以外の数字に対しても適用することができますよね。

例えばルールを変更して、「計算結果が 0、1以外だったら、2を足したり引いたりして、0 か 1 にする」
というルールに変更したらどうなるでしょう。

 

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

 

という計算になります。通常なら 1+1= 2 ですが、今のルールの場合は、計算結果から 2 を引いて、1+1=0 です。
情報分野ではお馴染みの計算ですね。引き算については、0 - 1 = 1 となります。

 

「計算結果が 0~4 以外だったら、5 を足したり引いたりして、0~4 までの数字にする」というルールに変更したら

1 + 1 = 2

2 + 3 = 0

3 + 3 = 1

2 - 4 = 3

1 - 2 = 4


という計算になります。掛け算に対しても同じルールを適用すると、

 

2 × 3 = 1
4 × 2 = 3

4 × 4 = 1


などとなります。通常なら 4 × 4 = 16 ですが、5 を超えるので、0~4 までの数字になるまで 5 を引き続けると、
16 - 5 - 5 - 5 = 1 となるので、4 × 4 = 1 です。

 

一般に、何か1より大きい整数 n があったとき、「計算結果が 0~n-1 以外の数字になったら、
n 足したり引いたりして、0 ~ n-1 までの数字にする」

というルールを設けることができます。この n のことをと言います。

数字 n が「俺より大きい数字など許さん!」と言って、全ての整数を自分より小さい数にしてしまった、
そんな世界感です。マイナスの数も、小数も分数も許しません。

まさに整数 n が支配する世界

数字が、0~n-1 n 個しかなくても、以上で述べたルールで、足し算、引き算、掛け算を行う
ことができるわけです。

では、割り算はどうでしょうか?

実は、一般の数字 n の支配下では、割り算をすることができません。
だって、法が 6 の世界で、5 ÷ 2 などを計算したら、計算結果が小数になってしまって、
0~5 の数字で表すことができません。

しかし!

n素数の場合は、割り算ができてしまうのです!

法が素数のときは割り算ができる


そもそも割り算て、どういう意味だったでしょうか。

整数に支配されていない通常の世界にいったん戻りましょう。
7÷3 のような割り算は、7 × 1/3 と、掛け算に書き直すことができますね。

1/3 は、3 × 1/3 = 1 、つまり 3 にその数字を掛け算すると、1 になるという性質を持っています。
このことを数学の世界では、「1/3 は 3 の逆数である」と言います。 
つまり、7÷3 = 「7 に 3 の逆数を掛けたもの」と言い直すことができます。

整数が支配する世界でも、同じように「逆数」を考えることができれば、割り算を定義できます。
例えば 7という整数が支配する世界で 3 ÷ 2 を計算したい場合は、

3 ÷ 2 = 3 × (2 の逆数) 

と定めてあげればいいわけです。

そして、素数が支配する世界では、必ず「逆数」を考えることができます:

定理素数が法の場合、0 以外の全ての数 a に対して、a × b = 1 となる数 b が必ず存在する。つまり、a の逆数 b が存在する。

 

 

ちょっと例を見てみましょう。法が 5 という素数である世界では、0,1,2,3,4 という五つの数しか存在しません。


1 × 1 = 1,
2 × 3 = 1,
3 × 2 = 1,
4 × 4 = 1.


なので、確かに 0 以外の数字 1,2,3,4 は、ある数字を掛け算すると、1になります。
11 の逆数、32 の逆数、23 の逆数、44 の逆数です。


他の例も見てみます。法が 7 という素数である世界では、0,1,2,3,4,5,6 という七つの数しか存在しません。


1 × 1 = 1,
2 × 4 = 1,
3 × 5 = 1,
4 × 2 = 1,
5 × 3 = 1,
6 × 6 = 1


と、確かにある数字を掛け算すると、1になりますね。
11 の逆数、42 の逆数、53 の逆数、24 の逆数、35 の逆数、66 の逆数です。

素数はこんな性質を持っているのです(ユークリッドの互除法を使って、この定理は証明されます)。

この素数の性質を使って、例えば法が 7 の場合、割り算を次のように定めることができます:


3 ÷ 2 = 3 × (2 の逆数) = 3 × 4 = 5


他の例も見てみると、


1 ÷ 6 = 1 × (6 の逆数) = 1 × 6 = 6,

5 ÷ 3 = 5 × (3 の逆数) = 5 × 5 = 4


です。このように割り算のルールを定めることで、マイナスも分数も小数もなく、
0 ~ 6 という七つの数字しか存在しない世界が保たれるのです。

法が 6 という素数でない数字の世界だと、2 にどんな数字を掛け算しても、1 にはなりません。
なので、5 ÷ 2 のような割り算を考えることができないんです。

「素数が支配する世界では、割り算ができる」というのは、素数が持つ一つの性質なのです。

難しい問題を作る(次回予告)


剰余計算から始まり、素数が支配する世界のお話までご紹介しました。

素数が支配する世界を利用して、「コンピュータでも計算するのが難しい計算問題」を、簡単に作ることができます。

例えば 97 という素数が支配する世界で 「6という数字を何乗すると、16 になるか」
というような問題を考えた場合、これはとても難しい問題です。

法となる素数をもっと大きくすることで、この手の問題は更に計算するのが難しくなっていきます。
これが、「コンピュータでも計算するのが難しい計算問題」です。

ここら辺は、後編で詳しくご紹介します。

実は今回の記事は、目指せ北海道さんの次の記事に刺激を受けて書いたものでした。
後編では、北海道さんの記事との関連についても触れながら、進めていきたいと思います。



てことで、今日はここまで!



注意)
・剰余計算という名前はあまり一般的ではないかもしれませんが、変な名前でもないと思ったので、使いました。
・「整数 n が支配する世界」という言葉を使いましたが、これは僕が勝手に使った言葉で、数学用語ではないです。
正式名称は「剰余環」とか「剰余体」とか。記号では Z_n と書かれます。

Why don't you get crypt currency 'nem' by posting your blog article?

nemlog is blog posting service which has donation feature by crypt currency nem.
nemlog was launched to create environment which can be donated nem among NEMbers via blog articles.
Let's get nem by posting good blogs.

Nem prize event is being held frequently, Please join us on this opportunity!

nemlog registration from here
Register
Comments from NEMber
やってみよう
2019-04-11 02:39:23ID:100516

>>ゼム🐋ゼム::さん

ありがとうございます!
新しい視点ですね。最初の、法12の計算なんか、まさに
謎解きクイズにできそう!

>>マクト::さん

嬉しいコメントをありがとうございます!
この話って、実質、四則演算しか使ってないんですよね。
それなのに、暗号に応用されるまでの理論が作られるのって、考えた人すごい!って思います。

ゼム🦈ゼム
2019-04-11 00:22:13ID:100464

・w・ルールを見つけるの楽しい!
謎解きに使えるぅううう!

新井マクト 🦎🦎🦎
2019-04-10 23:41:42ID:100442

とても面白い記事でした。
数学って奥が深いなぁ~。
でも楽しい。

やってみよう
2019-04-10 22:57:31ID:100410

>>こめふく@CoinTheReal::さん

ありがとうございます!法を使わずに「a^x=b」みたいな問題を考えると、x = log_a (b) と、対数 (log) を用いて簡単に答えが
出てしまいます。仰る通り、法を考えることで、log が通用しない新しい難問が生まれるんですね。
このような問題は、「離散対数問題」と呼ばれます(^^)

こめふく@CoinTheReal
2019-04-10 22:28:59ID:100400

面白かったです。
「コンピュータでも計算するのが難しい計算問題」に「桁の大きい素因数分解」があるのは知っていましたが、法と素数を使ったものは新たな知見でした。

やってみよう
2019-04-10 21:55:05ID:100378

>>オーウェン::さん

ありがとうございます(^^)
仰る通り、剰余計算を考えることで、2 × 3 = 1 とか、2+3=0 のような、
嘘みたいな計算式を大量生産することができるわけですね!

>>YUTO::さん

ありがとうございます。Nem やビットコインを守る暗号は「楕円曲線暗号」という複雑な暗号ですが、
そこでも「素数が支配する世界」が必要になります!仰る通り、素数が重要な役割を担っていますね。

やってみよう
2019-04-10 21:32:01ID:100348

>>目指せ北海道::さん

そう言っていただけてよかったです!(^^)
北海道さんの記事に出てくる素数 q の法のもと、
121666 の逆数を計算しようとしたのですが、挫折しましたw

>>サバトラ::さん

読んでいただき、ありがとうございます!
今回の記事は、他の数学記事より複雑めの内容ですw
一読していただけただけでもうれしいです!

オーウェン
2019-04-10 21:28:55ID:100347

3は2の逆数です。
ってすごい新鮮な感覚ヽ(・∀・)ノ

これは面白い。

YUTO
2019-04-10 20:59:15ID:100337

暗号通貨でも、素数が重要になってくるのは勉強になりました。
次回はどのような展開になるのかが楽しみです。

目指せ北海道
2019-04-10 20:05:53ID:100306

おお!割り算ができるってこういう事だったんですね!僕の理解はチョー浅いので、こうやってきちんと説明してもらえると、本当に助かります。次回も楽しみにしています!

NEMber who posted this article

「やってみよう」は、プログラマであるタノウエと、数学を勉強しているカナクボが、共同で管理しているアカウントです。
勉強をして身に付けた NEM の知識や数学の話題を、随時投稿していく予定です。
20052
0

Why don't you read following articles?