import decimal
import math
from Crypto.Util.number import long_to_bytes

# Returns GCD, x, y such that a * x + b * y = GCD(a, b)
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
""" 
GCD of 97/20		
97=4*20+17
20=1*17+3
17=5*3+2
3=1*2+1 
2=2*1+0
GCD is 1 (remainder is 0 at end)

GCD of 100/20
100=5*20+0
GCD is 20
"""

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def cube_root(x):
    return decimal.Decimal(x) ** (decimal.Decimal(1) / decimal.Decimal(3))

def big_exponent(base, exp, mod):
    answer = 1
    while exp > 0:
        if exp % 2 == 0:
            base = (pow(base, 2)) % mod
            exp //= 2
        else:
            answer = (base * answer) % mod
            exp -= 1
    return answer

# https://stackoverflow.com/questions/356090/how-to-compute-the-nth-root-of-a-very-big-integer
def find_invpow(x,n):
    high = 1
    while high ** n <= x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def find_invpowAlt(x,n):
    low = 10 ** (len(str(x)) / n)
    high = low * 10

    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1
	
"""
# basic

c = 44431629706061305008143502423137012887277828135988218627924826848164974267369140114151116956542699876402139670467425045450301114213737667412294102131791639564117923536368256828998437520972285622395911648477760804325095186682980015103833775233929473511843707365929109604516730159351999709137396760951561724605394354694071245237933265597444643797363943646984709831864750620734406848781544782140580781553249778510852115417666510789869996230415178275721761766565175907645048897615709905109681846646689243575820894299256876151171950776037745474751371071726067019383683284965811296018491131082246881726583726305095371092727
p = 212691419494563911012016458107764706057027846660556923783295585947349837091530859782385987932959348656441135167812270695168242808938780720834424043119692739636350805618004977676905871536695150965234220710456913491845984031497483010709484108563662345764645393885590662297355667270911004188786194404493930584763
q = 343771555081128227560810773103703230186239929820487041012723599379603845162266648302382922824441150879585264855730391652295840969079127665092831035812274337557171176301884861906361106483559667673320137971212932682795921938761120540964583816300085118595116098901061368547890422579172952819065405212828098113467
e = 102218683034763828584589001371647041187532369615830565599787446410855812507707

totient = (p - 1) * (q - 1)
d = modinv(e, totient)
flag = big_exponent(c, d, p * q)
print(long_to_bytes(flag))
"""

""" 
# broadcast attack

c1 = 261345950255088824199206969589297492768083568554363001807292202086148198632298416227800170521403879169323939870136918495166376001415603107530798184803733942230649625863328280827871999560410058158409477539013408803889636337981870043792827095136037430392653831785807945977864288192407940225619843273330120029313
n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627
c2 = 147535246350781145803699087910221608128508531245679654307942476916759248403409499940709875170482499717373851969854700407365859710668248221534523112910895863625501694252104929562808450560410931902051428001118134260015071473417379253511812576559427770355902270332217159041674805147868562215268081818231962157802
n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309
c3 = 633230627388596886579908367739501184580838393691617645602928172655297372237425265855898468213006428127058041006464863408951623696827190570241149630919096283514787011922034385643767864879634861850565793738024061098801151563062727926809059198778760627479771564465550880228117974715945657575773914891371732645934
n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723

e = 3
t1 = c1 * (n2 * n3) * modinv(n2 * n3, n1)
t2 = c2 * (n1 * n3) * modinv(n1 * n3, n2)
t3 = c3 * (n1 * n2) * modinv(n1 * n2, n3)
c = (t1 + t2 + t3) % (n1 * n2 * n3)
with decimal.localcontext() as context:
    context.prec = 150
    m = cube_root(c)

print(long_to_bytes(m))
# http://crypto.stackexchange.com/questions/6713/low-public-exponent-attack-for-rsa
"""



"""
# weird rsa
# dp and dq are given instead of e

c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

qinv = modinv(q,p)
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
h = (qinv * (m1-m2)) % p
m = m2 + (h*q)
print(long_to_bytes(m))
"""