二次時間で
曲がっていた、を直す。

受け取った Issue の本文を抜粋します。

expected: 暗号化と同じように O(N) で復号できる
actual:   n=5,000 で 26 ms の復号時間
          入力 2 倍で復号時間 4 倍増

さらに該当箇所まで指摘があり、cipher.rs のwhile remaining > 0 ループを「remaining で N 回、 内側の for で N 回 → n²」と要約しています。 この見立てが正しいかどうか、まずは数字で確かめにいきました。

直し方は知らん。

いいんです、こちらが調べます。

報告者と異なる OS（Windows / x86_64）でも同じ傾向が出るかを確認するため、 ハードウェアは別物・ツールチェーンとアルゴリズムだけ揃えました。

• 報告: macOS 14.6 ARM64 / rustc 1.92 / --release
• 追試: Windows 11 x86_64 / rustc 1.92 / --release
• commit: e499fcf (main, v0.2.0)
• 暗号化戦略: canonical (v0.1 既定) と chain (v0.2)
• アンカー位置: n / 2 (中央)
• 各サイズ 5 回計測して平均

ベンチは crates/core/examples/bench_decrypt.rsに追加し、誰でもワンコマンドで再走できるようにしました。

cargo run --release --example bench_decrypt -p musubi-core

出力は CSV 1 行 = 1 (n, strategy, encrypt_ms, decrypt_ms) です。 再現性のため鍵生成・乱数はすべて固定シードで動かしています。

数字は ms 単位の wall-clock。 doubling 列はひとつ上の n から見た倍率。 理論的には線形 (O(n)) なら 2.0×、二次 (O(n²)) なら 4.0× になるはずです。

canonical 列の倍率は 4 周辺に張り付き、chain 列の倍率は 2 周辺に張り付いています。 報告者の指摘どおり、canonical は完全な二次曲線です。 n=4,000 から 32,000 まで 8 倍にすると、 canonical は 5.2 → 296 ms（57×、理論的には 64× の 4× = 64×なのでほぼ理論値）に膨らみます。

対数-対数プロット

両軸を対数にすると、傾き = 計算量の指数。 canonical はほぼ 傾き 2、 chain はほぼ 傾き 1。

該当コードはほぼ報告者の引用通りです。

while remaining > 0 {
    let mut progress = false;
    for i in 0..n {
        if chars[i].is_some() { continue; }
        let rel = cipher.relations[i].as_ref().ok_or(...)?;
        let ref_idx = rel.reference();
        let Some(ref_char) = chars[ref_idx] else { continue; };
        chars[i] = Some(apply_relation(*rel, ref_char, key)?);
        progress = true;
        remaining -= 1;
    }
    if !progress { return Err(...); }
}

アルゴリズム的には「未解決スロットを全走査して、 参照先が解決済のものだけ埋める」 を、何も埋まらなくなるまで繰り返す素朴な方式です。 ここで効くのが参照グラフの形。

canonical の参照グラフ

encrypt（canonical）はアンカーから両側へ隣接位置だけを参照します。 長さ 11、 アンカー位置 5 ならグラフはこんな見た目：

位置:  0   1   2   3   4   5*  6   7   8   9   10
        ←   ←   ←   ←   ← anchor →   →   →   →   →
参照先: 1 ← 2 ← 3 ← 4 ← 5         5 → 6 → 7 → 8 → 9
                                                        ↑
                                          (10 は 9 を参照)

右側は i = 6, 7, 8, 9, 10 の順に走査され、 都度ひとつ前が解決済になっているので 1 パスで全員埋まる。

ところが左側は i = 0, 1, 2, 3, 4 の順に走査される一方で、 参照先は i + 1。 1 パス目で埋まるのは 位置 4 ひとつだけ。 位置 3 を埋めるにはもう 1 パス、位置 2 はさらにもう 1 パス…と 左側の長さ分のパスが要ります。

一般化すると、左側 L 文字、右側 R 文字のとき、 外側ループ回数 = max(L, R)、 各パスで内側 for は n 回、 よって総コスト ≈ n × max(L, R) ≈ n²/2。 アンカーが端っこなら定数倍だけ良くなりますが、 既定の中央アンカーでは ぴったり n²/2 です。

なぜ chain は曲がらないのか

v0.2 で追加した encrypt_chain はアンカーを根としたランダム生成木を作ります。 「すでに解決済の集合」から一様に親を選ぶため、 木の高さは期待値で O(√n) 程度。

