Coppersmith–FreivaldsアルゴリズムをC++で実装する方法｜行列積の高速検証

Freivaldsアルゴリズムとは

Freivalds（別名：Coppersmith–Freivalds）のアルゴリズムは、行列の掛け算の結果が正しいかどうかを高速に検証するための確率的アルゴリズムです。試行回数 k を選ぶことで、誤判定の確率を 2^-k 未満に抑えながら、O(kn²) の計算量でチェックできます。

n×n 行列の積を素直に計算して照合すると O(n³) の計算量が必要ですが、このアルゴリズムでは「ランダムなベクトルとの積」だけで検証を行うため、1回あたり O(n²) という低いコストで済むのが大きな特徴です。

アルゴリズムの手順

入力として同じ次元 n の3つの行列 matrix1、matrix2、matrix3 を受け取り、「matrix1 × matrix2 = matrix3」が成り立つかどうかを確認します。

Begin
    matrix1(n×n)、matrix2(n×n)、matrix3(n×n) を入力として受け取る
    （検証したい等式： matrix1 × matrix2 = matrix3）
    1) 各成分が 0 または 1 であるベクトル a[n][1] を一様ランダムに選ぶ
    2) matrix2 * a と matrix3 * a を計算し、さらに
       matrix1 * (matrix2 * a) - matrix3 * a を評価する
    3) 結果が 0 ベクトルになっているかどうかを判定する
    4) 0 であれば掛け算は正しいとみなし、そうでなければ誤りと判断する
End.

C++による実装例

以下は、上記のアルゴリズムを C++ で実装したプログラムです。ベクトルや中間結果を格納する配列は、必ずゼロで初期化してから加算する点に注意してください（未初期化のままだと誤動作の原因になります）。

#include <iostream>
#include <cstdlib>
using namespace std;

int main(int argc, char **argv) {
    cout << "行列の次元を入力してください: ";
    int n;
    cin >> n;

    cout << "1つ目の行列を入力してください:\n";
    double matrix1[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix1[i][j];
        }
    }

    cout << "2つ目の行列を入力してください:\n";
    double matrix2[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix2[i][j];
        }
    }

    cout << "検証対象の結果の行列を入力してください:\n";
    double matrix3[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix3[i][j];
        }
    }

    // 各成分が 0 または 1 のランダムベクトル a を生成
    double a[n][1];
    for (int i = 0; i < n; i++) {
        a[i][0] = rand() % 2;
    }

    // matrix2 × a を計算
    double matrix2a[n][1] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 1; j++) {
            for (int k = 0; k < n; k++) {
                matrix2a[i][j] += matrix2[i][k] * a[k][j];
            }
        }
    }

    // matrix3 × a を計算
    double matrix3a[n][1] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 1; j++) {
            for (int k = 0; k < n; k++) {
                matrix3a[i][j] += matrix3[i][k] * a[k][j];
            }
        }
    }

    // matrix1 × (matrix2 × a) を計算
    double matrix12a[n][1] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 1; j++) {
            for (int k = 0; k < n; k++) {
                matrix12a[i][j] += matrix1[i][k] * matrix2a[k][j];
            }
        }
    }

    // matrix1 * (matrix2 * a) - matrix3 * a が 0 かどうかを判定
    bool flag = true;
    for (int i = 0; i < n; i++) {
        if (matrix12a[i][0] - matrix3a[i][0] != 0) {
            flag = false;
            break;
        }
    }

    if (flag)
        cout << "これは正しい結果の行列です";
    else
        cout << "これは正しい結果の行列ではありません";

    return 0;
}

実行例

正しい結果の行列を入力した場合

行列の次元を入力してください: 2
1つ目の行列を入力してください:
1 2
3 4
2つ目の行列を入力してください:
2 0
1 2
検証対象の結果の行列を入力してください:
4 4
10 8
これは正しい結果の行列です

この入力では matrix1 × matrix2 の実際の計算結果が [[4, 4], [10, 8]] となるため、プログラムは「正しい結果の行列です」と判定します。

誤った結果の行列を入力した場合

行列の次元を入力してください: 2
1つ目の行列を入力してください:
1 2
3 4
2つ目の行列を入力してください:
2 0
1 2
検証対象の結果の行列を入力してください:
4 5
5 5
これは正しい結果の行列ではありません

こちらは入力された行列が実際の積と一致しないため、「正しい結果の行列ではありません」と表示されます。

計算量と誤り確率

1回の試行で行うのはベクトルと行列の積の計算だけなので、計算量は O(n²) で済みます。誤った積を偶然「正しい」と見逃す確率は1回につき最大 1/2 ですが、k 回独立に試行を繰り返せば、見逃す確率は 2^-k 未満まで下がります。たとえば k = 30 なら約10億分の1以下になり、実用上ほぼ確実な検証が可能です。必要に応じて試行部分をループで囲み、k 回繰り返すように拡張するとより堅牢になります。