С именем знаменитого Пьера Ферма связано много тайн. Однажды он получил письмо с вопросом: «Является ли простым число 100895598169?». Ферма незамедлительно ответил, что это двенадцатизначное число является произведением двух простых чисел: 898423 и 112303.
Способ исследования числа он не раскрыл.
Отыскание простых множителей натурального числа называют для краткости «факторизацией» («фактор», значит — множитель, составная часть; в этом последнем смысле слово обычно и употребляется). Даже с такими помощниками, как электронные вычислительные машины, факторизация больших чисел — чрезвычайно трудоёмкая задача, тем более трудно сделать это «ручным способом». Несколько первых простых чисел (2, 3, 5, 7, 11, $\ldots$) легко проверяются на их пригодность в качестве возможных множителей испытуемого числа — по известным признакам делимости на эти числа. Упрощает вычисления и знание признаков делимости на какие-либо из последующих простых чисел.
Ясно также, что для всякого заданного числа $N$ достаточно испытать в качестве возможных множителей простые числа, меньшие, чем $\sqrt N$. Действительно, если у числа $N$ есть множитель $m\gt\sqrt N$, то ему соответствует, как результат деления $N$ на $m$, и некоторый множитель, меньший, чем $\sqrt N$.
Как приём факторизации можно использовать известный алгоритм Евклида для отыскания наибольшего общего делителя (НОД) двух чисел. Состоит он, как вы, быть может, помните, в следующем: находим остаток $r_1$ от деления большего числа на меньшее, затем находим остаток $r_2$ от деления предшествующего делителя на $r_1$, затем остаток $r_3$ от деления $r_1$ на $r_2$ и т. д. Последний не равный нулю остаток (он непременно существует, поскольку числа $r_i$ убывают) и есть НОД заданных чисел (если он равен 1, то они взаимно просты).
Для примера применим этот алгоритм к числам 104 и 39:
$$
\begin{aligned}
104:39&=2&&\text{(остаток 26)};\\
39:26&=1&&\text{(остаток 13)};\\
26:13&=2&&\text{(остаток 0).}
\end{aligned}
$$
Ответ: $\gcd(104,39)=13$.
Как же применить алгоритм Евклида к факторизации чисел?
Для выявления простых множителей числа $N$ образуем другое число $P$ — произведение всех простых чисел от наименьшего из «подозреваемых» множителей числа $N$ до наибольшего среди всех простых, меньших, чем $\sqrt N$. К этим числам $N$ и $P$ мы и применим алгоритм Евклида.
Пусть, например, $N=851$. Замечаем, что $\sqrt N\lt31$. Устанавливаем по признакам делимости, что $N$ не делится на 3, 7, 11, 13. Кроме того, сразу видно, что 851 при делении на 17 даёт в остатке 1. Остаётся испытать делимость $N$ на 19, 23 и 29. Для такого небольшого числа, как 851, это легко сделать прямым делением на каждый из предполагаемых множителей. Но для уяснения метода поступим так, как было бы целесообразно действовать в случае большого числа.
Образуем $P=19\cdot23\cdot29=12673$. Далее,
$$
\begin{aligned}
12673:851&=14&&\text{(остаток 759)};\\
851:759&=1&&\text{(остаток 92)};\\
759:92&=8&&\text{(остаток 23)};\\
92:23&=4&&\text{(остаток 0).}
\end{aligned}
$$
Число 23 есть НОД чисел $N$ и $P$ и, следовательно, один из множителей числа 851. Деля 851 на 23, получаем 37 — число простое.
Факторизация числа 851 окончена: $851=23\cdot37$.
Для числа, предложенного Ферма, аналогичные вычисления длились бы значительно дольше. (Попробуйте!) Похоже, что сам Ферма считал иначе. Но как?
На подступах к разгадке?
В одной из современных математических книг высказано предположение, что, по-видимому, «некоторые математики 17-го века, потратившие много усилий на разработку теории чисел, владели незнакомыми нам способами узнавать простые числа». Но так как мастера-вычислители 17-го века не раскрыли потомкам своих секретов факторизации чисел, то естественно, что способы, изобретённые позже, могли оказаться и переоткрытиями.
Ферма — один из создателей теории чисел — в своих вычислениях пользовался самыми разнообразными свойствами чисел. В частности, он, несомненно, знал, что всякое нечётное число $N$ (равно как и всякое чётное, кратное 4) можно представить в виде разности квадратов двух целых чисел $x$ и $y$:
$$
N=a\cdot b=\left(\dfrac{a+b}2\right)^2-\left(\dfrac{a-b}2\right)^2=x^2-y^2,
$$
где $a$ и $b$ ($a\gt b$) — какие-либо возможные нечётные сомножители нечётного числа $N$ (тогда $a+b$ и $a-b$ — чётные числа, а $x$ и $y$ — целые).
Если $N$ — простое число, то $a=N$, $b=1$, разложение $x^2-y^2=(x+y)(x-y)$ единственно и не даёт иных сомножителей, кроме $N$ и 1. Если же $N$ — составное, то найдётся разложение $(x+y)(x-y)$, которое даёт хотя бы одну пару множителей, отличных от $N$ и 1.
Например, простое число 17 имеет только одно представление в виде разности квадратов, а именно $17=9^2-8^2=17\cdot1$; составное же число 203 имеет два таких представления:
$$
203=102^2-101^2=203\cdot1\quad\text{и}\quad203=18^2-11^2=29\cdot7.
$$
Так в «лаборатории факторизации чисел» появляется ещё один приём, который мы назовём «факторизацией по разности квадратов». При этом для подбора требующихся квадратных чисел $x^2$ и $y^2$ можно применить такую схему. действий (алгоритм):
- найти наименьший превосходящий заданное число $N$ квадрат: $x^2$ (например, по таблице квадратов чисел или предварительно извлекая $\sqrt N$ с избытком);
- из найденного $x^2$ вычесть $N$.
Если остаток сам является квадратным числом, т. е. $x^2-B=y^2$, то процесс подбора окончен; $N=x^2-y^2=(x+y)(x-y)$. Если же остаток не есть квадрат, то надо повторить операцию вычитания $N$ из следующего по старшинству квадратного числа и так продолжать до получения квадратного остатка.
Поясним этот алгоритм примером поиска множителей двух составных чисел: $N_1=153583$ и $N_2=689$.
Для числа $N_1$: $\sqrt{153583}\approx392$; $392^2=153664$; $153664-153583=81=9^2$; имеем $153583=392^2-9^2=401\cdot383$ — оба множителя — простые числа. Заметим, попутно, что оба они близки по величине один к другому и, следовательно, к $\sqrt N$. В этом — причина краткости пути к успеху.
Для числа $N_2=689$ ближайший избыточный квадрат $729=27^2$.
Вычисляем:
$$
\begin{aligned}
27^2-N_2&=729-689=40;\\
28^2-N_2&=784-689=95;\\
29^2-N_2&=841-689=152;\\
30^2-N_2&=900-689=211;\\
.~.~.~.~.~.~.&~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.\\
33^2-N_2&=1089-689=400=20^2.
\end{aligned}
$$
Следовательно, $689=33^2-20^2=53\cdot13$.
Успех достигнут только на седьмой попытке. Сравнивая множители числа 689, мы замечаем, что они сильно различаются по величине, что и вызвало удлинение нашей процедуры.
Возможная уловка
Начиная факторизацию какого-либо составного числа $N$, мы, разумеется, не знаем заранее, близки ли по величине его сомножители. Но если несколько последовательных шагов выполнения алгоритма не привели процесс подбора требующихся квадратных чисел к завершению, — ответ определился: искомые множители не близки по величине к $\sqrt N$.
В таком случае применим хитрость: начнём всё снова, предварительно умножив заданное $N$, скажем на 3 (сохраняя тем самым нечётность). Это увеличит меньший из двух сомножителей числа $N$ в 3 раза и сделает величины сомножителей числа $3N$ более близкими между собой, а, следовательно, и к $\sqrt{3N}$.
А если заранее предположить ещё более значительное различие между сомножителями числа $N$, то можно умножить его сразу на 5, 7 или 8 (в последнем случае образуется число чётное, но представимое разностью квадратов целых чисел). Умножение на 2 в любом случае было бы непригодным, а на 4 — бесполезным. Докажите это самостоятельно.
Вернёмся к числу $N_2=689$ и применим в качестве «уловки» умножение на 5. Это даёт $5\cdot N_2=3445$; $\sqrt{3445}\approx59$; $59^2=3481$; $3481-3445=36=6^2$. Имеем $3445=59^2-6^2=65\cdot53$; $5N_2=65\cdot53$; $N_2=53\cdot13$.
Успех с одной попытки, а не с семи, как прежде.
Может быть, так и действовал Ферма?
Намереваясь применить теперь приём «факторизации по разности квадратов» к числу $N=100895598169$, дерзнём на введение дополнительного множителя. Пусть интуиция навела нас на множитель 8 (проба меньших множителей, предположим, нас не воодушевила).
Имеем $8N=807164785352$. Ищем наименьшее число, квадрат которого больше, чем $8N$:
$$
\sqrt{807164785352}=898424~\text{(с избытком)}.
$$
Далее: $898424^2-8N=898424$.
Хотя получившаяся разность и не является квадратом, продолжать применение алгоритма излишне: дерзость вознаграждена неожиданным сюрпризом — общим множителем 898424! Разложение числа $8N$ обеспечивается теперь простым вынесением общего множителя за скобки:
$$
8\cdot N=898424\cdot(898424-1)=8\cdot112303\cdot898423.
$$
Окончательно: $N=112303\cdot898423$.
...Так ли всё происходило в «лаборатории» Ферма или как-нибудь иначе — сведений нигде нет; но в любом случае наше совместное гипотетическое «путешествие» в прошлое с позиций настоящего, было, надеюсь, для читателя не бесполезным.
Упражнения
- Найти НОД чисел $80\,887$ и $40\,091$.
- Доказать, что $N=55\,637$ имеет только один простой множитель, меньший, чем 30. (Воспользоваться числом $p=17\cdot19\cdot23\cdot29=215\,441$.)
- Найти все множители числа $N$ из задачи 2.
- Применить «факторизацию по разности квадратов» к разложению числа $131\,289$ на простые множители.
- Выполнить «факторизацию по разности квадратов» числа $500\,207$. (Применить «уловку» предварительного умножения на 3.)
Применяя «факторизацию по разности квадратов» непосредственно к числу $N=20\,099$, убедитесь в том, что $20\,099=199\cdot101$.
Сколько потребовалось шагов? Зная результат разложения $N$, объясните, почему самым лучшим множителем, ускоряющим процесс разложения $N$, оказалось бы число 8? Сколько потребуется шагов для разложения числа $8N$?
