Zenn
💪

[Package] AbstractAlgebra.jlで「プログラミング・ビットコイン」の演習問題 (§1) を解く

2021/01/11に公開
Julia
tech

タイトルの通りシリーズです．

プログラミング・ビットコイン --ゼロからビットコインをプログラムする方法というO'Reillyの本がありますが (こちらはAmazonのページへのリンクです)，1章 有限体 という大事な章がありますので，この演習問題をJuliaで書いてみようと思いました．

ここで参考になるのは@nekomath271828さんのAbstractAlgebra.jlに関する記事です．やっていきましょう．

なお以下の演習問題は本から取ってきたものです．Python版の著者実装(Notebook)については，こちらを確認頂ければと思います．

https://github.com/jimmysong/programmingbitcoin

§1 演習問題2

問題

{F}_{57}のもとで解いてください

  • 44+33
  • 9-29
  • 17+42+49
  • 52-30-38

Juliaで解くと

57が素数じゃないので，AbstractAlgebra.jlのGF(p)はエラーが出て利用できません (p:素数が条件)．そのため普通に剰余計算で実行しましょう．「%」と「mod」が使えますが (たぶん)，ここで期待されているのはmodの方みたいですね．

p = 57
println((44 + 33) % p)
println((9 - 29) % p) # 間違い
println(mod(9 - 29, p))
println((17 + 42 + 49) % p)
println((52 - 30 - 38) % p) # 間違い
println(mod(52 - 30 - 38, p))

§1 演習問題4

問題

F_{97}のもとで解いてください

  • 95 \cdot 45 \cdot 31
  • 17 \cdot 13 \cdot 19 \cdot 44
  • 12^7 \cdot 77^{49}

Juliaで解くと

p=97が素数なので，AbstractAlgebra.jlのGFを利用できます．F_97を定義し，各数値をそこからもらってきて計算をします．

F = GF(97)
println(F(95) * F(45) * F(31))
println(F(17) * F(13) * F(19) * F(44))
println(F(12) ^ 7 * F(77) ^ 49)

§1 練習問題5

問題

k=1,3,7,13,18のそれぞれに対し，F_{19}の上で次の集合を求めてください

  • \{k\cdot 0, k\cdot 1, \dots, k\cdot 18\}

Juliaで解くと

GFと内包表記で解けます．Pythonのnotebookでは著者がsortをしていますが，GFについてGFElementsのsortが未定義なのでここでは実行していません．比較演算子を書けばいける気もします．

F = GF(19)
for k in [1, 3, 7, 13, 18]
    println([k * F(i) for i in 0:18])
end

§1 練習問題7

問題

p=7,11,17,31のそれぞれに対し，F_{p}の上で次の集合を求めてください

  • \{1^{(p-1)},\dots,(p-1)^{(p-1)}\}

Juliaで書くと

練習問題5と同じで，GFと内包表記で動きます．

for p in [7, 11, 17, 31]
    F = GF(p)
    println([F(i) ^ (p - 1) for i in 1:p-1])
end

§1 練習問題8

問題

F_{31}のもとで，次の式を解いてください

  • 3/24
  • 17^{-3}
  • 4^{-4} \cdot 11

Juliaで書くと

フェルマーの小定理より，(p-1)乗を計算するところで割り算をトリックします．p=31が素数なので，これを利用します．例えば24で割る部分 (24^{-1}を掛ける)については，24^{p-2}を掛ける，に置き換えられます．またJuliaで剰余を考慮した累乗計算はpowermodを使えばよいです (Pythonのpowの第三引数付きと同じです，たぶん)．

いろんな計算をしていますが，いずれも同じ結果になりました．

  • 小問1: 1つ目の式はGFに計算を任せたものです．2つめの式はフェルマーの小定理を利用したものです．
  • 小問2: 1つ目の式はGFに計算を任せたものです．2つめの式はフェルマーの小定理とpowermodを利用したものです．
  • 小問3: 1つ目の式はGFに計算を任せたものです．2つめの式はフェルマーの小定理とpowermodにGFの要素F(11)を使ったものです．最後の3つ目の式は全部をjulia-nativeでmod/powermodで実装した計算です．
prime = 31
F = GF(prime)
println(F(3) * F(24)^(-1), " ", F(3) * F(24) ^ (prime - 2))
println(F(17) ^ (-3), " ", powermod(17, prime - 4, prime))
println(F(4) ^ (-4) * F(11), " ", powermod(4, prime - 5, prime) * F(11), " ", mod(powermod(4, prime - 5, prime) * 11, prime))

Discussion