Carmichael Fonksiyonu Hesaplama

Bu hesaplama hakkında

Carmichael fonksiyonu λ(n) — bazen indirgenmiş totient olarak da adlandırılır — n'ye aralarında asal olan her a tam sayısı için a^m ≡ 1 (mod n) eşitliğini sağlayan en küçük pozitif m tam sayısını verir. n'den küçük ve n'ye aralarında asal olan sayıları sayan Euler totienti φ(n) ile benzer bir rol oynar, ancak λ(n) genellikle daha küçüktür; çünkü işe yarayan herhangi bir üs yerine, tüm tabanlar için geçerli gerçek en küçük evrensel üssü bulur. Aslında λ(n) her zaman φ(n)'yi böler.

Bu fonksiyon modüler aritmetik ve kriptografide önemlidir: RSA anahtar üretiminde özel üssü türetirken φ(n) yerine λ(n) kullanılabilir; λ(n) genellikle φ(n)'den küçük olduğu için aynı modül için daha küçük geçerli bir üs elde edilebilir — bu da RSA anahtar üretim formülünün Carmichael tabanlı çeşidinin temelidir. Sayı teorisyenleri, n modülüne göre tam sayıların çarpımsal grubunun yapısını ve devirli alt grup ayrışımını incelerken de λ(n)'yi kullanır.

Pozitif bir tam sayı n girin; hesaplayıcı hem λ(n) hem de φ(n) değerini vererek indirgenmiş totienti aynı sayının standart Euler totientiyle karşılaştırmanızı sağlar.