def small_e_msg(key, ciphertexts=None, max_times=100):
    """If both e and plaintext are small, ciphertext may exceed modulus only a little

    Args:
        key(RSAKey): with small e, at least one ciphertext
        ciphertexts(list)
        max_times(int): how many times plaintext**e exceeded modulus maximally

    Returns:
        list: recovered plaintexts
    """
    ciphertexts = get_mutable_texts(key, ciphertexts)
    recovered = []
    for ciphertext in ciphertexts:
        log.debug("Find msg for ciphertext {}".format(ciphertext))
        times = 0
        for k in range(max_times):
            msg, is_correct = gmpy2.iroot(ciphertext + times, key.e)
            if is_correct and pow(msg, key.e, key.n) == ciphertext:
                msg = int(msg)
                log.success("Found msg: {}, times=={}".format(i2h(msg), times // key.n))
                recovered.append(msg)
                break
            times += key.n
    return recovered 

def hastad_unpadded(ct_list, mod_list, e):
    """
    Implementing Hastad's Broadcast Attack
    """
    m_expo = crt(ct_list, mod_list)
    if m_expo != -1:
        eth_root = gmpy2.iroot(m_expo, e)
        if eth_root[1] == False:
            print "[+] Cannot calculate e'th root!"
            return -1
        elif eth_root[1] == True:
            return long_to_bytes(eth_root)
    else:
        print "[+] Cannot calculate CRT"
        return -1 

def common_modulus(e1, e2, n, c1, c2):
	g, a, b = egcd(e1, e2)
	if a < 0:
		c1 = neg_pow(c1, a, n)
	else:
		c1 = pow(c1, a, n)
	if b < 0:
		c2 = neg_pow(c2, b, n)
	else:
		c2 = pow(c2, b, n)
	ct = c1*c2 % n
	m = int(gmpy2.iroot(ct, g)[0])
	return long_to_bytes(m) 

def root(self, a, e):
  	return (gmpy2.iroot(a,e)) 

def factor_prime_power(x):  # TODO: move this to a separate math/number theory module
    """Return p and d for a prime power x = p**d."""
    if x <= 1:
        raise ValueError('number not a prime power')

    k = 10
    # test whether p is below 2**k, for positive k
    p = 2
    while p < 1<<k:
        if x % p == 0:
            d = 0
            while x > 1:
                x, r = divmod(x, p)
                if r == 0:
                    d += 1
                else:
                    raise ValueError('number not a prime power')

            return int(p), d

        p = next_prime(p)

    # find prime factors of d
    p, d = x, 1
    while is_square(p):
        p, d = isqrt(p), 2*d
    e = 3
    while k * e <= p.bit_length():
        w, b = iroot(p, e)
        if b:
            p, d = w, e * d
        else:
            e = next_prime(e)

    if is_prime(p):
        return int(p), int(d)

    raise ValueError('number not a prime power') 

def iroot(x, n):
        """Return (y, b) where y is the integer nth root of x and b is True if y is exact."""
        if x == 0:
            return x, True

        k = (x.bit_length() - 1) // n
        y = 1<<k
        for i in range(k-1, -1, -1):
            z = y | 1<<i
            if z**n <= x:
                y = z
        return y, x == y**n 

def common_modulus(e1, e2, n, c1, c2):
    	g, a, b = egcd(e1, e2)
    	if a < 0:
    		c1 = neg_pow(c1, a, n)
    	else:
    		c1 = pow(c1, a, n)
    	if b < 0:
    		c2 = neg_pow(c2, b, n)
    	else:
    		c2 = pow(c2, b, n)
    	ct = c1*c2 % n
    	m = int(gmpy2.iroot(ct, g)[0])
    	return m