とりあえず状況の整理だけ

n が素数 p である場合を考える。
(Z/pZ)* において 2 が生成する部分群の指数ごとに素数を分類する。
（高校数学の言葉でいえば、2^n≡1 (mod p) となる最小の正の n に対し、(p-1)/n で定まる値が指数である。）

5 以上 200 以下の素数は次の通り。
指数 1 だけは、さらに mod 3 で分けておく。


指数1, mod 3 で 2
5,11,29,53,59,83,101,107,149,173,179,197

指数1, mod 3 で 1
13,19,37,61,67,131,139,163,181

指数2
7,17,23,41,47,71,79,97,103,137,167,191,193,199

指数3
43,109,157

指数4
113

指数6
31

指数8
73,89

指数10
151

指数18
127


概ね指数が大きいほどアルゴリズムの計算量が増えることが見て取れる。
今回は、指数 2 の場合に部分的に予想が証明できた。