Apakah algoritma uji primalitas Rabin-Miller menggunakan modular squaring benar?

Saya baru-baru ini menemukan potongan kode untuk algoritma Rabin-Miller, seperti yang dijelaskan di sini:

from random import randint

    def _bits_of_n(n):
        """ Return the list of the bits in the binary
            representation of n, from LSB to MSB
        """
        bits = []

        while n:
            bits.append(n % 2)
            n /= 2

        return bits

    def _MR_composite_witness(a, n):
        """ Witness functions for the Miller-Rabin
            test. If 'a' can be used to prove that
            'n' is composite, return True. If False
            is returned, there's high (though < 1)
            probability that 'n' is prime.
        """
        rem = 1

        # Computes a^(n-1) mod n, using modular
        # exponentation by repeative squaring.
        #
        for b in reversed(_bits_of_n(n - 1)):
            x = rem
            rem = (rem * rem) % n

            if rem == 1 and x != 1 and x != n - 1:
                return True

            if b == 1:
                rem = (rem * a) % n

        if rem != 1:
            return True
        return False

    def isprime_MR(n, trials=6):
        """ Determine whether n is prime using the
            probabilistic Miller-Rabin test. Follows
            the procedure described in section 33.8
            in CLR's Introduction to Algorithms

            trials:
                The amount of trials of the test.
                A larger amount of trials increases
                the chances of a correct answer.
                6 is safe enough for all practical
                purposes.
        """
        if n < 2:
            return False

        for ntrial in xrange(trials):
            if _MR_composite_witness(randint(1, n - 1), n):
                return False

        return True

Saya tahu bahwa tes RM harus mengambil N, menguraikan N-1 = t*(2^s) dan kemudian mencoba menemukan sedemikian rupa sehingga a^t != 1 dan a^((2^r)t) != -1 untuk semua 0 ‹= r ‹ s

Namun algoritma ini melakukan sesuatu yang berbeda. Ini mengingatkan saya sebagian pada algoritma Fermats, di mana kita menguji a^(n-1) mod n == 1, karena menggunakan kuadrat dan mengalikan untuk mendapatkan a^(n-1) tetapi memeriksa apakah ada hasil antara yang kongruen 1 mod n.

Saya tidak mengerti bagaimana kedua hal ini setara, bisakah Anda menjelaskan mengapa (x^2==1 dan x != 1 dan x!=n-1) berfungsi sebagai kondisi yang cukup?

Terima kasih!


python algorithm algebra primes
person michnovka    schedule 30.05.2015    source sumber

Jawaban (1)


arrow_upward
3
arrow_downward

Jika kita menemukan hasil antara yang kongruen dengan 1 (modulo n) dan hasil sebelumnya x tidak kongruen dengan 1 atau -1 (yaitu n-1) modulo n, maka bilangan x ini adalah akar kuadrat nontrivial dari 1 modulo n (yaitu bilangan x sedemikian rupa sehingga x ≠ -1, 1 mod n tetapi x^2 = 1 mod n). Artinya n adalah komposit.

Bukti: Misalkan demi kontradiksi bahwa x^2 kongruen dengan 1 modulo p, x bukan 1 atau -1 modulo p, dan p adalah bilangan prima. Ini sama dengan mengatakan bahwa p membagi x^2 - 1 = (x-1)(x+1). Oleh karena itu, karena p bilangan prima, p membagi x-1 atau x+1, yang berarti x kongruen dengan 1 atau -1 modulo p.

Inilah sebabnya mengapa (x^2==1 dan x != 1 dan x!=n-1) merupakan kondisi yang cukup - ini langsung menyiratkan bahwa n adalah komposit. Dengan demikian kita dapat menghentikan algoritma lebih awal untuk menghemat waktu komputasi.

Seperti yang dinyatakan oleh tautan Anda (dengan salah ketik), penjelasan yang bagus tentang hal ini ditemukan di bagian 31.8 Pengantar Algoritma oleh Cormen, Leiserson, Rivest, dan Stein, dan beberapa jawaban saya diadaptasi dari buku itu.

person user2258552    schedule 30.05.2015