Алгоритм Баха - Bachs algorithm - Wikipedia

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

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

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

Обзор

Алгоритм Баха дает число равномерно случайно в диапазоне (для данного входа ) вместе с его факторизацией. Он делает это, выбирая простое число и показатель степени такой, что , согласно определенному распределению. Затем алгоритм рекурсивно генерирует число В диапазоне , куда , наряду с факторизацией . Затем он устанавливает , и добавляет к факторизации произвести факторизацию . Это дает с логарифмическим распределением по желаемому диапазону; отбраковка затем используется для получения равномерного распределения.

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

  1. ^ Бах, Эрик (1988), «Как сгенерировать факторизованные случайные числа», SIAM Журнал по вычислениям, 17 (2): 179–193, Дои:10.1137/0217012, МИСТЕР  0935336
  2. ^ Калаи, Адам (2003), «Легкое создание случайных факторизованных чисел», Журнал криптологии, 16 (4): 287–289, Дои:10.1007 / s00145-003-0051-5, МИСТЕР  2002046

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

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