Cara yang efisien untuk menghitung đťś™ (đťś™ (p * q)) di mana p dan q adalah bilangan prima

Aug 17 2020

Membiarkan $p$ dan $q$ menjadi bilangan prima dan $\phi$Fungsi total Euler. Apakah ada cara komputasi yang efisien$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, itu tidak hanya berdasarkan anjak piutang $p-1$ dan $q-1$?

Jelas, jika $p$ dan $q$ tidak sama dengan dua, $p-1$ dan $q-1$ adalah genap dan akibatnya faktorisasi prima mereka sama sekali berbeda dari faktorisasi prima $p$ dan $q$. Oleh karena itu saya berasumsi bahwa tidak ada jalan pintas seperti itu.

Apakah saya mengabaikan sesuatu?

Jawaban

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

Tidak, tidak efisien, tidak secara umum. Seharusnya$p=2p'+1$ dan $q=2q'+1$ dimana $p',q'$adalah bilangan prima. Kemudian anjak piutang$pq$diyakini sulit. (Memang, bilangan prima ini dikenal sebagai bilangan prima aman , dan memfaktorkan produk dari dua bilangan prima aman diyakini sulit.) Namun demikian yang kita miliki

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

Jika Anda bisa menghitung $\varphi(\varphi(pq))$ dari $pq$ efisien untuk $p,q$ dari bentuk ini, maka Anda dapat memfaktorkan $pq$ efisien untuk $p,q$dari formulir ini. Pengurangan bekerja sebagai berikut. Pertimbangkan fungsi kuadrat$f$ diberikan oleh

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

Kita dapat menghitung koefisien dari $f$, sebagai

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

sehingga Anda dapat menggunakan rumus kuadrat untuk mencari akar dari $f$ dan pulih $p',q'$. Dari sini faktorisasi$pq$ bisa dipulihkan.

Jadi, tidak, Anda tidak mengabaikan apa pun. Sepertinya tidak ada cara yang efisien untuk menghitung$\varphi(\varphi(pq))$ untuk nomor acak $pq$ (kecuali memfaktorkan mudah).