各位可能有個疑惑
前面介紹的對稱加密要怎麼安全地發送相同的密鑰給對方呢？

我們明天會介紹一個有趣的方法辦到這件事，不過要懂那個有趣的方法以及後續的討論，得先幫大家上個簡單的數學課

同餘運算(modulo arithmetic)會是接下來很常使用的工具

由於電腦無法儲存精確地儲存實數，因此很多時候我們會在某個整數n的同餘運算下進行

同餘

同餘運算相當直覺，就是整數除以n如果餘數相同，就可以劃上等號
如

以上表示，38除以12、14除以12和2除以12餘數都相同

同樣道理可以延伸至負數

在python中可以用%來取得某個數的餘數

運算規則

同餘可以進行一系列 除法 以外的各種運算

假設 和
對任意正整數c，各位可以試著自己證明以下性質

• 加法 a+c = b+c mod n
• 減法 a-c = b-c mod n
• 乘法 ac = bc mod n
• 次方
• 與其他相加 a+p = b+q mod n
• 與其他相乘 ap = bq mod n

因此基本上只要不進行除法，大多數的運算跟普通時候的四則運算並無區別

簡單的小應用

我們可以藉由以下問題對剛學到的同餘運算小試身手

1. 求 的最後一位數

最後一位數可以藉由除以10的餘數得知

首先次方可以用指數律 處理

因為49與-1同餘，於是

-1的50次方為1，因此

當然以上可以在python迅速完成

pow(7,100,10)

pow利用特殊的演算法，可以快速地求出整數的次方在某個數的餘數
讓我們不用真的計算7的100次方

2. 證明對所有正整數n， 可以被7整除

這個就讓各位當小練習

也可以先用python來驗證不管多大的n都會對

小結

同餘運算相當實用
因為所有整數範圍現在都能被限縮在比n小的餘數上，因此範圍是有限的
而且每個餘數都是整數，能精確地被電腦儲存

同餘運算中加減乘都能做很直覺地計算
如果要求某個數字a在同餘運算上能做除法，得再要求n與a互質
這個性質未來會滿常被用到

相信今天的文章補充完後，之後看到我一直mod應該就知道我在寫什麼