Б. А. Кордемский Так или не так действовал Ферма? (о факторизации чисел)

С именем знаменитого Пьера Ферма связано много тайн. Однажды он получил письмо с вопросом: «Является ли простым число 100895598169?» Ферма незамедлительно ответил, что это двенадцатизначное число является произведением двух простых чисел: 898423 и 112303. Способ исследования числа он не раскрыл.

Отыскание простых множителей натурального числа называют для краткости «факторизацией» («фактор», значит — множитель, составная часть; в этом последнем смысле слово обычно и употребляется). Даже с такими помощниками, как электронные вычислительные машины, факторизация больших чисел — чрезвычайно трудоёмкая задача, тем более трудно сделать это «ручным способом». Несколько первых простых чисел (2, 3, 5, 7, 11, ...) легко проверяются на их пригодность в качестве возможных множителей испытуемого числа — по известным признакам делимости на эти числа. Упрощает вычисления и знание признаков делимости на какие-либо из последующих простых чисел.

Ясно также, что для всякого заданного числа N достаточно испытать в качестве возможных множителей простые числа, меньшие, чем √N . Действительно, если у числа N есть множитель m > √N , то ему соответствует, как результат деления N на m, и некоторый множитель, меньший, чем √N .

Как приём факторизации можно использовать известный алгоритм Евклида для отыскания наибольшего общего делителя (НОД) двух чисел. Состоит он, как вы, быть может, помните, в следующем: находим остаток r₁ от деления большего числа на меньшее, затем находим остаток r₂ от деления предшествующего делителя на r₁, затем остаток r₃ от деления r₁ на r₂ и т.д. Последний не равный нулю остаток (он непременно существует, поскольку, числа r_i убывают) и есть НОД заданных чисел (если он равен 1, то они взаимно просты).

Для иллюстрации применим этот алгоритм к числам 104 и 39:

104 : 39 = 2 (остаток 26);

39 : 26 = 1 (остаток 13);

26 : 13 = 2 (остаток 0).

Ответ: НОД (104, 39) = 13.

Как же применить алгоритм Евклида к факторизации чисел?

Для выявления простых множителей числа N образуем другое число P — произведение всех простых чисел от наименьшего из «подозреваемых» множителей числа N до наибольшего среди всех простых, меньших, чем √N . К этим числам N и P мы и применим алгоритм Евклида.

Пусть, например, N = 851. Замечаем, что √N  < 31. Устанавливаем по признакам делимости, что N не делится на 3, 7, 11, 13. Кроме того, сразу видно, что 851 при делении на 17 даёт в остатке 1. Остаётся испытать делимость N на 19, 23 и 29. Для такого небольшого числа, как 851, это легко сделать прямым делением на каждый из предполагаемых множителей. Но для уяснения метода поступим так, как было бы целесообразно действовать в случае большого числа.

Образуем P = 19·23·29 = 12673. Далее, 12673 : 851 = 14 (остаток 759), 851 : 759 = 1 (остаток 92); 759 : 92 = 8 (остаток 23); 92 : 23 = 4 (остаток 0).

Число 23 есть НОД чисел N и P и, следовательно, один из множителей числа 851. Деля 851 на 23, получаем 37 — число простое.

Факторизация числа 851 окончена: 851 = 23·37.

Для числа, предложенного Ферма, аналогичные вычисления длились бы значительно дольше. (Попробуйте!) Похоже, что сам Ферма считал иначе. Но как?

В одной из современных математических книг высказано предположение, что, по-видимому, «некоторые математики XVII века, потратившие много усилий на разработку теории чисел, владели незнакомыми нам способами узнавать простые числа». Но так как мастера-вычислители XVII века не раскрыли потомкам своих секретов факторизации чисел, то естественно, что способы, изобретённые позже, могли оказаться и переоткрытиями.

Ферма — один из создателей теории чисел — в своих вычислениях пользовался самыми разнообразными свойствами чисел. В частности, он, несомненно, знал, что всякое нечётное число N (равно как и всякое чётное, кратное 4) можно представить в виде разности квадратов двух целых чисел x и y:

где a и b (a > b) — какие-либо возможные нечётные сомножители нечётного числа N (тогда a+b и a–b — чётные числа, а x и y — целые).

Если N — простое число, то a=N, b=1, разложение x² – y² = (x + y)(x – у) единственно и не даёт иных сомножителей, кроме N и 1. Если же N — составное, то найдётся разложение (x + у)(x – y), которое даёт хотя бы одну пару множителей, отличных от N и 1.

Например, простое число 17 имеет только одно представление в виде разности квадратов, а именно 17 = 9² – 8² = 17·1; составное же число 203 имеет два таких представления: 203 = 102² – 101² = 203·1  и  203 = 18² – 11² = 29·7.

