前回 mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding p mod 8 = 5の時の平方剰余を計算しましたが、今回は、 p mod 4 = 3の時の平方剰余を計算してみましょう。 この場合も簡単に計算が可能です。 前回と同じように の解は存在することを…

pをある程度限定した素数とした時の平方剰余を計算してみます。 整数論の世界では実数の世界でのルートという言葉は使わないようです。 いくつかの整数論の定理を利用しますので、事前に明示しておきます。 これらの定理は超有名なので、整数論の本に必ず載…

lets encrypt で https 化していたサイトがあと１ヶ月で切れますよメールがきて、どうやら自動更新に失敗していると気がつく。 /root/letsencrypt/letsencrypt-auto certonly --webroot --webroot-path /home/onsenlife/public -d onsenlife.info --renew-by…

フェルマーの小定理でpを素数とすると、mod pの世界では、割り算をべき乗に置き換えられます。 pを3以上の素数としておきます。 フェルマーの小定理 で、pは3以上なので、 と書けます。これは mod p においては、乗算に対して、bの逆元が であることを示して…

1以上の整数であるmで割った余りの値を同一とみなす演算の世界では元の数はm-1個である。 gcd(a, m) = 1である数aの総数をオイラーの関数と呼ぶ。 小さい方からどのような数なのかみておく。 1: {1} -> 1 2: {1} -> 1 3: {1, 2} -> 1 4: {1, 3} -> 2 (2は除…

前回書き下した再帰を用いた高速指数計算関数をmod mバージョンにして、7を一般化した数bにしてみよう。 するとこうなる。関数名はpowからexpmodに置き換えた。 func expmod(b:Int, e:Int, m:Int) -> Int { if e == 0 { return 1 } let s = expmod(e/2) % m …

ある数の大きなべき数を計算を行う際にできるだけ少ない計算量で行うための方法として、高速指数計算法というものがある。 例えば、 を計算したいとする。ここで のように2の累乗の足し算に分解する。 そして、 を計算する。 この分解をプログラムで行う場合…