---
# System prepended metadata

title: Pfffft

---

# Pfffft
```python=
from Crypto.Util.number import *
n = 9538601039837440178261927169374130678758730744912936274728484335657913912145100217681955323973755948966368931646508068188903697598732297482662223112743544285222281158246055791351392206441202488175105009693655429379738971482455241095718722728013165344940100944530159210119817947390489235901206958570705164281600380640804661421382283193295122963524007177476158256734789917193861878635645812627268498613722092693060519241820024498856662687320519083885411190858282142701836173435459927762237853780703041038018877370565066048892184850356695892450491880774940543114467804277802895124004320934134192414239324028165803935713397443337571297810135296763368842070892004922725056117782311768067121341524178720717102150470679356701431638450872326205314643121197913447938272182395736167656548835442629334778890466779665276015670565122876751065058876429135275321284421486930932707474709737934240384842014695801024531241368362245386893367961374340301217483885903924451134665794688182286471
y = 8264768105228100481577267072448025764206717495292635640548187615478921502591166867926645907885293815798986305618351031289526156552546316112734888421721022944610431630948678880527683655976700732071767271644254104822242440244856474074932916866952689752576144029541317364277441690889758046334044077420303436132682617665286631795822941962246905272014594712907689569897607096029578372187936384369258559296928686343713054018693820199907890512547753290343853192561337127984951587298851111880417423370071611895700903905028598861667894195853434821242114002829465893289563395881010780047209390239218588429142336538527264270936464671811860921185699063325544406502512793507140928711741146075451964817644676901975654169460518833765167920659231284413235632717428454511512999625511966158848018191303535143985321971197232240134759012227244462755119081411501424244323304153732532175977685171526604812339610436925089522681050455874677358294229793230878911924504571494550831084819068672614463
c = 55027475114272357611162368016797629654665422519805373998932368075311161251900473826626562513710662298066586943825393109964409902948432230325381193469392908615585060732623651087521433143387367092515017821688332831932003406059575233215520159215163406998447286039603109813310800725152715416138056961184302262046302847817012063695701746907435524401783740189082972265276659061781199056289829256398927880276622301916705345901449314339838610446749193219016172028177830861392352866423064841869375383417666450323717006381869280514743793131216286221415621698319452790831313361692087744090096127392613773011098415822738999744916897345745733370949190421587906064120278438460641195780190882150954212576557441193218852751583146445936689723398018554037754216190856525581878375139890413870052900508454373865035779025694813553487395371375361071696421051763400321848549981865265961660656973761942047083119582785582256646254059307097521517158093476037072591198805867350780519280960453623240991871566645413005277747084834540060098765132282976488242779130150348215016384308110081706826857839867631082902393342336598283245894686616941045609371372574231323015877803976061852957443989487830675744990849456904694669301666694711289418479149660567852033549393648740008147955023015235627799871743253898767149015333944847588402498956173096577645166244818238556428020248697548664328185734864428159966212308590819334203171860074270151300815669623631857589738136249377976805220796759026321477352706778887561776095335183766873209965631458235754919616758427072135284208482837711944418892790249795198495988103406030914765948691409744739557220435189373755735916358293551460382536388410428629642945460176784913464230936520173101478157633960182967911025220193241198664764003800664747601391465809689797991730034407950838917268489191144520796761683121260686309522626911760325296714854901922960257570139476975297540411416167650646560883915966420597090157025645331965023967717296358487600
n_sqrt = 3088462568955213805312862502939753402938744820282598760038180488111693359432680285467917942206349960453386359560020917196683580619092828344437385087566084247864934177101568783776871204682678397853024334706276274194967880560946328278828203727458606798837443363769015587813027863081004176039939374876577685816756340023036381053304132304303868697911418834627192278932190959807500421060618286247241105544510897668443908549544867995122770565441538315617486916371824806780816326910240589086720
ans = []
count = 0
while(len(ans)==0):
    print(count)
    l = 0
    r = int(n ** 0.5)
    while(len(ans)==0 and l != r):
        print(l - r)
        p = (l + r) // 2
        q = ((p * 69) + 69 ) ^ 69
        for i in range(count):
            q *= 69
            q += 69
            q ^= 69
        if(p*q==n):
            ans.append(p)
            ans.append(q)
        elif(p*q>n):
            r = (l + r) // 2
        else:
            l = (l + r) // 2 + (l + r) % 2
    count+=1
print(ans)
```



