Жак Арсак - Программирование игр и головоломок

9873564383 = 631181 * 15643,

то вы, вероятно, сможете проверить этот результат на вашем микрокалькуляторе, А если компьютер сообщит вам, что 9873564401 — простое число, то как вы это проверите? Проделав вычисления на руках?

Вот основы метода Ж.-М. Полларда [POL].

По данному числу n (нечетному натуральному) строится последовательность по описанному ниже правилу:

— первый член последовательности равен 2;

— следующий за x элемент равен x ² − 1 по модулю n (остатку от деления x ² − 1 на n ).

Оказывается, что эта последовательность периодична. Это легко видеть. Остаток от деления на n есть неотрицательное целое, меньшее n , поэтому не может быть более n различных остатков. Поэтому неизбежно, что как только число членов превысит n , среди членов последовательности мы получим два одинаковых, что и означает периодичность последовательности. Но она может оказаться периодической с намного более коротким периодом, чем n . Вот, например, последовательность для n = 137:

a 1= 2

a 2= 3

a 3= 8

a 4= 63

a 5= 132

a 6= 24

a 7= 27

a 8= 43

a 9= 67

a 10= 104

a 11= 129

a 12= 63 = a 4

Последовательность периодична с периодом 8.

Пусть дана последовательность, вычисленная для некоторого n . Предположим, что n делится на s , и что соответствующая числу s последовательность периодична с периодом p .

Для достаточно большого i имеем a i + p = a i по модулю p , следовательно, a i + p − a i делится на p . Так как, кроме того, и n делится на p , то наибольший общий делитель (НОД) чисел a i + p − a i и n отличен от 1 [9] Повторим эти рассуждения чуть более подробно. Пусть a 1 = 2, a i +1 = a i ² − 1 mod n , b 1 = 2, b i +1 = b i ² mod s — последовательности, соответствующие числам n и s соответственно. Тогда легко доказать по индукции, что b i = a i mod s . Одним из периодов последовательности { а i } является n . Значит, n является периодом и для последовательности { b i }. Известно, что любой период последовательности кратен ее минимальному периоду, Так как p , по определению, является минимальным периодом последовательности b i , то n делится на p . — Примеч. ред. .

Построим последовательность Полларда для n = 22879:

a 1= 2

a 2= 3

a 3= 8

a 4= 63

a 5= 3968

a 6= 4271

a 7= 6877

a 8= 2235

a 9= 7602

a 10= 20928

a 11= 8486

a 12= 11982

НОД чисел a 12− a 4и n = 22879 есть 137, делитель числа n .

Если мы способны сказать, становится ли данная последовательность периодической (головоломка 1), то мы располагаем быстрым методом определения, имеет ли данное число делитель. Можете играть. Это не такая уж простая программа…

Есть тест на простоту числа, основанный на так называемой малой теореме Ферма: если n — простое, причем число n не является делителем a , то

a n −1= 1 по модулю n .

Представим n в виде n = 2 sm + 1. Назовем число n сильно псевдопростым по основанию a , если выполнено одно из следующих двух условий:

либо a m = 1 по модулю n ,

либо a m 2 r = n − 1 по модулю n = 2 sm + 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.

Метод интересен, потому что a n вычисляется за время, растущее не быстрее, чем ln n . Это утверждение вытекает из соотношений:

а 0= 1, а 1= а ,

a 2 n = ( а * а ) n , a 2 n +1= ( a * a ) n * а .

Все, что нужно для работы, у вас есть. Больше делать нечего, кроме собственно составления программы.

Кстати: знаете ли вы две универсальные конструкции в информатике? Первая — «известно, что…». Вторая — «это и нужно сделать…».

Я надеялся не приводить в этой книге никаких готовых программ. Программирую не я, а вы. И я не очень люблю смотреть, как подростки копируют программу, набирая ее на клавиатуре и при этом не отдавая себе отчета в том, что она делает и как устроена. Но сказать, что делает та или иная программа, может оказаться настоящей головоломкой, Программы, которые мы будем обсуждать, написаны на некотором воображаемом языке [10] Этот язык описан на стр.7–8 выше. Здесь лишь кратко напоминаются формы записи условных операторов и операторов цикла. — Примеч. ред. . Вам придется по крайней мере сделать усилие, чтобы перевести их на ваш обычный язык: Бейсик, LSE или Паскаль. Условная команда записывается в виде