Самая сложная задача в мире. Ферма. Великая теорема Ферма
Шрифт:
В один из тех редких случаев, когда Ферма показал некоторые из своих достижений, в ответе Френиклю в 1640 году он утверждал, что числа Мерсенна М = 2p– 1 являются простыми, когда показатель степени — простое число. Также если n простое число, то n — делитель 2n-1– 1, и, наконец, если п простое число, то единственно возможные делители 2n– 1 имеют вид k(2n) + 1. Но, как обычно, Ферма не предоставил никакого доказательства.
Первый результат очень важен, поскольку он позволяет отбросить большое количество чисел Мерсенна в качестве кандидатов в простые числа. Второй и третий — сокращенные пути. Второй позволяет найти по крайней мере один делитель некоего числа Мерсенна (который может быть самим числом, что доказывает 23-1– 1 = 3, являющееся делителем 3), а третий позволяет ограничить вид множителей
Прямое доказательство теоремы идет от гипотезы и шаг за шагом приближается к выводу. Некоторые из данных шагов можно инвертировать, а другие нет. В целом шаг, содержащий импликацию, нельзя инвертировать. Рассмотрим это на бытовом примере. Можно сделать вывод, что тротуар мокрый, из того факта, что идет дождь, но мы не можем сделать вывод о том, что идет дождь, из того, что тротуар мокрый. Последнее могло произойти из-за обстоятельств, не связанных с дождем: например, воду пролила проехавшая автоцистерна или тротуар полили из обыкновенного шланга. Если идет дождь, то тротуар мокрый; но необязательно наоборот. Значит, тот факт, что идет дождь, — достаточное условие для того, чтобы тротуар был мокрым, но не необходимое. Такая однонаправленность присутствует, среди прочего, в малой теореме.
Ферма воспользовался третьим результатом, чтобы доказать, что не существует ни одного совершенного числа из 20 или 21 знака. Для начала он установил, что 237– 1 — единственное число Мерсенна, которое может образовать по формуле Евклида совершенное число из 20 или 21 знака (это предполагает знание и принятие за справедливую теорему, обратную теореме Евклида, доказанную Эйлером несколько лет спустя). Затем он доказал, что данное число Мерсенна не является простым, поскольку делится на 223 = 3 · (2 · 37) +1, что как раз имеет вид k(2n) + 1. Действительно, вместо того чтобы вычислять огромное количество простых чисел, которые могли бы быть делителями 37-го числа Мерсенна, Ферма было достаточно постепенно попробовать числа к(2 · 37) + 1 для различных значений к. На третьей попытке он уже нашел ответ.
В письме Френиклю ученый говорил, что начал различать свет чудесных результатов. Но на самом деле он уже видел этот свет. Два последних результата, о которых он сообщал Френиклю, были следствиями намного более общего результата, известного сегодня как "малая теорема Ферма" (чтобы отличать его от Великой теоремы). Парадокс в том, что "малая" теорема Ферма намного более значима для теории чисел, чем "Великая".
В том же 1640 году Ферма ознакомил с малой теоремой Френикля. Малая теорема Ферма применима только к простым числам. В ее современной формулировке в теореме говорится, что при заданных простом числе p и натуральном числе a, если p не является делителем a, то ap-1– 1 делится на p. Сначала не очень ясна значимость данной теоремы, однако она устанавливает основополагающее свойство этих кирпичиков, простых чисел, что влечет за собой очень интересные последствия.
Годфри Харди около 1912 года отмечал, что теория чисел не имеет практического применения. Тем не менее ситуация радикально изменилась, когда в 1977 году был разработан шифровальный алгоритм под названием RSA, который основан на разложении числа на два простых множителя (нахождение решения) и умножении двух множителей для получения числа (сверка решения).
Взломать данный код означает разложить на простые множители огромное число. Это должно быть очень сложно, чтобы алгоритм был успешен. Наоборот, те, кто знают множители, могут легко зашифровать и расшифровать сообщение, поскольку для этого требуется только умножение. Впервые теория чисел получила практическое применение. От данного принципа сегодня зависят все шифрованные операции в интернете, не больше и не меньше. Однако надежность метода, понимаемая как разница во времени между шифровкой и дешифровкой, с одной стороны, и взломом кода, с другой стороны, не могла быть доказана. Вся электронная экономика висит на этом математическом волоске, хотя большинство экспертов считают, что алгоритм надежен.
Ферма изобрел метод разложения
x = (n1+n2)/2 и e = (n1– n2)/2.
Можно легко доказать, что N = n1n2. Если N — простое число, то n1 = N, а n2 = 1. В противном случае n1 и n2 — собственные делители N. Поскольку n1 и n2 нечетные, так как 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 не разлагает число на множители: операции в интернете остаются надежными.