Berdasarkan deskripsi wikipedia tentang Fungsi Totient Euler, saya menulis kode berikut:

from math import gcd

def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount

Ini berfungsi dengan baik untuk angka kecil, tetapi saya ingin menghitung fungsi totient untuk angka seperti n = 5692297035794675412610596123456169

Apakah ada cara yang lebih baik untuk menghitung fungsi Totoent seperti input besar?

1
mariohez 9 Mei 2021, 12:03

1 menjawab

Jawaban Terbaik

Karena ini juga ditandai Kriptografi, ini lebih ke efektivitas kemungkinan algoritma.

Ada cara untuk menghitung Totient Euler sangat cepat jika Anda mengetahui faktor prima dari n. Misalkan pi adalah k faktor prima dari n yang berbeda maka

(n) = (p1 -1) * (p2-1) * ... * (pk-1)

Ada juga formula untuk kekuatan prima. Itu tidak diperlukan di sini karena enkripsi/tanda tangan RSA atau enkripsi Paillier atau tanda tangan Rabin menggunakan n = p*q dengan dua bilangan prima yang berbeda p dan q.

Seperti yang kita lihat, menemukan (n) secara efektif membutuhkan pengetahuan tentang faktorisasi. Terbukti bahwa untuk RSA pengetahuan tentang (n) sama dengan faktorisasi dari n. Segera lihat di sini;

Atau lihat di kertas RSA asli;

Jika kita beralih ke anjak piutang (RSA), rekor saat ini dicapai pada tahun 2020, CADO-NFS telah difaktorkan dan 828-bit n dengan "kira-kira 2700 core-years, menggunakan CPU Intel Xeon Gold 6130 sebagai referensi (2.1GHz)".

Namun, jika Anda perlu menggunakan RSA, Anda harus menggunakan modulus berukuran setidaknya 2048-bit, lihat di keylength.com. Ini aman dari pemfaktoran setidaknya untuk waktu yang wajar dari faktorisasi klasik dan algoritma pemfaktoran kuantum Shor.

Akibatnya, tidak ada algoritme yang efektif untuk menemukan nilai Euler untuk n besar jika Anda tidak mengetahui faktorisasinya.

1
kelalaka 9 Mei 2021, 23:27