Книга: Программирование игр и головоломок

Простые числа

Простые числа

??** Головоломка 16. Чемпион головоломок.

На мой взгляд, наиболее замечательная арифметическая головоломка, над которой мне пришлось особенно долго работать и которая дала мне возможность получить некоторые удовлетворительные результаты, — это, конечно, проблема простых чисел. Пусть дано число n (конечно, нечетное) и достаточно большое; сказать, является ли оно простым и, если можно, дать его разложение на простые множители.

Если не предполагать, что n велико, то есть простой способ действовать: делить n на простые числа и смотреть, удается ли деление без остатка. Если да, то число составное и допускает разложение в произведение. Впрочем, при таком методе многие делители можно вообще не рассматривать. Если n есть произведение двух сомножителей p и q:

n = p * q,

то либо p = q, либо один из сомножителей больше другого, так что можно считать, что p — делитель, q — частное и p ? q. Поэтому будем делить n на последовательно возрастающие простые числа, для которых частное больше или равно делителю. Так как мы не располагаем таблицей простых чисел, то используем последовательность Делителей, которая заведомо содержит все простые числа, например, последовательность нечетных чисел или лучше целых чисел вида 6k ± 1.

Число операций растет как квадратный корень из n. Если вы добавите к n одну цифру, то вы увеличите время вычисления примерно раза в три. Но более важно другое. Если вы увеличиваете n, вы можете превысить «арифметические способности» своего компьютера. Как вы узнаете, правильно ли выполнено деление? Предел, которого вы можете достичь таким образом, существенно зависит от марки вашего микрокомпьютера[8].

Таким образом, вы должны бороться со следующими трудностями:

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

— число требуемых операций;

— доверие к вашей программе. Если ваша машина сообщает вам, что

9873564383 = 631181 * 15643,

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

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

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

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

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

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

a₁ = 2

a₂ = 3

a₃ = 8

a₄ = 63

a₅ = 132

a₆ = 24

a₇ = 27

a₈ = 43

a₉ = 67

a₁₀ = 104

a₁₁ = 129

a₁₂ = 63 = a₄

Последовательность периодична с периодом 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].

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

a₁ = 2

a₂ = 3

a₃ = 8

a₄ = 63

a₅ = 3968

a₆ = 4271

a₇ = 6877

a₈ = 2235

a₉ = 7602

a₁₀ = 20928

a₁₁ = 8486

a₁₂ = 11982

НОД чисел a₁₂ ? a₄ и n = 22879 есть 137, делитель числа n.

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

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

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

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

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

либо a^m2r = 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. Это утверждение вытекает из соотношений:

а⁰ = 1, а¹ = а,

a²ⁿ = (а * а)ⁿ, a²ⁿ⁺¹ = (a * a)ⁿ * а.

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

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

Оглавление книги