solution.py

#!/usr/bin/env python3

from Crypto.Util.number import isPrime, inverse, long_to_bytes

n = 3704315853248399520931286149673707861739862840174474318850719536726710629666865320437415173536083044248674656366508763974563867624182606586607673025903533434817835086465783354244510555600264634130273148019420890567027535547227590914410411615928952211983453962602151306110276831526240787368162679547412294786291064966782230443213405903174988451410995303610907533223263661657022610213941595505402486344210348467569618138176118521585956414022200085910233519821468163410050367827176390736810757738681372850691835129931503547843319099082181577780559763017889775357876998458807632809093618617485403908641927128567353193360668090395039602867558019689535059386138345918370693234076176881713132466541413701890144073499822831857803210562795039757846366860142062528042547185814880309533531009787005636747054029265024429693545769057677993257539297043796211840831462670392733400569034198413996091467275311168017215341595275384890539948027166145573735873646315369542533040843746818921047007048215557270397023005318175507358018082722469914231819553975967320629679189163059501755587530922829237056878993018295219879385447112790139581486354382509344797829578897288431682124840984604266323302273393857383811762984514580342125613255178652414822963564869351218173787050628467442637469971056029077563975073591774597269174531187818103532433894598280645766078102633738987646941950999789200401692007650522695229851082972906186018526013063835926631066293946238364751626692658502230496793712404951869930251498399478950443234400311619244641598277508121436749410796181780508379156355104722456111706582162269020945596481112763783522150990226114867335614536816138186566447583639848730080522260064509836147032605761376505234474572072334454737916929928957071355381652814660308963367515589390876610261412033928965154188453244893992884372548886256587154030720268721740548470139041848679945758053674161556432495785493981806766135281532135845427813009741588593121034452658170351001464780761847912542795779189019845240208570375066538167569500377796309764656262247487848676594103588076166586891212714090941313565555203618668077425758661000673064635747737323512221035673339963530741105199538223119
e = 65537
c = 1890542018923620935112404571390267463044771404340539852654454163421322784131374626938125628909369500484672852457699752836794851668177554752694569480833589506281060764802478167809475843864863010224742636449171460711562400590580946293278022177973604217197729862697501014955273338012893824413982401698433351247436693175518346363430547563575237429026208733403944381002182612963632178995085161195304895642449121609426847712983417558339924558444470082314710007938285805497203551318491773326164557602529684001253659352725160735497149899998922033507206044442056198143593433947379784128199737258656118578219421919085097879160406490718541327506724660681519907530750871792173102790503851758679070200134015226988860086382708659309820815068856900840522602932358921124524038033117760324955208431843589240233038158065364666936016479598474989719135380119445900393078743516628362378875759274530774051128410372267608865052931691829589285501692827537962441398960003650438584754477318978505734011792215065774609983390432428036137453401404511730410595609138140441384381140434709123509507412098963062352514519801938315793583554812274182187166556207679813626740486834909299435103532087886743107402138337819127106393630155591187052192592768360568615482279489728303155692177202699660408675290448360087377516035018720139480608360145681977445078359006122398216982658270012457757918360559874257031971071466702054740672492979859050720556486468907749247317125767439522125033157280673514896222594860231916321612316373414230977836316684012399810022699866047249292314143910277891224901227676543229301854239805048852751753718452085934738230534394786918582999166978975731235786980193716535038972364925871721576464369926284473469322169345932697475574026851062545326839136910259737680110603316183269062287676145272111842764815038653589575448189991669189039680679391320058642386385904979297205209960026834027355463625741637831547936201579980499257524969290528523228793264610947645811882323798981455817077587582259794354346200056385025658887609323422245456200058754051911510696552898584742736617473091204698952845833647824992896981893505822744013992729729002741594330169868768031061441416662299284


def iroot(k, n):
    hi = 1
    while pow(hi, k) < n:
        hi *= 2
    lo = hi // 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        midToK = pow(mid, k)
        if midToK < n:
            lo = mid
        elif n < midToK:
            hi = mid
        else:
            return mid
    if pow(hi, k) == n:
        return hi
    return lo

def decrypt(c, primes, e):
    phi = 1
    for p in primes:
        phi *= (p - 1)

    d = inverse(e, phi)

    return long_to_bytes(pow(c, d, n))


def constellation_factorization(n, stars):
    root = iroot(stars, n)

    n_candidate = 1
    offset = (root + 1) % 2

    primes = []

    while True:
        p = root + offset
        if isPrime(p):
            n_candidate *= p
            primes.append(p)

        p = root - offset
        if isPrime(p):
            n_candidate *= p
            primes.append(p)

        if n_candidate == n:
            return primes

        if n_candidate > n:
            return []

        offset += 2


for stars in range(2, 20):
    print('Assuming prime constellation of {} stars...'.format(stars))
    primes = constellation_factorization(n, stars)

    if primes:
        break


print(decrypt(c, primes, e))