# This piece of code observe's Robert Grant's claim that prime
# factors of RSA public keys can be found from the repeating decimal
# inverse of semi-prime.

# The method was determined from Grant's Instagram account:
#   https://www.instagram.com/p/B2HwOirnHH2/?utm_source=ig_web_copy_link

# To test this claim we

# 1. Create two primes
# 2. Multiply the two primes to produce a semi-prime
# 3. Take inverse of the semi-prime
# 4. Search the two primes for one or both of the factors.
# 5. The results will either be:
#   a)     every repeating inverse of semi-prime will contain both primes <-- Allows breaking RSA if efficiency is good enough.
#   b) NOT every repeating inverse of semi-prime will contain both primes <-- Does not allow breaking RSA reliably.

# In order to prove Grant's factoring algorithm valid, the method must
# work on all semi-primes. Otherwise it's just a coincidence, like how
# the number Pi happens to contain patterns like 0123456789 at position
# 17,387,594,880.

from decimal import Decimal, getcontext
from random  import SystemRandom
from typing  import Tuple


def generate_random_prime_smaller_than(n) -> int:
    """Returns a random prime smaller than n.

     Based on
         https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
     """
    sieve = [True] * n

    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)

    list_of_primes = [2] + [i for i in range(3,n,2) if sieve[i]]
    random_prime   = SystemRandom().choice(list_of_primes)

    return random_prime


def multiply_prime_numbers(first_prime:  int,
                           second_prime: int
                           ) -> int:
    """Create semi-prime, i.e. multiply two prime numbers.

    The semi-prime is the RSA public key.
    """
    return first_prime * second_prime


def get_inverse_of_semi_prime(semi_prime: int) -> Decimal:
    """Take inverse of semi-prime.

    The inverse should contain both prime number factors of the semi-prime.
    """
    return Decimal(1) / Decimal(semi_prime)


def get_period_of_inverse_of_semi_prime(semi_prime):
    """Find length of period in inverse of semi-prime.

    The period defines the length of numbers where the prime factors of
    the public key can be.

    Borrowed from https://www.geeksforgeeks.org/find-length-period-decimal-value-1n/
    """
    remainder = 1  # Initialize remainder
    for i in range(1, semi_prime + 2):
        remainder = (10 * remainder) % semi_prime

    # Store (n+1)th remainder
    d = remainder

    # Count the number of remainders before next
    # occurrence of (n+1)'th remainder 'd'
    count     = 0
    remainder = (10 * remainder) % semi_prime
    count    += 1
    while remainder != d:
        remainder = (10 * remainder) % semi_prime
        count    += 1
    return count


def search_primes_in_inverse_of_semi_prime(inverse_of_semi_prime: Decimal,
                                           first_prime:           int,
                                           second_prime:          int
                                           ) -> Tuple[int, int]:
    """Return True if inverse of semi-prime contains both prime factors."""

    inverse_of_semi_prime_string = str(inverse_of_semi_prime)

    position_of_first_prime  = inverse_of_semi_prime_string.find(str(first_prime))
    position_of_second_prime = inverse_of_semi_prime_string.find(str(second_prime))

    return position_of_first_prime, position_of_second_prime


def found_both_prime_factors(first_prime:  int,
                             second_prime: int,
                             semi_prime:   int) -> True:
    """Find prime factors of semi-prime from the inverse of.

    If prime factors were found, return True
    """

    # Step 0: Determine the required precision of the decimals
    period_length     = get_period_of_inverse_of_semi_prime(semi_prime)
    getcontext().prec = period_length + 10

    # Step 1: Get the inverse of the semi-prime
    inverse_of_semi_prime = get_inverse_of_semi_prime(semi_prime)

    if debug:
        print(f"\nDEBUG: Inverse of the semi prime has period of {period_length} and looks as follows:")
        print('       ' + str(inverse_of_semi_prime))
        print('')

    # Step 2: See if the prime factors are in the inverse of the semi-prime.
    position_first, position_second = search_primes_in_inverse_of_semi_prime(inverse_of_semi_prime, first_prime, second_prime)

    found_first_prime_factor  = position_first  != -1
    found_second_prime_factor = position_second != -1

    if debug:
        if found_first_prime_factor:
            print(f"DEBUG: Found the first prime factor {first_prime} in position {position_first}")
        else:
            print(f"DEBUG: Did not find the first prime factor {first_prime} in the inverse of the semi-prime.")

        if found_second_prime_factor:
            print(f"DEBUG: Found the second prime factor {second_prime} in position {position_second}")
        else:
            print(f"DEBUG: Did not find second prime factor {second_prime} in the inverse of the semi-prime.")

    return found_first_prime_factor or found_second_prime_factor


debug = False

