Tonelli-Shanks Modüler Karekök Hesaplayıcı

Bu hesaplama hakkında

Tonelli-Shanks algoritması, hesaplamalı sayılar teorisinin temel işlemlerinden biri olan, verilen bir n sayısı ve tek asal modül p için r² ≡ n (mod p) koşulunu sağlayan bir modüler karekök — yani r değerini — bulur. Ana algoritmayı çalıştırmadan önce Euler kriterini denetler: n’nin mod p’de bir karesel kalan olması (yani bir karekökün var olması), tam olarak n^((p−1)/2) ≡ 1 (mod p) olduğunda gerçekleşir. p ≡ 3 (mod 4) olduğunda karekök için doğrudan kapalı formda bir kısayol vardır, ancak p ≡ 1 (mod 4) olan daha zor genel durum için, p−1’den 2 çarpanlarını ayıklamak amacıyla karesel kalan olmayan bir sayıya karşı tekrarlanan karesini alma işlemi kullanan Tonelli-Shanks gerekir.

Bu işlem, pratik kriptografinin temelini oluşturur — özellikle ECDSA ve Bitcoin’in kullandığı sıkıştırılmış açık anahtar biçimlerinde, x-koordinatından bir eliptik eğri noktasının çözülmesinde; burada y-koordinatının, eğri denkleminden türetilen bir değerin modüler karekökü olarak geri kazanılması gerekir. n ve bir asal p girin, bu hesaplayıcı Euler kriterini denetler ve bir kök varsa onu bulmak için Tonelli-Shanks’i çalıştırır.