Б. А. Кордемский


Так или не так
действовал Ферма?

(о факторизации чисел)




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

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

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

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

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

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

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

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

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

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

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

Пусть, например, N = 851. Замечаем, что < 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:

N = a·b ( a + b

2

) 2  –  ( ab

2

) 2  = x2y2,

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

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

Например, простое число 17 имеет только одно представление в виде разности квадратов, а именно 17 = 92 – 82 = 17·1; составное же число 203 имеет два таких представления: 203 = 1022 – 1012 = 203·1  и  203 = 182 – 112 = 29·7.

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

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

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

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

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

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

Вычисляем

272N2 = 729 – 689 = 40;
282N2 = 784 – 689 = 95;
292N2 = 841 – 689 = 152;
302N2 = 900 – 689 = 211;
  .   .   .   .   .   .   .   .   .   . 
332N2 = 1089 – 689 = 400 = 202.

Следовательно, 689 = 332 – 202 = 53·13.

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

Возможная уловка

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

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

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

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

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

Может быть, так и действовал Ферма?

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

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

 807164785352  = 898424 (с избытком).

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

N = 898424·(898424 – 1) = 8·112303·898423.

Окончательно: 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?

Hosted by uCoz