𝜙𝜙p * qを蚈算する効率的な方法ここで、pずqは玠数です

Aug 17 2020

したしょう $p$ そしお $q$ 玠数であり、 $\phi$オむラヌのトヌティ゚ント関数。蚈算の効率的な方法はありたすか$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$、それは単にファクタリングに基づくものではありたせん $p-1$ そしお $q-1$

明らかに、 $p$ そしお $q$ 2に等しくない、 $p-1$ そしお $q-1$ であり、その結果、それらの玠因数分解はの玠因数分解ずは完党に異なりたす $p$ そしお $q$。したがっお、そのようなショヌトカットは存圚しないず思いたす。

私は䜕かを芋萜ずしおいたすか

回答

2 D.W. Aug 18 2020 at 00:35

いいえ、効率的ではなく、䞀般的ではありたせん。仮定したす$p=2p'+1$ そしお $q=2q'+1$ どこ $p',q'$玠数です。次に因数分解$pq$難しいず思われたす。実際、これらの玠数は安党な玠数ずしお知られおおり、2぀の安党な玠数の積を因数分解するのは難しいず考えられおいたす。しかし、

$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$

あなたが蚈算できれば $\varphi(\varphi(pq))$ から $pq$ 効率的に $p,q$ この圢匏の堎合、因数分解できたす $pq$ 効率的に $p,q$この圢の。削枛は次のように機胜したす。二次関数を考えたす$f$ によっお䞎えられた

$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$

の係数を蚈算できたす $f$、 なので

$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$

したがっお、2次方皋匏を䜿甚しお、の根を解くこずができたす。 $f$ 回埩したす $p',q'$。これからの因数分解$pq$ 回埩するこずができたす。

だから、いや、あなたは䜕も芋萜ずしおいたせん。蚈算する効率的な方法はおそらくありたせん$\varphi(\varphi(pq))$ 任意の数の堎合 $pq$ ファクタリングが簡単でない限り。