Pebble Coding

プログラマーの作業メモ

mod pでの平方剰余を計算する(p mod 8 = 5の場合)を実装する

少し前でp mod8 = 5の場合のmod p での平方剰余の計算方法を示しましたが、swiftで実装しておきます。
 {x} ^ {2} = a \mod p の解は存在すると仮定しておきます。

func quadraticResidue(_ a:Int, _ p:Int) -> Int {
    assert(p % 8 == 5)
    let x = expmod(a, (p+3)/8, p)
    if (x * x - a) % p == 0 {
        return x
    }
    let t = expmod(2, (p-1)/4, p)
    return t * x
}