Алгоритм Баха - Bach's algorithm

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

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

Более простой, но менее эффективный алгоритм ( ожидающий выполнения тестов на простоту) принадлежит Адаму Калаи . ${\ Displaystyle О (\ журнал ^ {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, «Генерация случайных факторизаций», часть которой доступна онлайн здесь .

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

• v
• т
• е