復号は二次時間で
曲がっている。

受け取った 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 で同等以上に取れます。 ここを落とすと改竄された暗号文を黙って受け入れる回帰になるので、 実装時の最大の落とし穴です。

• 調査完了 — 報告どおり O(n²) 確定。 ベンチ ・原因 ・修正方針までこのページに記録。
• 修正リリース — v0.2.1 で BFS 化を入れる予定。 PR は別ブランチで進めます。
• 影響範囲— n < 数百であれば実用上気付かない（< 1ms）。 対話的な復号で気になり始めるのは n > 5,000 から。 受け取った報告のラインです。
• ワークアラウンド — 暗号化時に--strategy chain を渡すと現状でも線形時間で復号できる。

「直し方は知らん」と書かれた報告に、 ベンチで応答して修正案で返す。 これくらいやらないと、 OSS の糸はほどけて切れる。