Fermatでスリム化
１．指数と法を同じにすると。。。
このワークシートはMath by Codeの一部です。
＜法だけ乗してみる＞
７で割った余りで数を同一視する整数の世界、
つまり、mod７でのべき乗計算をしてみる。
17≡1 (mod 7),
27≡2 (mod 7),
37≡3 (mod 7),
47≡4 (mod 7),
57≡5 (mod 7),
67≡6 (mod 7)
a7≡a (mod7)ということだ。
aが1から６のどれでも、法と同じ7回かけるaに等しい。合同になる。
7乗が1乗と同じと考えることもできるね。
つまり、７−１＝6乗分はキャンセルできるということだね。
かけ算で何もしない数は１だから、
16≡1 (mod 7),
26≡1 (mod 7),
36≡1 (mod 7),
46≡1 (mod 7),
56≡1 (mod 7),
66≡1 (mod 7)
a6≡1 (mod7)ということだ。
言い換えると、
a6ー1は必ず７の倍数になるということだね。
#[IN]Python
#============================================
nums =[1, 2, 3, 4, 5, 6]
ferm=[x**6-1 for x in nums ] #=[0, 63, 728, 4095, 15624, 4665]
g = [x % 7 for x in ferm]
print(g)
#============================================
[OUT]
[0,0,0,0,0,0]
どれも７の倍数になっているね。
素数pを法として
ap-1≡1 (mod p)
これが、フェルマーの小定理
（Fermat's little theorem)
これのおかげで、622を計算しなくても、23で割った余りが１になる。
つまり、622≡1 (mod23)
#[IN]Python
#============================================
pow(6,22,23)
#============================================
[OUT]
1
２．フェルマーさんにたよるかどうか
ちなみに
pythonで、6**22-1≡0(mod 23)をたしかめることもできる。
#============================================
res=6**22-1
print(res)
#============================================
[OUT]
131621703842267135
#============================================
res % 23
#============================================
[OUT]
0
質問：この事例からフェルマーの小定理の便利さを２つ上げください。
フェルマーの小定理の便利さは、指数を(法-1)だけへらせるとか、
何かの(法-1)乗−1をするだけで、法の倍数が作れてしまうとかですね。
＜たよらないとき＞
前回扱った、くりかえし2乗法を使うと、けた溢れしにくい計算で
大量のべき乗計算の剰余を、くりかえし2乗した剰余の積に分解して計算できます。
指数を2進数にすることで、かけ算、わり算のけた数を減らそう。
22(10)=16+4+2=10110(2)
なので、616まで、指数を倍々した剰余、つまり、剰余の2乗の剰余を求めよう。
61≡6 (mod 23),
62≡36-23=13 (mod 23),
64≡169-161=8 (mod 23),
68≡64-46=18 (mod 23),
616≡324-23*14=2 (mod 23),
622=616+4+2=616･64･62
≡2･8･13 ≡16･13 ≡208-23･9
＝1(mod 23)
＜たよるとき＞
x103≡4(mod 11)のｘは？
xが未知数のときは、倍々した剰余を求めておく作戦は使えない。
そこで、指数を減らすためにフェルマーの小定理にたよってみよう。
ｘ10≡1(mod11)と103＝3(mod10)から、x103≡x3≡4(mod11)を解けばよいね。
x =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]に対して
x3(mod11)=[1, 8, 5, 9, 4, 7, 2, 6, 3, 10]
だから、x≡5(mod11)が解だ。
#[IN]julia
#============================================
# x^k≡b(mod p)
k=103
p=11
b=4
# 指数をフェルーの定理で削減してから計算する。
# x をすべての剰余にした結果のリストを作る。
xms=[powermod(x,k % (p-1),11) for x in 1:p-1]
# 結果がｂになるものを検索することで、ｘを求める。
x=findfirst(isequal(b),xms)
print("x^",k,"≡",b,"(mod ",p,")の解x=",x)
#============================================
#[OUT]
x^103≡4(mod 11)の解x=5
３．どうしてそうなるの
ちなみに
pythonで、6**22-1≡0(mod 23)をたしかめることもできる。
#============================================
res=6**22-1
print(res)
#============================================
[OUT]
131621703842267135
#============================================
res % 23
#============================================
[OUT]
0
質問：この事例からフェルマーの小定理の便利さを２つ上げください。
フェルマーの小定理の便利さは、指数を(法-1)だけへらせるとか、
何かの(法-1)乗−1をするだけで、法の倍数が作れてしまうとかですね。
＜たよらないとき＞
前回扱った、くりかえし2乗法を使うと、けた溢れしにくい計算で
大量のべき乗計算の剰余を、くりかえし2乗した剰余の積に分解して計算できます。
指数を2進数にすることで、かけ算、わり算のけた数を減らそう。
22(10)=16+4+2=10110(2)
なので、616まで、指数を倍々した剰余、つまり、剰余の2乗の剰余を求めよう。
61≡6 (mod 23),
62≡36-23=13 (mod 23),
64≡169-161=8 (mod 23),
68≡64-46=18 (mod 23),
616≡324-23*14=2 (mod 23),
622=616+4+2=616･64･62
≡2･8･13 ≡16･13 ≡208-23･9
＝1(mod 23)
＜たよるとき＞
x103≡4(mod 11)のｘは？
xが未知数のときは、倍々した剰余を求めておく作戦は使えない。
そこで、指数を減らすためにフェルマーの小定理にたよってみよう。
ｘ10≡1(mod11)と103＝3(mod10)から、x103≡x3≡4(mod11)を解けばよいね。
x =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]に対して
x3(mod11)=[1, 8, 5, 9, 4, 7, 2, 6, 3, 10]
だから、x≡5(mod11)が解だ。
#[IN]julia
#============================================
# x^k≡b(mod p)
k=103
p=11
b=4
# 指数をフェルーの定理で削減してから計算する。
# x をすべての剰余にした結果のリストを作る。
xms=[powermod(x,k % (p-1),11) for x in 1:p-1]
# 結果がｂになるものを検索することで、ｘを求める。
x=findfirst(isequal(b),xms)
print("x^",k,"≡",b,"(mod ",p,")の解x=",x)
#============================================
#[OUT]
x^103≡4(mod 11)の解x=5