İlkel Kök Hesaplama

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, 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.

Bir n modülü girin, bu hesaplayıcı varsa en küçük ilkel kökünü bulsun; o n için ilkel kök yoksa bunu da belirtsin.