Алгоритм Баха - Википедия - Bachs algorithm

Алгоритм Баха^[1] вероятностный полиномиальное время алгоритм за генерация случайных чисел вместе с их факторизации, названный в честь его первооткрывателя, Эрик Бах. Это интересно, потому что неизвестен алгоритм, который эффективно факторизует числа, поэтому простой метод, а именно создание случайного числа и последующее его разложение, непрактичен.

Ожидается, что алгоритм выполняет O (log n) тесты на простоту.

Более простой, но менее эффективный алгоритм (ожидаемый, ${ Displaystyle О ( журнал ^ {2} п)}$ тесты на простоту), происходит из-за Адам Калаи.^[2]

Обзор

Алгоритм Баха дает число ${ displaystyle x}$ равномерно случайно в диапазоне ${ Displaystyle N / 2 <х leq N}$ (для данного входа ${ displaystyle N}$) вместе с его факторизацией. Он делает это, выбирая простое число ${ displaystyle p}$ и показатель степени ${ displaystyle a}$ такой, что ${ displaystyle p ^ {a} leq N}$, согласно определенному распределению. Затем алгоритм рекурсивно генерирует число ${ displaystyle y}$ В диапазоне ${ Displaystyle M / 2 <у leq M}$, куда ${ Displaystyle М = Н / р ^ {а}}$, наряду с факторизацией ${ displaystyle y}$. Затем он устанавливает ${ displaystyle x = p ^ {a} y}$, и добавляет ${ displaystyle p ^ {a}}$ к факторизации ${ displaystyle y}$ произвести факторизацию ${ displaystyle x}$. Это дает ${ displaystyle x}$ с логарифмическим распределением по желаемому диапазону; отбраковка затем используется для получения равномерного распределения.

Рекомендации

дальнейшее чтение

• Бах, Эрик. Аналитические методы в анализе и разработке теоретико-числовых алгоритмов, MIT Press, 1984. Глава 2, «Генерация случайных факторизаций», часть которой доступна в Интернете здесь.

Этот алгоритмы или же структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.