6

与えられた数n(n = p ^ a * q ^ b、いくつかの素数p、qおよびいくつかの整数a、b)および与えられた数φ(n)(http://en.wikipedia。 org / wiki / Euler%27s_totient_function)p、q、aおよびbを検索します。

キャッチは、nとφ(n)が約200桁であるため、アルゴリズムは非常に高速である必要があるということです。非常に難しい問題のようで、φ(n)の使い方がまったくわかりません。

これにアプローチする方法は?

4

2 に答える 2

6

の場合n = p^a * q^b、トーティエントはφ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1)です。一般性を失うことなく、p < q

したがってgcd(n,φ(n)) = p^(a-1) * q^(b-1)、分割しpない場合と分割する場合。q-1gcd(n,φ(n)) = p^a * q^(b-1)pq-1

最初のケースでは、とがn/gcd(n,φ(n)) = p*qあります。φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q)したがって、とがx = p*q = n/gcd(n,φ(n))ありy = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n))ます。p次に、 andを見つけるのqは簡単です:y^2 - 4*x = (q-p)^2、so q = (y + sqrt(y^2 - 4*x))/2、およびp = y-qa次に、指数を見つけることbは簡単です。

2番目のケースでは、n/gcd(n,φ(n)) = q。次に、指数を簡単に見つけることができb、除算が余りを残すまで除算してq、を取得しp^aます。で割るφ(n)と、(q-1)*q^(b-1)が得られますz = (p-1)*p^(a-1)。次にp^a - z = p^(a-1)p = p^a/(p^a-z)。指数aを見つけることも簡単です。

したがって、どちらのケースを使用するかを決定する必要があります。n/gcd(n,φ(n))が素数である場合に限り、ケース2があります。

そのためには、まともな素数性テストが必要です。または、最初にケース1があると想定し、それがうまくいかない場合は、ケース2があると結論付けることができます。

于 2012-04-27T17:01:47.870 に答える
0

n /(n-φ(n))が何であるかを考えてみてください。

ファローアップ:

n /(n-φ(n))=pq。nをpqで割り続けます。

于 2012-04-27T16:30:37.733 に答える