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

2 min read読了の目安(約2600字

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

プログラミング・ビットコイン --ゼロからビットコインをプログラムする方法という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))