Самая сложная задача в мире. Ферма. Великая теорема Ферма

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

РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ МЕТОДОМ ФЕРМА

Ферма изобрел метод разложения на множители исходя из того, что нечетное неквадратное число нельзя записать как 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 верен.