群位数計算において、群位数$\#G$が、$|\#G-c| \le w$ ($c,w$は正の実数)
という範囲にある時、通常のBSGSアルゴリズムではBS幅（Baby Stepの
り返し回数）は通常$\sqrt{w}$)が使われる。
しかしながら、群演算回数の平均値を最小にする為にはもっと小さな
BS値を使えば良い事が判っている。
一方、Blackburn & Teske によって $|\#G-c| \le x$である確率分布が既知
である時、探索区間によって異なるBS値を用いる方式が提案された。
この講演では、彼らの方式を数学的に厳密な形で定式化しなおし、
この方式が有効であるか否かの判定条件を与える。
（本研究はNTTの内山氏、早稲田大学の金山氏との共同研究です。)
プログラムに戻る ．