[6639092410065305787560527939072166169737886641489586983166779477657101562311224207614156710297824465691083137668110267845509047349682835779194895420713885762152285525767283974531608903968448821830798696205352513949051021619066949320845188387166610849508890350965274825693649587359177162745248958344302181077205541648168821300878087935077786066878650862334397494512797846867376882506453886644097484687319, 1436732681318953537354730674963357795976056940278405252077526806344146685409859023153141493061309694268622495206057462128019437630931950464692937938388603638347005733323807263107382779935188441319210487032637430948255254427550142923892890790121418831659118234103088971471378936071526843358553410660674599611701155290613544190015665361053988954099066154477345138129514894608343731833356791899472763398587420804695502512011756884064707125376501382096972480414630014116307516911585643895016910231582803602900752343822745361064170694302620691905201203985142581196377249267409]




http://www.socr.ucla.edu/Applets.dir/SOCR_PrimeNumberDecomposition.html

3319546205032652893780263969536083084868943320744793491583389738828550781155612103807078355148912232845541568834055133922754523674841417889597447710356942881076142762883641987265804451984224410915399348102676256974525510809533474660422594193583305424754445175482637412846824793679588581372624479172151090538602770824084410650439043967538893033439325431167198747256398923433688441253226943322048742343659

```
n = 9538601039837440178261927169374130678758730744912936274728484335657913912145100217681955323973755948966368931646508068188903697598732297482662223112743544285222281158246055791351392206441202488175105009693655429379738971482455241095718722728013165344940100944530159210119817947390489235901206958570705164281600380640804661421382283193295122963524007177476158256734789917193861878635645812627268498613722092693060519241820024498856662687320519083885411190858282142701836173435459927762237853780703041038018877370565066048892184850356695892450491880774940543114467804277802895124004320934134192414239324028165803935713397443337571297810135296763368842070892004922725056117782311768067121341524178720717102150470679356701431638450872326205314643121197913447938272182395736167656548835442629334778890466779665276015670565122876751065058876429135275321284421486930932707474709737934240384842014695801024531241368362245386893367961374340301217483885903924451134665794688182286471
p = 6639092410065305787560527939072166169737886641489586983166779477657101562311224207614156710297824465691083137668110267845509047349682835779194895420713885762152285525767283974531608903968448821830798696205352513949051021619066949320845188387166610849508890350965274825693649587359177162745248958344302181077205541648168821300878087935077786066878650862334397494512797846867376882506453886644097484687319
q = 1436732681318953537354730674963357795976056940278405252077526806344146685409859023153141493061309694268622495206057462128019437630931950464692937938388603638347005733323807263107382779935188441319210487032637430948255254427550142923892890790121418831659118234103088971471378936071526843358553410660674599611701155290613544190015665361053988954099066154477345138129514894608343731833356791899472763398587420804695502512011756884064707125376501382096972480414630014116307516911585643895016910231582803602900752343822745361064170694302620691905201203985142581196377249267409
print(p*q == n)
m1 = (p-1) >> 1
print(long_to_bytes)
for i in range(1,1000000000):
    tmp = pow(y,i,n)
    if(c % tmp == 0):
        print(tmp)
        print(long_to_bytes(i))
```


