curryで数論関数
目で見る合同１次方程式の解
1。カリー化で１変数化
このワークシートはMath by Codeの一部です。
前回はzipを使うと、ｙがｘの単純な代数的な数式でなくても関数が作れることがわかったね。
今回はカリー化を使ってみよう。
数学の関数、特に数論で使う関数は２以上の変数の関数が多いけど、
多変数関数はコード化がしにくい。
そこで、高階関数をサポートしている言語で可能なカリー化を使ってみよう。
たとえば、ｘとｙの２変数関数ｚがあるとしたら、
ｚを出すにはｘとｙを同時に入れないといけない。
でも、関数利用の場面では、ｘを一時的に定数にして、ｙだけ動かしたり、ｙを固定してｘだけ動かして調べるとか、いろんな使い方がある。
たとえば、xとｙの合計を出すadd(x,y)という関数があるとしよう。
これを細切りして、ｘを入れて、ｙをあとで入れてadd(x,y)を出すと再定義したcurryAddを作る。
すると、add_ten = curryAdd(10)とすると、x=10を固定した１変数関数add_ten(y)として
扱うことができるね。
#[OUT]julia
#======================
function add(x, y)
return x + y
end
curryAdd = x -> y -> add(x, y)
add_ten = curryAdd(10)
println(add_ten(5))
#======================
[OUT]
15
２．数論関数をカレー化して使おう
一番単純な合同1次方程式はどんな式だろうか？
ax≡b (mod p)
とかけるね。
これを関数とみると、z=f(a,k,p)という３変数関数の値がbと等しくなるのを探すことになる。
問題によって、a,k,p,bの値が変わると、探し方も変わるね。
さあて、落ち着いて考えてみよう。
ｘの値はmod pの剰余だから、
bが０でないなら、 xは１からp-1を動かして調べることになる。
ということは、z=f(a,k,p)＝ｂを探すのではなくz=f(a,p)=bを探せばよいことがわかる。
探し方はfの中でｘを動かした結果としてｚをリストで返し、そこにｂを探せばよい。
では、juliaで作ってみよう
＜juliaで合同１次方程式を解く＞
#=====================================
# ax≡b(mod p）の解がx
function multmod(a,p)
k=1:p
return [a*x % p for x in k]
end
crrymmod = p -> a -> multmod(a, p)
# (例１）4x≡3(mod 19)」の解は？ x ≡15
p=19;a=4;b=3
mm = crrymmod(p)
x=findfirst(isequal(b),mm(a))
#=====================================[OUT]
15
#===========================================
#(例２）「4x≡16(mod 28)」の解は？ x ≡ 4 (mod 7)
p=29;a=4;b=16
mm = crrymmod(p)
x=findfirst(isequal(b),mm(a))
#===========================================
[OUT]
7
#===========================================
#(例３）「18x≡8(mod 14)」の解は？ x≡2 ,9 (mod 7)
p=14;a=18;b=8
mm = crrymmod(p)
x=findall(isequal(b),mm(a))
#===========================================
[OUT]
2-element Vector{Int64}:
2
9
3.２次合同方程式を解こう
２次合同方程式もカレー化で、取り組もう。
質問：どのようにして、合同２次方程式が実装できますか。たとえばjuliaで作ってみよう。
#============================================
#x^2+ax≡b(mod p）の解がx
function squaremod(a,p)
k=1:p
return [(x^2+a*x) % p for x in k]
end
crrymmod = p -> a ->squaremod(a,p)
#(例1）x^2+2x≡0(mod 7)の解は？ x ≡ 0, 5 (mod 7)
p=7;a=2;b=0
mm = crrymmod(p)
x=findall(isequal(b),mm(a))
#=============================================
[OUT]
2-element Vector{Int64}:
5
7
mod 7なのにx=7がでるのは変だけど、1スタートの７エンドでｘを動かしているので仕方ないね。
わかっていれば問題ない。
#============================================
#(例2）x^2+2x-1≡０(mod 7)の解は？x≡ 2, 3 (mod 7)
#左辺-7して因数分解すると、x2+2x-8=(x-2)(x+4)≡0(mod 7)から、x≡2, -4≡2,3(mod 7)
p=7;a=2;b=1
mm = crrymmod(p)
x=findall(isequal(b),mm(a))
#============================================
[OUT]
2-element Vector{Int64}:
2
3
#============================================
#(例3）x^2≡3(mod 10)の解は？なし
p=10;a=0;b=3
mm = crrymmod(p)
x=findall(isequal(b),mm(a))
#============================================
[OUT]
Int64[]
これは解なしということだね。