วิธีค้นหาผกผันขององค์ประกอบในขนาดใหญ่มาก $\mathbb{Z}_n$ กลุ่ม?

Aug 16 2020

สมมติว่าฉันมีองค์ประกอบ $a\in\mathbb{Z}_n$ ที่ไหน $n$ เป็นตัวเลขหลายพันหลัก (ฐาน 10) และ $\gcd(a,n)=1$. มีวิธีที่มีประสิทธิภาพในการคำนวณในการหาค่าผกผันของ$a$เหรอ? หรือวิธีใดก็ได้ในการหาค่าผกผันของ$a$ สักครั้งในทศวรรษนี้?

แก้ไข 1:ฉันเป็นแฟนของ python ถ้าคุณต้องการตอบด้วยอัลกอริทึมจริง

อัปเดต:อัลกอริธึมแบบยุคลิดที่ขยายจะทำ (Python ด้านล่าง):

def inverse(a, n):
    t    = 0
    newt = 1
    r    = n
    newr = a

    while newr != 0:
        quotient  = r//newr
        (t, newt) = (newt, t - quotient*newt) 
        (r, newr) = (newr, r - quotient*newr)

    if r > 1:
        return "a is not invertible"
    if t < 0:
        t = t + n

    return t

คำตอบ

3 JCAA Aug 16 2020 at 17:39

อัลกอริทึมแบบยุคลิดนั้นรวดเร็วมาก https://en.m.wikipedia.org/wiki/Euclidean_algorithm