与えられた数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)の使い方がまったくわかりません。
これにアプローチする方法は?
与えられた数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)の使い方がまったくわかりません。
これにアプローチする方法は?
の場合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-1
gcd(n,φ(n)) = p^a * q^(b-1)
p
q-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-q
。a
次に、指数を見つけること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があると結論付けることができます。
n /(n-φ(n))が何であるかを考えてみてください。
ファローアップ:
n /(n-φ(n))=pq。nをpqで割り続けます。