Так в «лаборатории факторизации чисел» появляется ещё один приём, который мы назовём «факторизацией по разности квадратов». При этом для подбора требующихся квадратных чисел x² и y² можно применить такую схему действий (алгоритм):

1. найти наименьший превосходящий заданное число N квадрат: x² (например, по таблице квадратов чисел или предварительно извлекая √N  с избытком);
2. из найденного x² вычесть N.

Если остаток сам является квадратным числом, то есть x² – N = y², то процесс подбора окончен; N = x² – y² = (x + y)(x – y). Если же остаток не есть квадрат, то надо повторить операцию вычитания N из следующего по старшинству квадратного числа и так продолжать до получения квадратного остатка.

Поясним этот алгоритм примером поиска множителей двух составных чисел: N₁ = 153583  и  N₂ = 689.

Для числа N₁: √ 153583  » 392; 392² = 153664; 153664 – 153583 = 81 = 9²;  имеем  153583 = 392² – 9² = 401·383 — оба множителя — простые числа. Заметим, попутно, что оба они близки по величине один к другому и, следовательно, к √N . В этом — причина краткости пути к успеху.

Для числа N₂ = 689 ближайший избыточный квадрат 729 = 27².

Вычисляем

Следовательно, 689 = 33² – 20² = 53·13.

Успех достигнут только на седьмой попытке. Сравнивая множители числа 689, мы замечаем, что они сильно различаются по величине, что и вызвало удлинение нашей процедуры.

Начиная факторизацию какого-либо составного числа N, мы, разумеется, не знаем заранее, близки ли по величине его сомножители. Но если несколько последовательных шагов выполнения алгоритма не привели процесс подбора требующихся квадратных чисел к завершению, — ответ определился: искомые множители не близки по величине к √N .

В таком случае применим хитрость: начнём всё снова, предварительно умножив заданное N, скажем на 3 (сохраняя тем самым нечётность). Это увеличит меньший из двух сомножителей числа N в 3 раза и сделает величины сомножителей числа 3N более близкими между собой, а, следовательно, и к √ 3N .

А если заранее предположить ещё более значительное различие между сомножителями числа N, то можно умножить его сразу на 5, 7 или 8 (в последнем случае образуется число чётное, но представимое разностью квадратов целых чисел). Умножение на 2 в любом случае было бы непригодным, а на 4 — бесполезным. Докажите это самостоятельно.

Вернёмся к числу N₂ = 689 и применим в качестве «уловки» умножение на 5. Это даёт 5·N = 3445; √ 3445  » 59; 59² = 3481; 3481 – 3445 = 36 = 6². Имеем 3445 = 59² – 6² = 65·53; 5N₂ = 65·53; N₂ = 53·13.

Успех с одной попытки, а не с семи, как прежде.

Намереваясь применить теперь приём «факторизации по разности квадратов» к числу N = 100895598169, дерзнём на введение дополнительного множителя. Пусть интуиция навела нас на множитель 8 (проба меньших множителей, предположим, нас не воодушевила).

Имеем 8N = 807164785352. Ищем наименьшее число, квадрат которого больше, чем 8N:

Далее: 898424² – 8N = 898424. Хотя получившаяся разность и не является квадратом, продолжать применение алгоритма излишне: дерзость вознаграждена неожиданным сюрпризом — общим множителем 898424! Разложение числа 8N обеспечивается теперь простым вынесением общего множителя за скобки:

Окончательно: N = 112303·898423.

...Так ли всё происходило в «лаборатории» Ферма или как-нибудь иначе — сведений нигде нет; но в любом случае наше совместное гипотетическое «путешествие» в прошлое с позиций настоящего, было, надеюсь, для читателя не бесполезным.

1. Найти НОД чисел 80 887 и 40 091.
2. Доказать, что N = 55 637 имеет только один простой множитель, меньший, чем 30. (Воспользоваться числом p = 17·19·23·29 = 215 441.)
3. Найти все множители числа N из задачи 2.
4. Применить «факторизацию по разности квадратов» к разложению числа 131 289 на простые множители.
5. Выполнить «факторизацию по разности квадратов» числа 500 207. (Применить «уловку» предварительного умножения на 3).
6. Применяя «факторизацию по разности квадратов» непосредственно к числу N = 20 099, убедитесь в том, что 20 099 = 199·101. Сколько потребовалось шагов? Зная результат разложения N, объясните, почему самым лучшим множителем, ускоряющим процесс разложения N, оказалось бы число 8? Сколько потребуется шагов для разложения числа 8N?