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 False
        return True
    except ValueError:
        return False


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


def main():
    """Funcția principală care validează datele de intrare și afișează rezultatul în fișierul de ieșire."""
    with open("rabin-miller.in", "r") as f, open("rabin-miller.out", "w") as w:
        sir_input = f.readline().strip()
        if not este_input_valid(sir_input):
            print("Datele nu corespund restricțiilor impuse.")
            exit(0)
        elif este_numar_prim(int(sir_input)):
            w.write("DA")
        else:
            w.write("NU")
        print("Datele sunt introduse corect.")


# Apelăm funcția principală pentru a rula programul.
main()






'''Explicatie'''
Acest cod implementează un program care primește un număr natural n în fișierul de intrare și verifică dacă acesta este prim folosind algoritmul Miller-Rabin.

Înainte de a efectua testul de primalitate, se validează datele de intrare pentru a se asigura că n este un număr natural valid mai mare sau egal cu 2. Dacă datele de intrare nu respectă aceste restricții, programul afișează un mesaj corespunzător și se oprește prin apelul funcției exit(0).

Dacă datele sunt valide, programul continuă și efectuează testul de primalitate folosind funcția este_numar_prim. Aceasta implementează testul Miller-Rabin, care este o metodă probabilistică pentru a verifica dacă un număr este prim sau nu.

Dacă n este prim, funcția este_numar_prim returnează True, altfel returnează False. În funcția principală main, dacă n este prim, programul afișează "DA" în fișierul de ieșire, altfel afișează "NU". La sfârșit, se afișează un mesaj corespunzător în consolă.