Bach’s algorithm とは

Bachのアルゴリズムは、その発見者であるEric Bachにちなんで命名された、それらの分解と同時に乱数を生成するための確率的多項式時間アルゴリズムである。数を効率的に計算するアルゴリズムは知られていないので、興味深いです。つまり、乱数を生成してそれを因数分解するという単純な方法は実用的ではありません。
このアルゴリズムは、O(log n)素数性テストを期待通りに実行する。
単純ではあるが効率の低いアルゴリズム(期待通りにO(log2 n)の素数性テストを実行する)は知られており、Adam Kalai