```python
from Crypto.Util.number import *
from math import ceil, sqrt
from decimal import Decimal

def bsgs(g, y, p):
    m = int(ceil(sqrt(p - 1)))
    S = {pow(g, j, p): j for j in range(m)}
    gs = pow(g, p - 1 - m, p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p
    return None

n = 9538601039837440178261927169374130678758730744912936274728484335657913912145100217681955323973755948966368931646508068188903697598732297482662223112743544285222281158246055791351392206441202488175105009693655429379738971482455241095718722728013165344940100944530159210119817947390489235901206958570705164281600380640804661421382283193295122963524007177476158256734789917193861878635645812627268498613722092693060519241820024498856662687320519083885411190858282142701836173435459927762237853780703041038018877370565066048892184850356695892450491880774940543114467804277802895124004320934134192414239324028165803935713397443337571297810135296763368842070892004922725056117782311768067121341524178720717102150470679356701431638450872326205314643121197913447938272182395736167656548835442629334778890466779665276015670565122876751065058876429135275321284421486930932707474709737934240384842014695801024531241368362245386893367961374340301217483885903924451134665794688182286471
y = 8264768105228100481577267072448025764206717495292635640548187615478921502591166867926645907885293815798986305618351031289526156552546316112734888421721022944610431630948678880527683655976700732071767271644254104822242440244856474074932916866952689752576144029541317364277441690889758046334044077420303436132682617665286631795822941962246905272014594712907689569897607096029578372187936384369258559296928686343713054018693820199907890512547753290343853192561337127984951587298851111880417423370071611895700903905028598861667894195853434821242114002829465893289563395881010780047209390239218588429142336538527264270936464671811860921185699063325544406502512793507140928711741146075451964817644676901975654169460518833765167920659231284413235632717428454511512999625511966158848018191303535143985321971197232240134759012227244462755119081411501424244323304153732532175977685171526604812339610436925089522681050455874677358294229793230878911924504571494550831084819068672614463
c = 55027475114272357611162368016797629654665422519805373998932368075311161251900473826626562513710662298066586943825393109964409902948432230325381193469392908615585060732623651087521433143387367092515017821688332831932003406059575233215520159215163406998447286039603109813310800725152715416138056961184302262046302847817012063695701746907435524401783740189082972265276659061781199056289829256398927880276622301916705345901449314339838610446749193219016172028177830861392352866423064841869375383417666450323717006381869280514743793131216286221415621698319452790831313361692087744090096127392613773011098415822738999744916897345745733370949190421587906064120278438460641195780190882150954212576557441193218852751583146445936689723398018554037754216190856525581878375139890413870052900508454373865035779025694813553487395371375361071696421051763400321848549981865265961660656973761942047083119582785582256646254059307097521517158093476037072591198805867350780519280960453623240991871566645413005277747084834540060098765132282976488242779130150348215016384308110081706826857839867631082902393342336598283245894686616941045609371372574231323015877803976061852957443989487830675744990849456904694669301666694711289418479149660567852033549393648740008147955023015235627799871743253898767149015333944847588402498956173096577645166244818238556428020248697548664328185734864428159966212308590819334203171860074270151300815669623631857589738136249377976805220796759026321477352706778887561776095335183766873209965631458235754919616758427072135284208482837711944418892790249795198495988103406030914765948691409744739557220435189373755735916358293551460382536388410428629642945460176784913464230936520173101478157633960182967911025220193241198664764003800664747601391465809689797991730034407950838917268489191144520796761683121260686309522626911760325296714854901922960257570139476975297540411416167650646560883915966420597090157025645331965023967717296358487600
ans = []

'''
count = 0
while(len(ans)==0):
    print(count)
    l = 0
    r = int(n ** 0.5)
    while(len(ans)==0 and l != r):
        print(l - r)
        p = (l + r) // 2
        q = ((p * 69) + 69 ) ^ 69
        for i in range(count):
            q *= 69
            q += 69
            q ^= 69
        if(p*q==n):
            ans.append(p)
            ans.append(q)
        elif(p*q>n):
            r = (l + r) // 2
        else:
            l = (l + r) // 2 + (l + r) % 2
    count+=1
print(ans)
'''

ans = [6639092410065305787560527939072166169737886641489586983166779477657101562311224207614156710297824465691083137668110267845509047349682835779194895420713885762152285525767283974531608903968448821830798696205352513949051021619066949320845188387166610849508890350965274825693649587359177162745248958344302181077205541648168821300878087935077786066878650862334397494512797846867376882506453886644097484687319, 1436732681318953537354730674963357795976056940278405252077526806344146685409859023153141493061309694268622495206057462128019437630931950464692937938388603638347005733323807263107382779935188441319210487032637430948255254427550142923892890790121418831659118234103088971471378936071526843358553410660674599611701155290613544190015665361053988954099066154477345138129514894608343731833356791899472763398587420804695502512011756884064707125376501382096972480414630014116307516911585643895016910231582803602900752343822745361064170694302620691905201203985142581196377249267409]
p = ans[0]
q = ans[1]

#print(p*q == n)
m1 = (p-1) >> 1
#print(long_to_bytes)
#for i in range(1,1000000000):
#    tmp = pow(y,i,n)
#    if(c % tmp == 0):
#        print(tmp)
#        print(long_to_bytes(i))

y_m0p = pow(c,p,n)
y_pinv = pow(y,-p,n)
#y_p = pow(y,p,n)

y_m0 = (y_m0p*y_pinv) % n
print(y_m0)

    
print(bsgs(y,y_m0,n))

        
        
#1074129
```
```python=
possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890_!?{}%$&@()+-~=*/\\;,\"<>"
def find_m0(prev,length):
    if(length == 0):
        if(pow(y,bytes_to_long(str.encode(prev)),n) == y_m0): print(prev)
        return
    for i in possible:
        find_m0(prev+i,length-1)
for i in range(1,20):
    find_m0('',i)
```
```python=
for i in range(1000):
    print(long_to_bytes(i*(p-1)))
```
int(ceil((n-1)**0.5)) = 3088462568955213805312862502939753402938744820282598760038180488111693359432680285467917942206349960453386359560020917196683580619092828344437385087566084247864934177101568783776871204682678397853024334706276274194967880560946328278828203727458606798837443363769015587813027863081004176039939374876577685816756340023036381053304132304303868697911418834627192278932190959807500421060618286247241105544510897668443908549544867995122770565441538315617486916371824806780816326910240589086720
(p-1) ** 0.5 =
2576643632725586533540071410551402511926966425923360918998422165991515437761519941498600439418381563561213591292622301748734335953379658482636556299488848964984535831341422151462128945121254378028662784
(q-1) ** 0.5 =
1198637844104278925687650768358691767753689553087119344407724890222292056698763493128469041165418787348261396176246663314953921846090862047548768322266867198547551024629066488326554094066459371442836707731210620099588463764037153456899876394763986054186369182729902327007044640230604800