この場合、解決の波は木の高さ分だけ広がれば全員に届くので、 外側ループは O(√n) 回、 内側 for が n 回で O(n × √n)。 実測の n^1.16 はキャッシュ効果やパス当たり並列に多数解決できる効果で、 理論値より良く出ているだけです。

アルゴリズム的に直すのは簡単です。 参照グラフはアンカー根の有向木なので、BFS で位相順序を作って一回だけ走らせると O(n) になります。

// 1. 子ども一覧を構築 — O(n)
let mut children: Vec<Vec<usize>> = vec![vec![]; n];
for (i, rel) in cipher.relations.iter().enumerate() {
    if let Some(r) = rel { children[r.reference()].push(i); }
}

// 2. アンカーから BFS — 解決順を決める
let mut order = Vec::with_capacity(n);
let mut queue = VecDeque::from([anchor_pos]);
while let Some(p) = queue.pop_front() {
    order.push(p);
    for &c in &children[p] { queue.push_back(c); }
}

// 3. 解決順に走らせる — 各位置 1 回だけ
chars[anchor_pos] = Some(cipher.anchor.character);
for &i in &order[1..] {
    let rel = cipher.relations[i].as_ref().ok_or(...)?;
    let ref_char = chars[rel.reference()].expect("BFS guarantees parent first");
    chars[i] = Some(apply_relation(*rel, ref_char, key)?);
}

これで n=32,000 が 296 ms → 推定 1 ms 前後に下がります。 encrypt も chain も既に O(n) なので、 décrypt をそろえれば暗号往復が 全工程線形になります。

サニティチェックも忘れずに

既存実装が暗黙に持っていた検証「グラフに閉路や到達不能ノードがある時にエラー」は BFS 後の order.len() == n で同等以上に取れます。 ここを落とすと改竄された暗号文を黙って受け入れる回帰になるので、 実装時の最大の落とし穴です。

修正方針 §05 に書いた擬似コードをほぼそのままの形でcrates/core/src/cipher.rs に書き、 PR #22 としてマージしました。 実装の核は 25 行ほどで、 暗号文フォーマットには手を入れていません。

// 1. 子ども一覧を O(n) で構築
let mut children: Vec<Vec<usize>> = vec![Vec::new(); n];
for (i, rel) in cipher.relations.iter().enumerate() {
    if i == anchor_pos { continue; }
    let rel = rel.as_ref().ok_or_else(|| MusubiError::MalformedCiphertext {
        reason: format!("missing relation at position {i}"),
    })?;
    let ref_idx = rel.reference();
    if ref_idx >= n {
        return Err(MusubiError::MalformedCiphertext { /* ... */ });
    }
    children[ref_idx].push(i);
}

// 2. アンカーから BFS。 親が先に解決済みなのが保証される。
let mut queue: VecDeque<usize> = VecDeque::with_capacity(n);
queue.push_back(anchor_pos);
let mut visited: usize = 1;
while let Some(p) = queue.pop_front() {
    for &c in &children[p] {
        let rel = cipher.relations[c].as_ref().expect("validated");
        let ref_char = chars[p].expect("BFS visits parent before child");
        chars[c] = Some(apply_relation(*rel, ref_char, key)?);
        queue.push_back(c);
        visited += 1;
    }
}

// 3. 閉路 / 到達不能の検出は visited != n でまかなう。
if visited != n { return Err(MusubiError::MalformedCiphertext { /* ... */ }); }

同じハードウェア・同じシードで再走したベンチです。 canonical の倍率が 2× 周辺に 張り付いて、 n=32,000 でも 2.4 ms におさまっています。

ベンチ越しに見える事実：

• canonical の 倍率はすべて 1.8 – 2.4 ×。 理論値（線形）の 2.0× にぴたり載る。
• n=32,000 で 124 倍速い。 n が大きいほど効くのが二次から線形への落ち方の典型的な挙動。
• chain は前から線形だったので わずかに遅くなっています（children の事前構築コスト分）。 ただし n=32k で 2.3 ms と十分小さく、 両戦略が同じ計算量レジームに揃ったほうが運用はシンプル。

対数-対数プロット — 直線の傾き 1

§03 と同じスケールで、 修正前後の canonical だけを並べたものです。 赤いラインが上の slope 2 から 緑のラインの slope 1 へ落ちたのが 一目でわかります。

「直し方は知らん」と書かれた報告に、 ベンチで応答して修正案で返し、 修正をマージして数字で締める。 OSS の糸の結び方。