Факторизация чисел
Страница переведена на новый сайт https://myeducation.su/ :
страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)
|
Считаете сайт полезным? |
Квант 7 июль 1972
Ниже текст для быстрого знакомства с темой. Формулы отображаются некорректно. Если тема вас заинтересовала, нажмите на ссылку выше и скачивайте оригинал.
И не забудьте поделиться страницей в соц. сетях! 🙂
Так или не так действовал Ферма?
С именем знаменитого Пьера Ферма
связано много тайн. Однажды он
получил письмо с вопросом: «Является
ли простым число 100895598169?»
Ферма незамедлительно ответил, что
это двенадцатизначное число является
произведением двух простых чисел:
898423 и 112303.
Способ исследования числа он не
раскрыл.
Огыскание простых множителей
натурального числа называют для
краткости «факторизацией» («фактор
», значит — множитель, составная
часть; в этом последнем смысле
слово обычно и употребляется). Даже
с такими помощниками, как электронные
вычислительные машины, факторизация
больших чисел — чрезвычайно
трудоемкая задача, тем более
трудно сделать это «ручным способом
». Несколько первых простых чисел
(2, 3, 5, 7, 11, . . .) легко проверяются
на их пригодность в качестве
возможных множителей испытуемого
числа — по известным признакам
делимости на эти числа. Упрощает
вычисления и знание
признаков делимости на какие-либо
из последующих простых чисел *).
Ясно также, что дл^ всякого за данного
числа N достаточно испытать
в качестве возможных множителей^
простые числа, меньшие, чем
V N . Действительно, если у числа N
есть множитель m > V N , то ему
соответствует, как результат деления
N на т, и некоторый множитель,
меньший, чем V N .
Как прием факторизации можно
использовать известный алгоритм Ев-
•) См. например, заметку о признаках
делимости на 19 и / в «Кванте» ЛГг 6, 1970,
стр. 10.
Б. А. Кордемский
клида для отыскания наибольшего
общего делителя (НОД) двух чисел.
Состоит он, как вы, быть может,
помните, в следующем *): находим
остаток л, от деления большего числа
на меньшее, затем находим остаток
г 2 от деления предшествующего делителя
на г г, затем остаток г3 от деления
г 1 на Го и т. д. Последний не
равный нулю остаток (он непременно
существует, поскольку числа
г{- убывают) и есть НОД заданных
чисел (если он равен 1, то они взаимно
просты).
Для примера применим этот алгоритм
к числам 104 и 39:
104 : 39 — 2 (остаток 26);
39 : 26 (остаток 13);
26 : 13 = 2 (остаток 0).
О т в е т : НОД (104,39) = 13.
Как же применить алгоритм Евклида
к факторизации чисел?
Для выявления простых множителей
числа N образуем другое число
Р — произведение всех простых чисел
ог наименьшего из «подозреваемых
» множителей числа N до наибольшего
среди всех простых, меньших,
чем } N. К этим числам N н Р мы
и применим алгоритм Евклида.
Пусть, например, N — 851. Замечаем,
что Уд?<31. Устанавливаем
по признакам делимости, что N не делится
на 3, 7, 11, 13. Кроме того,
сразу видно, что 851 при делении на
17 дает в остатке 1 . Остается испытать
делимость N на 19, 23 и 29. Для
такого небольшого числа, как 851,
это легко сделать прямым делением
*) Обоснование и примеры применения
алгоритма Евклида приведены в статье
Л. Н. Виленкина «Сокращение алгебраических
дробен» («Квант» Xs 11, 1970) и Ваг\-
тена «Алгоритм Евклида и основная теорема
арифметики» («Квант» .Vs б, 1972).
11
на каждый из предполагаемых множителей.
Но для уяснения метода
поступим так, как было бы целесообразно
действовать в случае большого
числа.
Образуем Р = 19 *23-29 = 12673.
Далее, 12673 : 851 = 14 (остаток 759),
851 : 759=1 (остаток 92); 759 : 92—8
(остаток 23); 92 : 23 = 4 (остаток 0).
Число 23 есть НОД чисел N и Р и,
следовательно, один из множителей
числа 851. Деля 851 на 23, получаем
37 — число простое.
Факторизация числа 851 окончена:
851 = 23-37.
Для числа, предложенного Ферма,
аналогичные вычисления длились бы
значительно дольше. (Попробуйте!)
Похоже, что сам Ферма считал иначе.
Но как?
На подступах к разгадке?
В одной из современных математических
книг высказано предположение,
что, по-видимому, «некоторые
математики 17-го века, потратившие
много усилий на разработку теории
чисел, владели незнакомыми нам способами
узнавать простые числа». Но
так как мастера-вычислители 17-го
века не раскрыли потомкам своих
секретов факторизации чисел, то естественно,
что способы, изобретенные
позже, могли оказаться и переоткры-
тиямй.
Ферма — один из создателей теории
чисел — в своих вычислениях
пользовался самыми разнообразными
свойствами чисел. В частности, он,
несомненно, знал, что всякое нечетное
число N (равно как и всякое четное,
кратное. 4) можно представить
в виде разности квадратов двух целых
чисел х и у:
где а и b (а > Ь) — какие-либо возможные
нечетные сомножители нечетного
числа N (тогда а + b
и а — b — четные числа,, а х и у —
целые).
Если N — простое число, то а —
— N, b = 1, разложение х2 — у 2 —
— (х т- у){х — у) единственно и не
дает иных сомножителей, кроме N и 1.
Если же N — составное, то найдется
разложение (х + у)(х — у), которое
дает хотя бы одну пару множителей,
отличных от N и 1 .
Например, простое число 17 имеет
только одно представление в виде
разности квадратов, а именно 17 *-
— 92—82 — 17-1; составное же число
203 имеет два таких представления:
203 = 1022—1012 = 203-1
203 = 182—112 = 29-7.
Так в «лаборатории факторизации
чисел» появляется еще один прием,
который мы назовем «факторизацией
по разности квадратов». При этом
для подбора требующихся квадратных
чисел х2 и у 2, можно применить
такую схему действий (алгоритм):
1) найти наименьший превосходящий
заданное число N квадрат: х2 (например,
по таблице квадратов чисел или
предварительно извлекая \ fN c избытком);
2) из найденного х г вычесть N.
Если остаток сам является квадратным
числом, то есгь х2—N — у 2,
то процесс подбора окончен; N —
= х 2—у 2 = (х — f у)(х — у). Если же
остаток не есть квадрат, то надо
повторить операцию вычитания N
из следующего по старшинству квадратного
числа и так продолжать до
получения квадратного остатка.
Поясним этот алгоритм примером
поиска множителей двух составных
чисел: Л% = 153583 и N 2 — 689.
Для числа N t : 1/153583 » 392;
3922 = 153664; 153664—153583 =
=* 81 — 92; имеем 153583 = 3922—
— 92 = 401 -383 — оба множителя —
простые числа. Заметим, попутно, что
оба они близки по величине один
к другому и, следовательно, к V N .
В этом — причина краткости пути
к успеху.
Для числа N 2 = 689 ближайший
избыточный квадрат 729 = 272.
12
Вычисляем:
272—N 2 = 729—689=40;
28s—N 2= 784—689 = 95;
292—N 2—841—689= 152;
301— 2=900—689=211;
332—N i =1089—689==400=202.
Следовательно, 689 = 332—202=
« 53-13.
Успех достигнут только на седьмой
попытке. Сравнивая множители
числа 689, мы замечаем, что они сильно
различаются по величине, что и вызвало
удлинение нашей процедуры.
Возможная уловка
Начиная факторизацию какого-либо
составного числа N, мы, разумеется,
не знаем заранее, близки ли по
величине его сомножители. Но если
несколько последовательных шагов
выполнения алгоритма не привели
процесс подбора требующихся квадратных
чисел к завершению,— ответ
определился: искомые множители не
близки по величине к Уд?.
В таком случае применим хитрость:
начнем все снова, предварительно
умножив заданное N, скажем
на 3 (сохраняя тем самым нечетность).
Это увеличит меньший из двух сомножителей
числа N в 3 раза и сделает
величины сомножителей числа 3N
более близкими между собой, а, следовательно,
и к уздг.
А если заранее предположить еще
более значительное различие между
сомножителями числа N, то можно
умножить его сразу на 5, 7 или 8
(в последнем случае образуется число
четное, но представимое разностью
квадратов целых чисел). Умножение
на 2 в любом случае было бы непригодным,
а на 4 — бесполезным.
Докажите это самостоятельно.
Вернемся к числу ТУ2 = 689 и применим
в качестве «уловки» умножение
на 5. Это дает 5 -N 2= 3445;
У 5 4 4 5 « 5 9 ; 592 =3481; 3481—3445=
= 36 = 62. Имеем 3445=592—62 = 65х
Х53; 5N2= 6 5 *53; W2=53-13.
Успех с одной попытки, а не с семи,
как прежде.
Может быть, так и действовал Ферма?
Намереваясь применить теперь
прием «факторизации по разности
квадратов» к числу N = 100895598169,
дерзнем на введение дополнительного
множителя. Пусть интуиция навела
нас на множитель 8 (проба меньших
множителей, предположим, нас не
воодушевила).
Имеем 8N = 807164785352. Ищем
наименьшее число, квадрат которого
больше, чем SN:
V807164785352=898424 (с избытком)
Далее: 8984242—SN = 898424.
Хотя получившаяся разность и не
является квадратом, продолжать применение
алгоритма излишне: дерзость
вознаграждена неожиданным сюрпризом
— общим множителем 898424!
Разложение числа 8N обеспечивается
теперь простым вынесением общего
множителя за скобки: 8- #=898424 X
X (898424—1)=8 • 112303 • 898423.
Окончательно: N ~ 112303-898423.
…Так ли все происходило в «лаборатории
» Ферма или как-нибудь
иначе — сведений нигде нет; но в любом
случае наше совместное гипотетическое
«путешествие» в прошлое с позиций
настоящего, было, надеюсь,
для читателя не бесполезным.
Упражнения
1. Найти НОД чисел 80 887 и 40 091.
2. Доказать, что N=55 637 имеет только
один простой множитель, меньший, чем 30.
(Воспользоваться числом р= 17-19-23-29=»
=215 441.)
3. Найти все множители числа N из задачи
2.
4. Применить «факторизацию по разности
квадратов» к разложению числа 131 289
иа простые множители.
5. Выполнить «факторизацию по разности
квадратов» числа 500 207. (Применить
«уловку» предварительного умножения на 3).
6. Применяя «факторизацию по разности
квадратов» непосредственно к числу Лг~
= 20 099, убедитесь в том, что 20 099= 199 • 101.
Сколько потребовалось шагов? Зиая результат
разложения N, объясните, почему самым
лучшим множителем, ускоряющим процесс
разложения N, оказалось бы число 8?
Сколько потребуется шагов для разложения
числа 8.V?
13
Б. А. Кордемский
#физика #квант
