巨大な数のオイラーズフィー

Question

小さな数のオイラーズファイを計算するのは簡単で、そのような機能を提供する多くのオンラインサイトがあります。しかし、数字が本当に巨大なときは、2^128のようになりますか？どのようにしてこのような高い数値のオイラーピ関数を計算できますか？デスクトップPCを使用することはできますか？

Answer 1

あなたが素因数を知っているなら、はい。しかし、一般的には、少なくとも誰もが知っている方法では効率的に行うことはできません。 totient関数を一般的に計算することができれば、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を得ることができます。

これは、「C++ビッグナンバーライブラリ」と「C++多倍長ライブラリ」をインターネットで検索RSA encryption