Разложение на множители методом Ферма

Ферма изобрел метод разложения на множители исходя из того, что нечетное неквадратное число нельзя записать как N = х² ‑ y², где  

x = (n₁+n₂)/2 и e = (n₁‑n₂)/2.  

Можно легко доказать, что N = n₁n₂. Если N – простое число, то n₁ = N, а n₂ = 1. В противном случае n₁ и n₂ – собственные делители N. Поскольку n₁ и n₂ нечетные, так как N нечетное, то х и у – целые числа. Отсюда следует, что решение предыдущих уравнений для х и у предполагает возможность разложения N на множители. Для решения этого уравнения прибегают к проверкам, начиная с целого числа m, которое выполняет некое свойство, и, если оно не является решением, продолжают с помощью другого числа m', которое получается на основе m, и продолжают таким образом, пока не получают собственный делитель или не доходят до самого числа N. Разложение на множители методом Ферма может стать очень эффективным в некоторых случаях, поскольку числа т должны быть квадратными, и очень часто бывает легко определить, является ли число квадратным, просто посмотрев на него. Действительно, идеальные квадраты могут заканчиваться только на 0,1,4,5,9,16,36,56, 76 и 96, что исключает 90% окончаний. Красота данного метода в том, что в нем не требуется знания всех простых чисел до определенного числа и что если N – составное число и имеет множитель, близкий к √n, то это разложение на множители быстро его определяет.  

Как бы то ни было, после всеобщего внедрения RSA и тесты простоты числа (первый шаг алгоритма – найти два огромных простых числа), и алгоритмы разложения на простые множители (которые в худшем случае могли бы разрушить надежность RSA) получили огромную практическую важность.

Итак, Ферма был озабочен проблемой нахождения простого числа. В качестве элементарной проверки, является ли данное число простым, можно задаться вопросом, выполняет ли заданное число требования малой теоремы Ферма; однако заметьте, что здесь речь идет, скорее, про обратную теорему. Следовательно, нет никакой гарантии того, что число окажется простым. Действительно, известно, что так называемые числа Кармайкла не выполняют обратную теорему. Но даже тогда этот тест является настолько простым и быстрым, что он используется при исполнении алгоритма RSA, чтобы быстро отбросить составные числа. Ведь на самом деле тест простоты, основанный на малой теореме Ферма, заключается в том, чтобы выяснить, является ли число составным. В довершение всего малая теорема Ферма также используется, чтобы доказать, что алгоритм RSA верен.

Другие тесты на простоту делятся на вероятностные и детерминированные. К первым относится тест Миллера – Рабина, который также основывается на малой теореме Ферма, или тест Соловея – Штрассена, основанный на теореме Эйлера, обобщающей малую теорему. Последний тест никогда не утверждает, что число простое, если это не так, но он менее успешен с составными числами. Действительно, существуют тесты, более эффективные в том, чтобы показать, что число составное, а другие больше подходят для доказательства того, что оно простое.

Детерминированное продолжение теста Миллера – Рабина основывается на недоказанном результате: расширенной гипотезе Римана. Очевидно, что его эффективность зависит от того, истинна ли эта гипотеза. Однако в 2002 году впервые было объявлено о тесте под названием AKS, который является универсальным (работает для любого числа), детерминированным, безусловным (не зависит от недоказанных результатов) и эффективным (с полиномиальной сложностью вычислений). Алгоритм AKS также основан на обобщении малой теоремы Ферма.

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

Существует много других результатов, зависящих от малой теоремы. Один из самых известных – то, что мы все замечали: количество знаков после запятой в рациональном числе повторяется периодически, если в данном рациональном числе, выраженном несократимой дробью, знаменатель – простое число р, отличное от 2 и 5 (которые являются простыми множителями 10). Именно поэтому 1/3 ‑ 0,33333..., а 1/7 ‑ ‑ 0,142857142857..., но 1/5 ‑ 0,2, без периодического повторения. Предыдущие рассуждения служат для того, чтобы понять: малая теорема – один из самых важных результатов в теории чисел.

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

Замечание немецкого математика Курта Гензеля в своей книге "Теория чисел" (Zablentheorie, 1913).

Конечно же, Ферма, верный своей традиции, не оставил ни одного доказательства. Теорема была доказана Эйлером, который не знал, что Лейбниц несколькими годами ранее уже доказал ее, хотя результат был опубликован только в XIX веке.

В доказательстве Лейбница используются математические методы, известные Ферма, поэтому возможно, что доказательство Ферма, если оно существовало, было сделано подобным способом.

В любом случае, Ферма явно не догадывался о ее последующем применении. Для него теорема была инструментом для теста простоты некоторых чисел, таких как 2ⁿ ‑ 1. Она была одним из его сокращенных путей, используемых с целью избежать решета Эратосфена. Например, благодаря своей малой теореме Ферма смог подступиться к числам вида аⁿ ‑ 1 при а > 2, которые никогда не являются простыми, сведя кандидатов в их простые делители к меньшему множеству. Как легко увидеть, эти числа – обобщение чисел Мерсенна. Кроме того, малая теорема позволила Ферма таким же образом подойти к числам аⁿ + 1, которые, как он утверждал, являются простыми, если a четное, а n имеет вид 2^m. Именно в ходе этого исследования математик открыл так называемые простые числа Ферма, которые соответствуют этим двум условиям и еще одному – тому, что число m вида 2^2p +1 простое, если р простое.

Но в данном случае интуиция подвела Ферма. Эйлер нашел контрпример при p ‑ 5. Итоговое число делится на 641. Ферма осознавал, что не может доказать этот результат, и говорил о своем разочаровании в течение многих лет; в 1659 году он изложил доказательство своему другу Каркави, но с учетом контрпримера Эйлера, оно, даже если и существовало, явно было ошибочным. В любом случае ясно, что малая теорема позволяла Ферма исключить из своих вычислений любое множество простых чисел – кандидатов в делители чисел некоего вида, что облегчало тесты простоты указанных чисел. Однако, к своему большому разочарованию, он никогда не добился того, к чему стремился, – вывести теорему, позволяющую избавиться от всех простых чисел, которые можно исключить для указанных типов чисел.

Сегодня не существует по‑настоящему эффективного и надежного метода нахождения простых чисел произвольного размера; нет формулы вроде той, что нашел Евклид для четных совершенных чисел. В большинстве методов нахождения простых чисел требуется знать все простые числа до некоего предварительного числа либо знать, являются ли числа, соседние с кандидатом на простое число, разложимыми на множители. Следовательно, тесты простоты крайне важны: сначала ищут кандидата на простое число, а потом проверяют, является ли оно таковым.

Казалось, что к концу 1640 года Ферма потерял интерес к суммам собственных делителей. Его следующие исследования по теории чисел напрямую связаны с Великой теоремой.