Number Theory

def are_coprime(p1, p2):
    """
        This function check if p1 and p2 are coprime

        Args:
            p1 (list): list of prime numbers of the first number
            p2 (list): list of prime number of the second number

        Returns:
            Return a  boolean result
    """
    r = True
    for entry in p1:
        if entry in p2:
            r = False
            break
    return r

def getPrimeNumber(n, safe=True):
    """
        This function generate a large prime number
        based on "A method for Obtaining Digital Signatures
        and Public-Key Cryptosystems"
        Section B. How to Find Large Prime Numbers
        https://dl.acm.org/doi/pdf/10.1145/359340.359342

        Args:
            n (Integer): The size of the prime number. Must be a multiple of 64
            safe (Boolean): When generating the prime number, the function must find a safe prime number, based on the Germain primes (2p + 1 is also a prime number)

        Returns:
            Return the prime number
    """
    if n % 64 != 0:
        print("Must be multiple of 64")
        return
    # from sys import getsizeof
    upper = getrandbits(n) 
    lower = upper >> 7
    r = randint(lower, upper)

    while r % 2 == 0:
        r += 1

    # Now, we are going to compute r as prime number
    i = 100
    while 1:
        # Check if it's a prime number
        if _millerRabinTest(r):
            break

        # TODO: it's dirty, need to change that
        # i = int(log2(r))
        # i *= randint(2, 50)

        r += i
        # print(f"{i} {r}")
        i += 1


    # print(_fermatLittleTheorem(r))
    # print(getsizeof(r))
    return r

def getSmallPrimeNumber(n) -> int:
    """
        This function is deprecated

        Args:
            n (Integer): Get the small prime number until n

        Returns:
            Return the first prime number found
    """
    is_prime = True

    while True:  
        for i in range(2, n):
            # If n is divisible by i, it's not a prime, we break the loop
            if n % i == 0:
                is_prime = False
                break

        if is_prime:
            break
        is_prime = True
        n = n + 1

    p = n
    return p

def get_n_prime_numbers(n) -> list:
    """
        This function return a list of n prime numbers

        Args:
            n (Integer): the range, must be an integer

        Returns:
            Return a list of n prime numbers
    """
    l = list()

    count = 2
    index = 0
    while index < n:
        is_prime = True
        for x in range(2, count):
            if count % x == 0:
                is_prime = False
                break

        if is_prime:
            l.append(count)
            index += 1

        count += 1

    return l

def get_prime_numbers(n) -> list:
    """
        This function get all prime number of the n

        Args:
            n (Integer): find all prime number until n is achieves

        Returns:
         Return a list of prime numbers
    """
    l = list()
    for i in range(2, n):
        if n % i == 0:
            l.append(i)
    return l

def isPrimeNumber(p):
    """
        Check if the number p is a prime number or not. The function iterate until p is achieve. It's a smallest function identifying if p is a prime number
        To identify if p is prime or not, the function check the result of the Euclidean Division has a remainder. If yes, it's means it's not a prime number

        Args:
            p (Integer): number if possible prime or not

        Returns:
            Return a boolean if the number p is a prime number or not. True if yes
    """
    for i in range(2, p):
        if p % i == 0:
            return False
    return True

def isSafePrime(n) -> bool:
    """
        This function has not been implemented yet, but check if the number n is a safe prime number. This function will test different properties of the possible prime number n

        Args:
            n (Integer): the prime number to check

        Returns:
            Return a Boolean if the prime number n is safe or not. True if yes, otherwise it's False
    """
    if n.bit_length() >= 256:
        return True

    # Do Sophie Germain's test

    return False

def sieveOfEratosthenes(n) -> list:
    """
        This function build a list of prime number based on the Sieve of Erastosthenes

        Args:
            n (Integer): Interate until n is achives

        Returns:
            Return a list of all prime numbers to n
    """
    if n < 1:
        return list()

    eratost = dict()
    for i in range(2, n):
        eratost[i] = True

    for i in range(2, n):
        if eratost[i]:
            for j in range(i*i, n, i):
                eratost[j] = False

    sieve = list()
    for i in range(2, n):
        if eratost[i]:
            sieve.append(i)

    return sieve

def sophieGermainPrime(p) -> bool:
    """
        Check if the number p is a safe prime number: 2p + 1 is also a prime

        Args:
            p (Integer):  Possible prime number

        Returns:
            Return True if p is a safe prime number, otherwise it's False
    """
    pp = 2 * p + 1
    if _millerRabinTest(pp):
        return True
    return False

def fibonacci(n) -> list:
    """
        This function generate the list of Fibonacci

        Args:
            n (integer): it's maximum value of Fibonacci sequence

        Returns:
            Return a list of n element in the Fibonacci sequence
    """
    fibo = [0, 1]
    fibo.append(fibo[0] + fibo[1])
    for i in range(2, n):
        fibo.append(fibo[i - 1] + fibo[i])
    return fibo