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

11

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

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

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

Способ исследования числа он не раскрыл.

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

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

Как прием факторизацию можно использовать известный алгоритм Евклида.

*) См. например, заметку о признаках делимости на 19 и 7 в «Кванте» № 6, 1970, стр. 10.

клида для отыскания наиболее общего делителя (НОД) двух чисел. Состоит он, как вы, быть может, помните, в следующем *): находим остаток $r_1$ от деления большого числа на меньше, затем находим остаток $r_2$ от деления предшествующего делителя на $r_1$, затем остаток $r_3$ от деления $r_1$ на $r_2$ и т. д. Послений не равный нулю остаток (он непременно существует, поскольку числа $r_i$ убывают) и есть НОД заданных чисел (если он равен 1, то они взaimно просты).

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

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

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

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

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

Пусть, например, $N = 851$. Замечаем, что $\sqrt{N} < 31$. Установливаем по признакам делимости, что $N$ не делится на 3, 7, 11, 13. Кроме того, сразу видно, что 851 при делении на 17 дает в остатке 1. Остается испытыть делимость $N$ на 19, 23 и 29. Для такого необольшего числа, как 851, это легко сделать примым делением

*) Обоснование и примеры применения алгоритма Евклида приведены в статье А. Н. Виленкина «Сокращение алгебраических дробей» («Квант» № 11, 1970) и Вагутена «Алгоритм Евклида и основная теорема алфметики» («Квант» № 6, 1972).