【C++】モジュロ p における平方根の求め方（p が 4*i + 3 の形の場合）

問題概要

この問題では、整数 n と素数 p が与えられ、「モジュロ p における平方根」を求めます。ここで、p は 4*i + 3 の形、すなわち p % 4 == 3 を満たす素数である必要があります（i > 1）。

この条件に当てはまる素数には、たとえば 7、11、19、23、31 などがあります。

入出力例

入力 : n = 3, p = 7
出力 : 平方根は存在しません

すべての n に対して平方根が存在するとは限りません。n が「平方剰余」でない場合、答えは存在しないため、その判定も行う必要があります。

解法アプローチ①：全探索（線形探索）

最もシンプルな解法は、ループを使う方法です。2 から (p − 1) までの各値について、その値の2乗を p で割った余りが n と一致するかどうかを順番に確認していきます。

コード例

#include <iostream>
using namespace std;

// モジュロ p 上で n の平方根を線形探索する
void findSquareRootMod(int n, int p) {
    n = n % p;
    for (int i = 2; i < p; i++) {
        if ((i * i) % p == n) {
            cout << "モジュロ上の平方根は " << i;
            return;
        }
    }
    cout << "平方根は存在しません";
}

int main() {
    int p = 11;
    int n = 3;
    findSquareRootMod(n, p);
    return 0;
}

実行結果

モジュロ上の平方根は 5

この方法の計算量は O(p) であり、p が大きくなると非効率になるという欠点があります。

解法アプローチ②：公式を使う効率的な方法

p が 4*i + 3 の形の場合、平方根が存在すれば次の公式で直接求められます。

平方根 = ±n^(p+1)/4 (mod p)

この公式が成り立つ背景にはオイラーの規準があります。n が平方剰余であれば n^(p−1)/2 ≡ 1 (mod p) が成立するため、x = n^(p+1)/4 とおくと x² = n^(p+1)/2 = n・n^(p−1)/2 ≡ n (mod p) となり、x が確かに平方根になります。

べき乗の計算には繰り返し二乗法（バイナリ累乗）を用いることで、全体の計算量を O(log p) まで抑えることができます。

コード例

#include <iostream>
using namespace std;

// 繰り返し二乗法によるべき乗計算（mod p）
int calcPowerVal(int x, int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y /= 2;
        x = (x * x) % p;
    }
    return res;
}

void squareRoot(int n, int p) {
    // p が 4*i + 3 の形かどうかを確認
    if (p % 4 != 3) {
        cout << "無効な入力です";
        return;
    }
    n = n % p;
    int sr = calcPowerVal(n, (p + 1) / 4, p);
    if ((sr * sr) % p == n) {
        cout << "モジュロ上の平方根は " << sr;
        return;
    }
    // 負の側の平方根（p - sr）も確認
    sr = p - sr;
    if ((sr * sr) % p == n) {
        cout << "平方根は " << sr;
        return;
    }
    cout << "平方根は存在しません";
}

int main() {
    int p = 11;
    int n = 4;
    squareRoot(n, p);
    return 0;
}

実行結果

モジュロ上の平方根は 9

まとめ

p が 4*i + 3 の形の素数である場合、モジュロ p 上の平方根は次の2つの方法で求められます。

• 全探索： 2〜(p−1) の各値の2乗を順に確認するシンプルな方法。計算量は O(p)。
• 公式ベース： n^(p+1)/4 を繰り返し二乗法で計算する高速な方法。計算量は O(log p)。

競技プログラミングや暗号処理の現場では p が非常に大きな値になるため、実用性を重視するなら公式を使った O(log p) のアプローチを選ぶのがおすすめです。