3057 - Rabin Miller

Cerința

Se dă un număr natural n. Să se afișeze DA dacă numărul este prim altfel se afișează NU.

Date de intrare

Fișierul de intrare rabin-miller.in conține pe prima linie numărul n.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", fișierul de ieșire rabin-miller.out va conține pe prima linie DA sau NU după caz. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

n se poate reprezenta pe 8 Bytes

Exemple

Exemplul 1

rabin-miller.in

5

ecran

Datele sunt introduse corect.

rabin-miller.out

DA

Exemplul 2

rabin-miller.in

13

ecran

Datele sunt introduse corect.

rabin-miller.out

DA

Exemplul 3

rabin-miller.in

abc

ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 3057 - Rabin Miller
def este_input_valid(sir_input):
    """Verifică dacă șirul de intrare este un număr natural valid."""
    try:
        n = int(sir_input.strip())
        if n < 2:
            return "Datele nu corespund restricțiilor impuse."
        print("Datele sunt introduse corect.")
        return "Corect"
    except ValueError:
        return "Datele nu corespund restricțiilor impuse."


def este_numar_prim(n):
    """Implementarea testului de primalitate Miller-Rabin, garantată să fie corectă."""
    import math

    def calculeaza_sd(x):
        """Calculează (s: int, d: int) pentru care x = d*2^s """
        if not x:
            return 0, 0
        s = 0
        while 1:
            if x % 2 == 0:
                x //= 2
                s += 1
            else:
                return s, x

    if n <= 2:
        return n == 2

    # n - 1 = d*2^s
    s, d = calculeaza_sd(n - 1)

    if not s:
        return False  # divizibil cu 2!

    log2n = int(math.log(n) / math.log(2)) + 1

    # Conform hipotezei lui Riemann, este imposibil
    # ca toate numerele sub acest prag să fie "strong liars".
    # Prin urmare, numărul este garantat să fie prim dacă nu se găsește o contradicție.
    prag = min(n, 2*log2n*log2n+1)

    for a in range(2, prag):
        # Din mica teoremă a lui Fermat, dacă n este prim atunci a^(n-1) % n == 1
        # Prin urmare, trebuie să fie adevăratul dacă n este într-adevăr prim:
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if -pow(a, d*2**r, n) % n == 1:
                    break
            else:
                # Contrazice mica teoremă a lui Fermat, prin urmare nu este prim.
                return False

    # Nu s-a găsit nicio contradicție, prin urmare n trebuie să fie prim.
    return True


if __name__ == "__main__":
    with open("rabin-miller.in", "r") as f, open("rabin-miller.out", "w") as w:
        sir_input = f.readline().strip()
        validitate_input = este_input_valid(sir_input)
        if validitate_input != "Corect":
            print(validitate_input)
            exit(0)
        if este_numar_prim(int(sir_input)):
            w.write("DA\n")
        else:
            w.write("NU\n")

Explicatie

este_input_valid(sir_input): Această funcție primește un șir de caractere ca intrare și verifică dacă acesta reprezintă un număr natural valid. În cazul în care șirul este valid, funcția returnează "Corect". În caz contrar, funcția returnează "Datele nu corespund restricțiilor impuse.".

este_numar_prim(n): Această funcție primește un număr întreg pozitiv n ca intrare și verifică dacă acesta este un număr prim utilizând testul de primalitate Miller-Rabin. În cazul în care n este prim, funcția returnează True. În caz contrar, funcția returnează False.

calculeaza_sd(x): Această funcție primește un număr întreg pozitiv x ca intrare și calculează cea mai mare putere a lui 2, denumită s, astfel încât x poate fi scris sub forma x = d * 2^s.

Funcția este utilizată în implementarea testului de primalitate Miller-Rabin pentru a calcula valorile s și d necesare.

if __name__ == "__main__":: Această condiție verifică dacă programul este rulat direct sau importat ca modul într-un alt program. În cazul în care programul este rulat direct, codul din blocul de instrucțiuni este executat. În caz contrar, blocul de instrucțiuni nu este executat. În programul dat, acest bloc verifică dacă datele de intrare sunt valide, iar în caz afirmativ, utilizează funcția este_numar_prim(n) pentru a verifica dacă numărul este prim sau nu. În funcție de rezultatul verificării, se scrie "DA" sau "NU" în fișierul de ieșire.