y_m0 = 400006050897663432083921091860168732790860203128931635889517122949574068191511713242310576423953392595655567927364180437002813597411413498327036094248687369472191918841865320375846143810294285158305471058993589872109828641438837340285274761379091208693752182387193818357881846921056788666487232666643038036827754206799260426560801473122725187152005665253499201618796681449559008309930107250214769126337641771296564355900699829612203495983108795349247084919053539456070645761421546837981707108669085966012379692891622577741820136299422829655873311744578418878018154310185043712606879293173776637042974513536492363525135001794715782148125828245832390669032972665961321256817858625643419612051835402413344203593048176906073623981170765120471170500358500046330807857055627447661491760294334927480907207476693587613488214661241761158690964557032279424472416287841296296291455046338488861604485793503180720474726022810584352481859372151856740665004030054579651003826344362397486

```python=
prime_already_get = []
dup = 0
for i in range(1000000):
    tmp = getPrime(31)
    if(tmp in prime_already_get):
        dup += 1
        print(dup)
        continue
    prime_already_get.append(tmp)
    if(((p-1)%tmp)==0):
        print(tmp)
```
```python=

```
1241159693

1479736039

1841903251

1227656359

2061384947

http://www.factordb.com/index.php
factors =[6070220398670377781840618452566141552676379823913197960163957517455072144738254164604476609706628567487569866243111819018258132033122800442807270531707057,1414219382851944940018194919477228335544050858431751505251638124732114784153858161590805750311738618604955625782142846822493009257,104429039898529118921800466421700262498978748368570655794747590957079592012005900890139119355107060909,2010339349,1841903251,2]


factors = [2372562687710726156398423112305181403588087021948455279001818288969150612064915470306882991911959065167626589497533386494761274254438967,1151966812605370897621192478568205205333075506377718771097603319409120402034147864981494996933208259954898034933033607023,70572748886417517956931010735287134882695621342889152809738109620427776857035716820937088331,2061384947,2010339349,1841903251,1479736039,1227656359,1241159693,2]

```python=
prime_already_get = []
dup = 0
composite = [2372562687710726156398423112305181403588087021948455279001818288969150612064915470306882991911959065167626589497533386494761274254438967,1151966812605370897621192478568205205333075506377718771097603319409120402034147864981494996933208259954898034933033607023,70572748886417517956931010735287134882695621342889152809738109620427776857035716820937088331]
while True:
    tmp = getPrime(31)
    if(tmp in prime_already_get):
        dup += 1
        # print(dup)
        continue
    prime_already_get.append(tmp)
    for i in composite:
        if((i%tmp)==0):
            print(tmp)
```
```python=
targets = [2372562687710726156398423112305181403588087021948455279001818288969150612064915470306882991911959065167626589497533386494761274254438967,1151966812605370897621192478568205205333075506377718771097603319409120402034147864981494996933208259954898034933033607023,70572748886417517956931010735287134882695621342889152809738109620427776857035716820937088331]
possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890_!?{}%$&@()+-~=*/\\;,\"<>"
def find_m0(prev,length):
    if(length == 0):
        for i in targets:
            if(i % bytes_to_long(str.encode(prev)) == 0): print(prev)
        return
    for i in possible:
        find_m0(prev+i,length-1)
for i in range(1,20):
    find_m0('',i)
```

Bje1
1114268977

fW=9
1716993337


factors = [2372562687710726156398423112305181403588087021948455279001818288969150612064915470306882991911959065167626589497533386494761274254438967,670920956873445862196256431115204266708855321770953832826436483375311084293478458024729653877048365013485218279,63335469570752949318565665079345680179244208952690919985774771884749131678495718203,2061384947,2010339349,1841903251,1716993337,1479736039,1227656359,1241159693,1114268977,2]



```python=
x = [2010339349,1841903251,1716993337,1479736039,1227656359,1241159693,1114268977]
y_m0_modq = c % q
N = []
A = []
N.append(q)
A.append(y_m0_modq)
for i in x:
    N.append(i)
    A.append(c % i)
    
from functools import reduce

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * pow(p, -1, n_i) * p
    return sum % prod
    
print(chinese_remainder(N,A))
```