模運算 ( mod ) 也是我們的工具之一,
正常的除法 : 23 / 4 = 5 ...3 , 那如果我們今天只想要得到餘數,
就是 mod : 23 mod 4 = 3 ( 23 除以模數 4 為 3 , 4 就是模數 )
那它有什麼特性呢?
( a mod p ) * ( b mod p ) = ( a * b ) mod p
舉例來說:
( 10 mod 3 ) * ( 7 mod 3 ) = ( 10 * 7 ) mod 3 = 2
模反元素 ( mod inverse )
如果 c 與 d 在模數是 n 下互為模反元素,則 ( c * d ) / n = 1
舉例來說:
7 與 9 在模數是 4 下互為模反元素,則 ( 7 * 9 ) / 4 = 1
我做夢也沒想到我有一天居然也會教數學,對我來說,數學就是很難的科目,以為填了化學系,就不會再碰到數學了,結果讀了才發現,
“數學” 在 ”化學”上也是很重要的,然後再學習資訊的過程中,
又會碰到那些好難好難的數學,真的是 “ 你越害怕什麼? 就越會碰到什麼? “
總之,這些觀念對 RSA都很重要,所以一定要弄懂
( 10 mod 3 ) * ( 7 mod 3 ) = ( 10 * 7 ) mod 3 = 1 not 2
7 與 9 在模數是 4 下互為模反元素,則 ( 7 * 9 ) / 4 = 1 ???
With mathematica 7.0
PowerMod[9, -1, 4]=1
PowerMod[7, -1, 4]=3
( a mod p ) * ( b mod p ) = ( a * b ) mod p write as
(( a * b ) mod p) mod p more appropriate