Первым шагом алгоритма тестирования простоты AKS является проверка, является ли входное число идеальной степенью. Похоже, что это хорошо известный факт в теории чисел, поскольку в статье это не объясняется подробно. Может кто-нибудь сказать мне, как сделать это за полиномиальное время? Спасибо.
23
Ответы:
Для заданного числа n, если оно вообще можно записать как (b> 1), то b < log ( n ) + 1 . И для каждого фиксированного b проверка наличия a с a b = n может быть выполнена с помощью бинарного поиска. Таким образом, общее время работы O ( журнал 2ab b<log(n)+1 b a ab=n .O(log2n)
источник
См. Бах и Соренсон, Алгоритмы сита для тестирования идеальной мощности, Algorithmica 9 (1993), 313-328, DOI: 10.1007 / BF01228507, и DJ Bernstein, Обнаружение идеальной мощности по существу за линейное время, Math. Комп. 67 (1998), 1253-1283.
источник
Я нашел интересное и элегантное решение в статье: «О выполнении теста на простоту класса AKS», Р. Крэндалл и Дж. Пападопулос, 18 марта 2003 г.
источник
PS: все LG являются основанием 2.
Код Python:
источник