Yalan RSA
Roman, Serge və Andrew məşhur RSA şifrələmə alqoritmini təkmilləşdirmək qərarına gəliblər. Onlar düşünürlər ki, RSA-da istifadə olunan modul n-in iki fərqli sadə ədədin hasilatı olması məhdudiyyəti artıqdır. Bunun əvəzinə, onlar n-i iki fərqli sadə ədədin k-ci dərəcələrinin hasilatı kimi istifadə etməyi planlaşdırırlar: n = p^kq^k.
Lakin, Nick qeyd etdi ki, digər bütün riyazi problemlərdən əlavə, bu sxem daha asan sındırıla bilər. Yəni, n-in iki fərqli sadə ədədin hasilatı olduğu halda onu faktorlaşdırmaq çətindir, çünki onun yalnız bir qeyri-trivial faktorlaşdırması var. Digər tərəfdən, n = p^kq^k halında daha çox fərqli qeyri-trivial faktorlaşdırmalar ola bilər. Məsələn, 100 = 2^2·5^2 səkkiz qeyri-trivial faktorlaşdırmaya malikdir: 100 = 2·50, 100 = 2·2·25, 100 = 2·2·5·5, 100 = 2·5·10, 100 = 4·25, 100 = 4·5·5, 100 = 5·20 və 100 = 10·10.
İndi Roman, Serge və Andrew maraqlanırlar — verilmiş n = p^kq^k üçün n-in neçə fərqli qeyri-trivial faktorlaşdırması var?
Giriş verilənləri
Giriş faylı bir tam ədəd n (6 ≤ n ≤ 10^18, n = p^kq^k olduğu və fərqli sadə ədədlər p və q və tam ədəd k > 0 olduğu təmin edilir) ehtiva edir.
Çıxış verilənləri
Bir tam ədəd çıxış edin — n-in fərqli qeyri-trivial faktorlaşdırmalarının sayı.