"""
RSA is an asymmetric encr algo that relies on a public key and a private key. 
Public key encrypts message M to a cyphertext C:
  
  C = M^e % N

e is part of the public key and is implementation specific, chosen
but frequently chosen to be 3 (bad) or 17 or 65537 (a number that has a 
lot of 0s, makes "computer maths easy).

N is also part of the public key - N = p*q, where p and q are (large) prime 
numbers.

Decrypting the message:

  M = C^d % N

d is the part of the private key (private exponent) derived using p and q,
such that:

  e*d=1%((p-1)(q-1))

To break the encryption, if one gets to factor N to p and q, d can be 
derviced from there

"""
import sys

def d(p, q, e=3):
    """ TODO: Doesn't make sense!?"""
    return 1%((p-1)*(q-1))

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b) 


def trick(A, B, p_max=10):
    """
    If A and B are mutually prime (gcd is 1):
    
    A^p = m*B + 1

    for some p and m. 
    
    returns p and m 
    """
    if gcd(A,B) != 1:
        print("ERROR: A, B not mutually prime!")
        return None, None
    for p in range(2, p_max):
        m, found = 1, False
        lhs, rhs = A**p, m*B + 1
        while lhs > rhs:
            rhs = m*B + 1
            print("({}, {}): {} =? {}".format(p, m, lhs, rhs))
            if lhs == rhs:
                found = True
                break
            m += 1
        if found:
            print('===== FOUND')
            print("p={}, m={}".format(p, m))
            return p, m
    print("Not found up to {}".format(p_max))
    return None, None



# (g^p/2 + 1) * (g^p/2 -1) = m*N --- this is almost like a*b~=N
# because of m*N, the terms on LHS might not be the factors but
# multiple of factors, i.e. a*factor, b*factor
# e.g. 7^4/2 + 1 = 50; 7^4/2 - 1 = 48; which are not factors of 15
# gcd(50, 15) = 5, gcd(48, 15) = 3

# Trick #2:
# g^x = m_1*N + r
# g^(x+p) = m_2*N + r
# [if g^p = m_1*N + 1 => expanding g^(x+p)=g^x*x^p=(m_1*N+1)*(m_2*N+r)=...=(m_1*m_2 + 3m_1+m_2)*N +r ~= something*N+r 

if __name__ == '__main__':
    trick(int(sys.argv[1]), int(sys.argv[2]))