def main():
    PRIME_UPPER_LIMIT           = 500
    NUMBER_OF_TESTS_TO_RUN      = 1000
    used_prime_tuples           = []
    prime_pair_repeat_threshold = 10

    for _ in range(NUMBER_OF_TESTS_TO_RUN):

        # RSA private key generation
        prime_pairs_repeated = 0
        while True:
            first_prime  = generate_random_prime_smaller_than(PRIME_UPPER_LIMIT)
            second_prime = generate_random_prime_smaller_than(PRIME_UPPER_LIMIT)

            if (first_prime, second_prime) not in used_prime_tuples:
                used_prime_tuples.append((first_prime, second_prime))
                break
            else:
                prime_pairs_repeated += 1
                if prime_pairs_repeated >= prime_pair_repeat_threshold:
                    print("Running out of unique prime tuples for private keys. Exiting.")
                    exit()

        # RSA public key generation
        semi_prime = multiply_prime_numbers(first_prime, second_prime)

        if debug:
            print(f"\nDEBUG: Upper limit of generated primes for private key is {PRIME_UPPER_LIMIT}")
            print(f"\nDEBUG: Private key is {(first_prime, second_prime)}")
            print(f"DEBUG: Public  key is {semi_prime}")

        if not found_both_prime_factors(first_prime, second_prime, semi_prime):
            print(f"Grant's \"factoring method\" FAILS when primes are {(first_prime, second_prime)}")


if __name__ == '__main__':
    main()

# Example output:

# Grant's "factoring method" FAILS when primes are (151, 241)
# Grant's "factoring method" FAILS when primes are (53, 271)
# Grant's "factoring method" FAILS when primes are (211, 449)
# Grant's "factoring method" FAILS when primes are (41, 53)
# Grant's "factoring method" FAILS when primes are (271, 229)
# Grant's "factoring method" FAILS when primes are (137, 17)
# Grant's "factoring method" FAILS when primes are (271, 239)
# Grant's "factoring method" FAILS when primes are (5, 41)
# Grant's "factoring method" FAILS when primes are (151, 101)
# Grant's "factoring method" FAILS when primes are (137, 389)
# Grant's "factoring method" FAILS when primes are (463, 67)
# Grant's "factoring method" FAILS when primes are (281, 463)
# Grant's "factoring method" FAILS when primes are (211, 241)
# Grant's "factoring method" FAILS when primes are (199, 331)
# Grant's "factoring method" FAILS when primes are (197, 127)
# Grant's "factoring method" FAILS when primes are (211, 353)
# Grant's "factoring method" FAILS when primes are (349, 101)
# Grant's "factoring method" FAILS when primes are (101, 29)
# Grant's "factoring method" FAILS when primes are (151, 271)
# Grant's "factoring method" FAILS when primes are (127, 197)
# Grant's "factoring method" FAILS when primes are (127, 193)
# Grant's "factoring method" FAILS when primes are (37, 23)
# Grant's "factoring method" FAILS when primes are (271, 101)
# Grant's "factoring method" FAILS when primes are (13, 3)
# Grant's "factoring method" FAILS when primes are (271, 241)
# Grant's "factoring method" FAILS when primes are (239, 107)
# Grant's "factoring method" FAILS when primes are (3, 127)
# Grant's "factoring method" FAILS when primes are (353, 271)
# Grant's "factoring method" FAILS when primes are (241, 37)
# Grant's "factoring method" FAILS when primes are (73, 271)
# Grant's "factoring method" FAILS when primes are (449, 137)
# Grant's "factoring method" FAILS when primes are (157, 11)
# Grant's "factoring method" FAILS when primes are (229, 101)
# Grant's "factoring method" FAILS when primes are (241, 137)
# Grant's "factoring method" FAILS when primes are (241, 401)
# Grant's "factoring method" FAILS when primes are (41, 13)
# Grant's "factoring method" FAILS when primes are (67, 13)
# Grant's "factoring method" FAILS when primes are (139, 47)
# Grant's "factoring method" FAILS when primes are (2, 13)
# Grant's "factoring method" FAILS when primes are (13, 127)
# Grant's "factoring method" FAILS when primes are (163, 109)
# Grant's "factoring method" FAILS when primes are (239, 53)
# Grant's "factoring method" FAILS when primes are (353, 109)
# Grant's "factoring method" FAILS when primes are (17, 101)
# Grant's "factoring method" FAILS when primes are (101, 499)
# Grant's "factoring method" FAILS when primes are (401, 251)
# Grant's "factoring method" FAILS when primes are (463, 239)
# Grant's "factoring method" FAILS when primes are (101, 53)
# Grant's "factoring method" FAILS when primes are (239, 19)
# Grant's "factoring method" FAILS when primes are (397, 101)
# Grant's "factoring method" FAILS when primes are (11, 271)
# Grant's "factoring method" FAILS when primes are (2, 101)
# Grant's "factoring method" FAILS when primes are (103, 101)
# Grant's "factoring method" FAILS when primes are (463, 281)
# Grant's "factoring method" FAILS when primes are (311, 211)
# Grant's "factoring method" FAILS when primes are (193, 353)
# Grant's "factoring method" FAILS when primes are (353, 257)
# Grant's "factoring method" FAILS when primes are (311, 239)
# Grant's "factoring method" FAILS when primes are (113, 127)
# Grant's "factoring method" FAILS when primes are (331, 239)
# Grant's "factoring method" FAILS when primes are (5, 101)
# Grant's "factoring method" FAILS when primes are (233, 349)
# Grant's "factoring method" FAILS when primes are (17, 113)
# Grant's "factoring method" FAILS when primes are (257, 353)
# Grant's "factoring method" FAILS when primes are (241, 223)
# Grant's "factoring method" FAILS when primes are (19, 13)
# Grant's "factoring method" FAILS when primes are (127, 11)
# Grant's "factoring method" FAILS when primes are (271, 11)
# Grant's "factoring method" FAILS when primes are (233, 449)
# Grant's "factoring method" FAILS when primes are (23, 137)