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

少し前でp mod8 = 5の場合のmod p での平方剰余の計算方法を示しました
mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding
が、swiftで実装しておきます。

の解は存在すると仮定しておきます。

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 {
        // 因子の2乗を計算しaに一致した場合は解なので終了、ケースB
        return x
    }
    // ケースA
    let t = expmod(2, (p-1)/4, p)
    return t * x
}