HesapHanem

Euler Totient Hesaplama

Herhangi bir pozitif tam sayının Euler totientini bulun.

Nasıl hesaplanır?

Euler'in φ(n) fonksiyonu, 1 ile n arasında n ile 1'den başka ortak böleni olmayan tam sayıların adedidir. Araç her sayıyı tek tek denemez. n'yi asal çarpanlarına ayırır ve n'yi bölen her farklı asal p için φ(n) = n × ∏(1 − 1/p) çarpım formülünü yalnızca tam sayı adımlarıyla uygular. Asal bir p için φ(p) = p − 1'dir. Girdi tam sayıya indirgenir ve 1 ile 1.000.000.000 arasında olmalıdır. İki sonuç alanı da aynı sayıyı gösterir.

Örnek hesaplama

n = 36 alalım. Asal çarpanları 2 ve 3'tür, çünkü 36 = 2² × 3². 36 ile başlanır. Asal 2 için 36 / 2 = 18 çıkarılır, 18 kalır. Asal 3 için 18 / 3 = 6 çıkarılır, 12 kalır. Yani φ(36) = 12: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 ve 35 sayılarının 36 ile ortak böleni yoktur.

Bu örneği dene →

Sık yapılan hatalar

  • Her asal çarpanı kuvvetiyle birlikte saymak. 36 = 2 × 2 × 3 × 3 olsa da formülde yalnızca farklı asallar 2 ve 3 kullanılır.
  • Her n için φ(n) = n − 1 sanmak. Bu yalnızca asallar için geçerlidir; 36 için sonuç 35 değil 12'dir.
  • Ortak çarpanı olan sayıların φ değerlerini çarpmak. φ(a × b) = φ(a) × φ(b) yalnızca a ile b aralarında asalsa geçerlidir.
  • Ondalıklı ya da bir milyardan büyük sayı girmek. Ondalık kısım atılır, daha büyük değerde sonuç çıkmaz.

Bu hesaplama hakkında

Bu hesaplayıcı, 1'den n'e kadar n ile aralarında asal olan (n ile 1 dışında ortak böleni olmayan) pozitif tam sayıların sayısı olan Euler totientini φ(n) bulur. Değer, n'in asal çarpanlarına ayrılmasından φ(n) = n·∏(1 − 1/p) çarpım formülüyle hesaplanır (p, n'in her farklı asal çarpanı üzerinden); bir asal sayı p için ise φ(p) = p − 1'dir.

Totient fonksiyonu sayılar teorisinin merkezinde yer alır ve RSA açık anahtarlı şifreleme sisteminin matematiksel temelini oluşturur; burada iki büyük gizli asal sayıdan hesaplanan φ(n), özel anahtarı açık anahtardan türetmek için kullanılır. Ayrıca modüler aritmetikte sıkça kullanılan Fermat'nın küçük teoreminin genellemesi olan Euler teoremini de yönetir.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    İki farklı asal sayının çarpımı olan bir modül için, n = p × q ise totient (p − 1)(q − 1) değerine eşit olmalıdır; elle kontrol için kullanışlıdır: 77 = 7 × 11 için 6 × 10 = 60 çıkmalıdır. Bu aracın üst sınırının bir milyar olduğunu, gerçek RSA modüllerinin boyutunun çok altında kaldığını unutmayın; yani öğrenme ve ödev için uygundur, anahtar üretimi için değil. Modüler aritmetik sorusu mu çözüyorsunuz? Takıldığınız n değerini ve beklediğiniz sonucu paylaşın.

Popüler hesaplayıcılar

Kredi Hesaplama

Aylık taksit, toplam faiz ve ödeme planını hesaplayın.

Yüzde Hesaplama

Yüzde değişim, indirim ve oran hesaplamaları.

İndirim Hesaplama

İndirimli fiyatı, kazancı ve indirim tutarını hesaplayın.

Vücut Kitle Endeksi (VKİ)

Boy ve kiloya göre vücut kitle endeksini hesaplayın.

Yaş Hesaplama

Doğum tarihinden bugüne tam yıl, ay ve gün cinsinden yaşınızı hesaplayın.

Bileşik Faiz Hesaplama

Ana para, faiz oranı ve süreye göre bileşik faizle nihai tutarı hesaplayın.

Tüm Hesaplayıcılar