# Generowanie dwóch dużych liczb pierwszych

from random import randrange, getrandbits

def is_prime(n, k=128):
    """ Sprawdza, czy liczba jest pierwsza 
        Argumenty:
            n -- int -- liczba do sprawdzenia
            k -- int -- liczba testów do przeprowadzenia
        Funkcja zwraca True, jeżeli liczba jest pierwsza
    """
    # Sprawdzenie, czy n nie jest parzyste
    # Należy pamiętać, że 2 jest liczbą pierwszą!
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    # Znajdź r i s
    s = 0
    r = n - 1
    while r & 1 == 0:
        s += 1
        r //= 2
    # Wykonuję k testów
    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, r, n)
        if x != 1 and x != n - 1:
            j = 1
            while j < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    return False
                j += 1
            if x != n - 1:
                return False
    return True
    
def isprime(x):
    x = abs(int(x))
    if x < 2:
        return "Less 2", False
    elif x == 2:
        return True
    elif x % 2 == 0:
        return False    
    else:
        for n in range(3, int(x**0.5)+2, 2):
            if x % n == 0:
                return n, False
        return True



def generate_prime_candidate(length):
    """ Losowe generowanie nieparzystej liczby całkowitej
        Argumenty:
            length -- int -- długość liczby do wygenerowania (w bitach)
        Funkcja zwraca liczbę całkowitą
    """
    # Generowanie losowych bitów
    p = getrandbits(length)
    # Stosuję maskę, aby ustalić wartość MSB i LSB na 1
    p |= (1 << length - 1) | 1
    return p
def generate_prime_number(length=1024):
    """ Generowanie liczby pierwszej
        Argument:
            length -- int -- długość liczby do wygenerowania (w bitach)
        Funkcja zwraca liczbę pierwszą
    """
    p = 4
    # Kontynuuję generowanie w przypadku, gdy test pierwszości zwraca False
    while not is_prime(p, 128):
        p = generate_prime_candidate(length)
    return p

print('Generowanie wartości n za pomocą liczb pierwszych p i q:')
print('\n')
print(generate_prime_number())
print('\n')
