Стандартный метод факторизации

Если от нас требуется факторизовать большое число N, необходимо воспользоваться следующим: если число N не простое, то оно должно иметь хотя бы два делителя, меньший из которых не может превосходить квадратного корня из N. Это означает, что для случая N=9167 нужно проверять на делимость только простые числа, меньшие 9167 (эта величина примерно равна 96). Наибольшее простое число, не превосходящее 96, равно 89, поэтому в нашем случае мы получили бы ответ при самой последней проверке, выполнив к этому моменту более двадцати операций деления. Если бы мы выполняли эти проверки для N=9161, то не нашли бы ни одного делителя, поскольку число 9161 - простое.

С увеличением N растет и число тестов, которые необходимо провести. Так, если N=988027, то оно либо простое, либо делится на число, не превосходящее 988027, что чуть-чуть меньше 994. Теперь следует разделить 988027 на каждое простое число, меньшее 994. Если мы обнаружим простое число, которое в точности (то есть без остатка) делит 988027, то задача решена. Если такого числа нет, то число 988027 является простым. На самом деле

988027=991997,

и поскольку 991 и 997 - это простые числа, то факторизация завершена. На это пришлось бы потратить массу усилий, поскольку существует более 160 простых чисел, меньших 991, и их придется все перепробовать, прежде чем будет найден ответ. Эта задача отнимет кучу времени и будет весьма утомительна, даже если использовать калькулятор. Человек, знакомый с программированием и имеющий компьютер, разумеется, мог бы поручить ему все вычисления. Независимо от того, каким образом это будет сделано, при увеличении N с 9167 до 988027 (то есть примерно в 108 раз) число операций деления, которые нам (или компьютеру) необходимо выполнить, возрастет с 20 до более чем 160. Заметим, что при росте числа N более чем в 100 раз (так что число N возросло более чем в 10 раз) число тестов вырастает только в 8 раз. Объяснение этого факта можно найти в M21.

Такой метод поиска простых делителей заданного числа, когда это число делят поочередно на все простые числа, меньшие его квадратного корня, по существу принадлежит Эратосфену и является стандартным методом как при факторизации числа (если он срабатывает), так и при доказательстве его простоты (если ничего не найдено). Это не единственный метод, которым можно воспользоваться. Иногда можно найти быстрый путь: например, можно заметить, что

9167=9216-49=96²-7²=(96-7)(96+7)=89103,

или, что еще лучше,

988027=988036-9=994²-3²=(994-3)(994+3)=991997,

но, вообще говоря, так везет далеко не всегда. Иногда существуют специальные приемы, позволяющие уменьшить число вариантов - например, если число, которое мы пытаемся факторизовать, является числом специального вида, таким как

2^p-1

где p - простое. Однако для чисел того типа, что применяется в системе RSA, такие специальные методики оказываются неприменимы.

Стойкость описанной далее системы шифрования RSA основана на следующем факте: факторизация большого числа требует значительных затрат времени даже в том случае, когда известно, что оно является произведением двух больших простых чисел. Что касается процесса зашифрования по системе RSA, то в его основе лежит красивая и мощная теорема, сформулированная в начале семнадцатого столетия без доказательства французским математиком Пьером Ферма (Pierre Fermat). Её часто называют "Малой теоремой Ферма", и её не следует путать с пресловутой "Великой теоремой Ферма" - её он также сформулировал без доказательства, а доказана она была только в 1993 году (см. [13.2]). Возможно, у Ферма и было доказательство его "Малой теоремы", однако представляется крайне маловероятным, чтобы он сумел доказать свою "Великую теорему". Швейцарский математик Леонард Эйлер^*) в 1760 году опубликовал доказательство Малой теоремы Ферма и получил ее обобщение, известное под именем теоремы Ферма-Эйлера. Именно эта теорема используется в алгоритме зашифрования/расшифрования RSA.

В качестве первого шага поучительно будет рассмотреть несколько примеров, которые иллюстрируют теорему, носящую название