ConverterHub

İlkel Kök Hesaplama

En küçük ilkel kökü bulmak için bir n modülü girin.

Sonuç

5
22
10

Nasıl hesaplanır?

2 ile 100.000 arasındaki tam sayı bir n modülü için araç Euler'in totient değerini φ(n), yani n'den küçük ve n ile ortak böleni olmayan sayıların adedini hesaplar. Sonra n ile aralarında asal olan g = 1, 2, 3, … değerlerini dener; her biri için değer 1'e dönene kadar mod n çarpmayı tekrarlayıp adımları sayar. Adım sayısı φ(n)'e eşit olan ilk g, en küçük ilkel köktür. Ayrıca gerekli mertebe olarak φ(n)'i ve ilkel kök sayısını verir; bu sayı φ(φ(n))'dir. Hiçbir g işe yaramazsa, örneğin n = 8 veya n = 100 için, sonuç çıkmaz: ilkel kök yalnızca n = 2, 4, p^k ve 2p^k için vardır (p tek asal). Tam sayı olmayan değerler, 2'den küçük n ve 100.000'in üstündeki n reddedilir.

Örnek hesaplama

n = 23 olsun; bu bir asaldır, dolayısıyla φ(23) = 22 ve ilkel kökün mertebesi 22 olmalıdır. 1 denenince mertebe 1 çıkar. 2 denenince mertebe 11 çıkar; çünkü 2'nin 11. kuvveti 2048'dir ve bu mod 23'te 1'dir. 3 ve 4'ün de mertebesi 11'dir. 5 denenince mertebe 22 olur: kuvvetleri 1'e dönmeden önce sıfırdan farklı 22 kalanın hepsini dolaşır. Yani en küçük ilkel kök 5'tir. İlkel kök sayısı φ(22) = 10'dur.

Bu örneği dene →

Sık yapılan hatalar

  • İlkel kökü, birimin ilkel kökü ya da karekökle karıştırmak. Burada g'nin kuvvetleri, n ile aralarında asal her sayıyı üretmelidir.
  • Her modülün bir ilkel kökü olduğunu sanmak. 8, 12 ve 100 gibi modüllerde yoktur ve araç yanlış cevap vermek yerine sonuç göstermez.
  • Mertebesi büyük çıkan ilk g'de durmak. İlkel kökün mertebesi tam olarak φ(n) olmalıdır; n = 23 için 2, 3 ve 4 mertebe 11'de kalır.
  • 100.000'den büyük bir sayı ya da ondalık girmek. Yalnızca 2 ile 100.000 arasındaki tam modüller kabul edilir.
  • En büyük ya da rastgele bir ilkel kök beklemek. Araç yalnızca en küçüğünü verir; diğerleri, üssü φ(n) ile aralarında asal olan kuvvetlerdir.

Bu hesaplama hakkında

Bir g sayısı, kuvvetleri — g¹, g², g³ ve devamı — n'ye göre aralarında asal olan her sayıyı, tekrara düşmeden önce dolaşıyorsa, yani g^k ≡ 1 (mod n) eşitliğini sağlayan en küçük k üssü tam olarak Euler'in totient fonksiyonu φ(n)'ye eşitse, n modülüne göre ilkel kök olarak adlandırılır. Başka bir deyişle, tek bir ilkel kök, n modülüne göre çarpımsal grubun tamamını kendi başına üretir. İlkel kökler her modül için var olmaz: klasik sayılar teorisi (Gauss'a kadar uzanan) bunların yalnızca n değeri 1 (önemsiz durum), 2, 4, tek bir asalın kuvveti veya tek bir asalın kuvvetinin iki katı olduğunda var olduğunu gösterir.

İlkel kökler kriptografide sadece bir merak konusu değil, işlevsel bir araçtır: Diffie-Hellman anahtar değişimi ve ElGamal şifreleme sistemi, bir ilkel kök tarafından üretilen bir grup içindeki ayrık logaritma probleminin zorluğuna dayanır; hızlı ve kesin polinom çarpımında kullanılan sayı-teorik dönüşümler (bazı modern kriptografi ve hata düzeltme şemalarıyla ilgili) de uygun bir modülün ilkel köklerini bulmaya dayanır.

2 ile 100.000 arasında bir tam sayı n modülü girin; bu hesaplayıcı en küçük ilkel kökünü, φ(n) değerini ve ilkel kök sayısını bulsun. O n için ilkel kök yoksa sonuç vermez.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar

  • İlk yorumu siz yazı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