Эйлерс Фи Огромных чисел
Его легко вычислить с помощью небольших чисел, есть даже много онлайн-сайтов, которые предлагают такие функции. Но что, когда цифры действительно огромны, я имею в виду 2 ^ 128? Как я могу вычислить функцию Фи Эйлера такого большого числа? Могу ли я использовать свой настольный компьютер для этого?
Решение
Если вы знаете основные факторы, тогда да. Но в целом вы не можете сделать это эффективно, по крайней мере, не так, как кто-либо знает. Если бы мы могли вычислить общую функцию в целом, то мы могли бы получить ее для n = pq, где p и q — простые числа, которые были бы (p-1) (q-1). Поэтому n — phi (n) = p + q — 1, и тогда мы знаем p + q = c. Тогда (p + q) ^ 2 = c ^ 2, поэтому p ^ 2 + q ^ 2 = c ^ 2 — 2n. Но тогда (p-q) ^ 2 = p ^ 2 + q ^ 2 — 2pq = c ^ 2 — 4n. Итак, мы знаем p + q и p-q, из которых мы можем получить p и q.
Это сломалось бы RSA шифрование
Другие решения
Других решений пока нет …