Шрифт:
Построим последовательность Полларда для n = 22879:
a1 = 2
a2 = 3
a3 = 8
a4 = 63
a5 = 3968
a6 = 4271
a7 = 6877
a8 = 2235
a9 = 7602
a10 = 20928
a11 = 8486
a12 = 11982
НОД чисел a12– a4 и n = 22879 есть 137, делитель числа n.
Если мы способны сказать, становится ли данная последовательность периодической (головоломка 1), то мы располагаем быстрым методом определения, имеет ли данное число делитель. Можете играть. Это не такая уж простая программа…
Есть тест на простоту числа, основанный на так называемой малой теореме Ферма: если n — простое, причем число n не является делителем a, то
an– 1 = 1 по модулю n.
Представим n в виде n = 2sm + 1. Назовем число n сильно псевдопростым по основанию a, если выполнено одно из следующих двух условий:
либо am = 1 по модулю n,
либо am2r = n– 1 по модулю n = 2sm + 1 для некоторого r, 0 <= r < s.
Очень мало сильно псевдопростых чисел, не являющихся простыми; так
2047 = 23 * 89 — сильно псевдопросто по основанию 2,
1373653 = 829 * 1657 — по основанию 2 и 3,
25326001 = 2251 * 11251 — по основанию 2, 3 и 5,
3215031751 = 151 * 751 * 28351 — по основанию 2, 3, 5 и 7.
Метод интересен, потому что an вычисляется за время, растущее не быстрее, чем ln n. Это утверждение вытекает из соотношений:
а0 = 1, а1 = а,
a2n = (а * а)n, a2n+1 = (a * a)n * а.
Все, что нужно для работы, у вас есть. Больше делать нечего, кроме собственно составления программы.
Кстати: знаете ли вы две универсальные конструкции в информатике? Первая — «известно, что…». Вторая — «это и нужно сделать…».
Таинственные программы
Я надеялся не приводить в этой книге никаких готовых программ. Программирую не я, а вы. И я не очень люблю смотреть, как подростки копируют программу, набирая ее на клавиатуре и при этом не отдавая себе отчета в том, что она делает и как устроена. Но сказать, что делает та или иная программа, может оказаться настоящей головоломкой, Программы, которые мы будем обсуждать, написаны на некотором воображаемом языке [10] . Вам придется по крайней мере сделать усилие, чтобы перевести их на ваш обычный язык: Бейсик, LSE или Паскаль. Условная команда записывается в виде
10
Этот язык описан на стр.7–8 выше. Здесь лишь кратко напоминаются формы записи условных операторов и операторов цикла. — Примеч. ред.
(последовательность команд выполняется тогда и только тогда, когда условие истинно)
или
(если условие истинно, то выполняется последовательность команд, заключенная между ТО и ИНАЧЕ, в противном случае выполняется та последовательность команд, которая расположена между ИНАЧЕ и КОНЕЦ_ЕСЛИ).
В обоих случаях КОНЕЦ_ЕСЛИ играет роль закрывающей скобки, связанной с открывающей скобкой ЕСЛИ. Мы будем использовать цикл
Последовательность команд, содержащаяся между ВЫПОЛНЯТЬ и ВЕРНУТЬСЯ, повторяется, ПОКА условие истинно.
* Головоломка 17. Для забавы. Вот легко понимаемая программа. Здесь n и b — два натуральных числа и b нечетно (это существенно)