RSA-260

[Kera]

Witam
Może dla zabawy, spróbujemy rozłożyć liczbę RSA-260.

Ukryta treść:    

22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

Jest tu wielu wirtuozów matematycznych, więc co wedle waszej wiedzy możemy wydedukować na temat rozkładu tej najmniejszej jeszcze nie rozłożonej liczby RSA-260

Dodano po 11 godzinach 42 minutach 3 sekundach:
jeżeli założymy że różnica między dzielnikami \(\displaystyle{ p,q}\) jest nie większa niż najmniejszy dzielnik \(\displaystyle{ p}\) tej liczby, to
\(\displaystyle{ \left(p-1 \right) \cdot \left( q-1\right) \le }\)

Ukryta treść:    

14107282862612736238518413624661975820671447973692178714112128889545826016026289675108923997487151663480962298036822805605800496502

a to sugeruje że maksymalna ilość sprawdzeń wynosi co najwyżej

Ukryta treść:    

142625033632102926562847708460993961074162003315040814463439299984943275689971427467327015226374077365269744458321861867994751096

Dodano po 4 godzinach 15 minutach 12 sekundach:
wkradł się błąd:
Przyjmujemy że liczba RSA-260 to \(\displaystyle{ N}\)
wiec powinno być
\(\displaystyle{ \mathbf{N}-\left( p-1\right) \cdot \left( q-1\right) \le }\)

[Kera]

aby temat się posunął , kto wie ile jest: \(\displaystyle{ 2^{11056412764764833217640542627513115463806044751235007697206874159564411470701000993256364863284873299542950165015700025585371102275727210558105966513471011544592029341062096178787457490939563262434598160261578882144338509684626535368545505278456190515638730266} }\) mod 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

[Brombal]

\(\displaystyle{ 2^
{11056412764764833217640542627513115463806044751235007697206874159564411470701000993256364863284873299542950165015700025585371102275727210558105966513471011544592029341062096178787457490939563262434598160261578882144338509684626535368545505278456190515638730266}
}\)

Liczba ta jest malutka, składa się jedynie z
\(\displaystyle{ 3328311886636344082007149864297528507040608916384365726066621371884390529070866452399694854636059726513578502462828607313746914111037621891741207727617545150426399783473054602261391791856409263100297248978415757965546611179621970775544601076935457061912102734}\) cyfr
Do jej zapisania wystarczy jedynie
\(\displaystyle{ 41603898582954301025089373303719106338007611454804571575832767148554881613385830654996185682950746581419731280785357591421836426387970273646765096595219314380329997293413182528267397398205115788753715612230196974569332639745274634694307513461693213273}\) dysków 1TB.

Dodano po 2 godzinach 53 minutach 49 sekundach:
Wykładnik potęgi dwójeczki jest liczbą złożoną.
\(\displaystyle{ 2 \cdot 3 \cdot 67 \cdot 242161 \cdot 1157207827 \cdot 98146005073371191921101489262030698125438694580341826160747426338098764294914542805498946212667799452776182150536997407137600899516771916994829657495693015603038784111226089034749059174162068893198819628743553701570251248504148431540557924439}\)
Ostatnia liczba również jest złożona

[Kera]

Dzięki Brombal, ostatnio przypadkowo odkryłem ciekawą zależność i mogę zapewnić, że reszta z tego dzielenia modulo jest podpowiedzią rozkładu RSA-260. Zależność jest wręcz ukryta na widoku, a efektem ubocznym jest "test pierwszości".

[ksetlak]

Hej, Kera, znowu jestem na tym forum

W międzyczasie szukałem grodzisk na mapie LIDAR, tworzyłem katalog ciekawych miejsc w okolicy, wrzucałem filmiki z Suno na YouTube itp. - niektóre rzeczy są na stronie ksetlak.pl. Ostatnio przypomniałem sobie o matematyce i tym forum

Ja już nie mam dostępu do serwera obsługującego funkcje GMP w języku PHP. Niby mam Pythona na kompie, ale nie umiem w nim programować. Czyli ogólnie nie mam jak operować na dużych liczbach, w szczególności na pierwiastkach dużych liczb.

Widzę, że zacząłeś zabawę z językiem C++. Jeżeli umiesz napisać program (algorytm Fermata) działający na bardzo dużych liczbach, to mogę Ci powiedzieć, o czym kiedyś mówiłem w temacie mojego sposobu na przyspieszenie Fermata.

Pytanie, czy potrafisz napisać od zera w C++ coś takiego na początek:

https://ksetlak.pl/matematyka/Fermat-Ksetlak-dla-Kera.xlsx
https://ksetlak.pl/matematyka/Fermat-Ksetlak-dla-Kera.ods

Jeżeli tak, to mogę Ci pokazać, o czym mówiłem kiedyś.

-------------

Mega ważna rzecz to sprawdzenie , czy w przykładzie z pliku pierwiastek z 5 jest liczbą całkowitą.

Można też sprawdzić, czy 5 jest kwadratem doskonałym. W PHP jest coś takiego jak gmp_perfect_square. I to jesty chyba szybsze niż samodzielne wyciąganie pierwiastka i zabawa z nim.

Dodano po 8 godzinach 23 minutach 29 sekundach:
Tam w algorytmie w PHP używałem pętli, która zatrzymywała się, gdy znalazłem wynik.

Kod: Zaznacz cały

$i = 1;
while ($i < 6) {
  if ($i == 3) break;
  echo $i;
  $i++;
}

Jeśli chcesz się ze mną pobawić, to pomnóż liczbę RSA-260 przez największą możliwą potęgę liczby 2, następnie wyciągnij pierwiastek. Potem sprawdź dokładnie , czy pierwiastek jest ok, czy skrypt wyliczył dobrze.

[Kera]

Co to da, że pomnożę liczbę RSA-260 przez największą możliwą potęgę liczby 2, następnie wyciągnę pierwiastek?

[ksetlak]

Mój sposób to operowanie na na przykład takich liczbach.

Ukryta treść:    

7503209065079545212282506209370595862271026809271799184278010848683531918846443952382445607764311518733269520027410177765414653330205295270617932891907267947273474765566237892617525475273447464215049098076111278532266081405477508716887129728476673596115699144420069906486880993173514140828449434580496080485538669334761905546118103110809853544970923762996486441846961529083834250561431718151492325114237055728141257026937178873004340145029695787886034421441312689124977364767607941920196616396056671704092126559913569391512591347929538538745140529334128853594661326369328327571127074153272896149721505932454505753792307004805588024779293646436831391668628083431363400391918984238481236709274956813803692230189933932426052336362345295062885829522649185644654439478630946373876439467719264353624819930088316255373991938771944412291318072353663864691421564046349447144216919753623175563252378290999468755159306575948269242904521666519117167857232709482046948527092094439169419185624043052294825525935368430447492109353293549767413030792778132867005477155128363266315416627211634337977565580051743323264890313468731303643729730509643452594561672245883341919772543115950123157348195850137109667430230062802178131618561923795861301732214740600767368413309561348044971354135413918286635737728294071346212296851682535348155726795382400772465618948049609982893451783500394236877739957841389391203260711474334755547239849426467139853816669100442199909416847454158633940381381232207571146195143185751247443081931798807523876114286108244811991145956695979719732889129133928579294665635794561299523659359325308842129679953625027913561849387055003751479189980526208542914601410365463723670222533906623831323978749337721723827826826014028290416915207058543290697774442051207678342386678463027843028680302102921774386419902518645467002231534651211205682779256873147070826507477317338180684168506276596851503810782200565133057397850443517213398884698851677019625568055939270028763604197945533372510468836620619452837686478955693420783610067478511824255040247500521968108292624455109862702517809635202194617187788655421988616302657710752393097740223218421366532262682912396097243585994215363754579160976554007341820620578797049592983662162322240192720394688021861940920972242965593284683215570264129189500343235843902857138032342504553107731383985363233252762900617054343428542280596849017803480395034917136050441060711905838217148821258828139379079246501298168166741977828162679693690322392753213679330286155160948716495469438390814965534398730381552639570175446219488021401577949134590826617098595887692912295040136746790425954634393420829455008794011436144198463111748202250165944587684782568774451298996936814701618888618314994999875518174676435837764618919908160825504740349981992492268348036133589725432087195082185285732017579726272339503519708572858760109032128314108117304557972866015222803311257444502918490766077868409246228937948216418066041744404955217049192511178376024789410216706936934502638444912408177379861720218448292261742082893640518090519037026171470143584196657373253532899461388700597452992140083730608639330483562352868383672949178136862822210719492636031604053018630137534370643757194635220302965090411088643999774406771097342745231673243452854053658568016190155969529207249594607472927870563474161477484870156352192855044724856895105189631419426321793215920867283336814167129776275849962452300083100417760590090880884047109246167799686258639643370185472122489335919390661034771509610606296795581036827278714654159599052373134453401599093005614329639487525338226941515163869782763866300542571403419202532979797281222854649618293771992726711215

Pierwszym krokiem jest wyciągnięcie z tego pierwiastka (jego części całkowitej, nie potrzebuję liczb po przecinku).

Potem użycie pętli i sprawdzania idealnego kwadratu.

Potem znów pierwiastek.

Więc najpierw warto sprawdzić, czy da się obliczyć pierwiastek. Bo ja np. w Pythonie na kompie nie mogę bez zainstalowania jakiegoś modułu. Kiedyś próbowałem go zainstalować, nie wyszło mi.

[Kera]

Poniżej pierwiastek zaokrąglony w górę i jego reszta.

Ukryta treść:    

86621065942872956614381812868640367447678280755827561953613899289230120726614702259770637796166372239857008743135602765271775583997481502723967497621370782194013649968272980623690925104570320801941041609553222620818928583709650715745475276774010343389091075280605852239766281978789257044144957727751575450602722974777063564219760675204627223007657756646240745288234118433584607019272952608867292623383080113271092446582236693762471455108074539110158922856203918976553848105407828564249900611152713712429953010080778657471415498726909339101031601861431333573173802068346896596638392924813290211295338084443479845361171838648555748739650881002200482265387903323260617519820200644589837167622915729771201380740068870939915861080376900410640655391370093907806331242416178405233787005287395447276152744106783374439116880186020119496127042095328607420430407510777058669017617242748371768438259176649991294637424590325715080709255479798635879461688667727781899003705939323013943228134554355331632358643704929148361435342665334493276131949381928382173719324359281124376827800795118679853084623920719180303125001391879278108522191553193625881575869794977019336784827169563134877556424233263537820250448969430395348280737127210872374868066333020462716718962085436583977963921939523469653669442025997332087965189330698156139114048329831925486218289671777694472781310234747772492724969644070730109401125331684628967121149434159506956927597848426062851212121772517817228272990064809986790927963900734675942114231287092569563524696760329968238953033089184466120081583098405006299181149562224363545192146809851098100766330942736495688840944163752266685078917099560595040278945467922032786729888035929301839759356089535484973915218605451151149025968625592434529804756661030636256032651534574706352994837621146241544016435250867311886789521758

126433743116166160505029734254991640567394754764930986389653534938869233249429408358572628767624695203570233796297476240976206339946435218614759432400928823292678748718147207492832862725746692726310707973460403378972978863904457611801314575809315194853916352486289269794302882480667563685256483106681257935094793172168170303452396257401945091533259456202283914365249779778949259605336912540458690269139600001499026734861149598363761822319983503644015221050786509436755811965826764545036353254121175094280744285127869060078426732371479921264454346724905146543336488695099879629891979201501863612529384263290681193138378115778355709547877061158365410249451078357305228247383838451762294300474625318451490308855148332756034117971063009737384624651335794080276125298458830518321028025502188095573637785316149718784989259671001285238163223866899392522330778456001830190285388766597574068342747557269886479519806254614727815864919222493864767167928640609686653057983746831785509757450005922733974714625447852418164356417559802236329825566899371246117867478061065102403112180372595362837249833252431522591802812798756973949534637453069394795817104327507120885211276776270299552723591879794141210297803283246752901953920952816482408552405986842524581816197573207983637447535968628612650302019530020522682713205469775273578286942166711577420874535417159018507599028703545847999567021063522745018495249855207855969116239800447119897100453141151457519576546578929461146658820018435749950670296104229359315711475285483605723623388039270166965341991751340366207081987288558089048135871596819905935883700915848437189705149860844304054433963594607080952570686874564090818337687168595872962025912416058017733952769703950156687341742715760676615865843550014968423857362335284814123132999541321624696088759662152692365058089588267603789628699349

Znam to co chcesz mi przekazać, ale ten sposób jest bardzo nieefektywny. A tym bardziej mnożenie przez potęgę liczby 2.
Jakieś inne pomysły, koledzy matematycy?

[ksetlak]

Kera, zgadzam się co do pierwszego modułu mojego algorytmu. Tam jest coś takiego jak na tej hiperboli dla x dodatnich. Większa ilość liczb pierwszych przyspiesza działanie Fermata, ale tylko na początku.

https://www.fisicalab.com/sites/all/files/contenidos/fundmat/grafico_hiperbola.png

Natomiast nie wiem, jak policzyć wydajność drugiego modułu. Więc o wydajności całości algorytmu, w szczególności dla liczb kilkuset cyfrowych, ciężko się wypowiadać. Zwłaszcza że tam można puścić milion pętli jednocześnie, byle serwer to obsłużył.

Rozmawiałem dzisiaj z programistą i przypomniałem sobie, czemu kiedyś rzuciłem ten temat

Oryginalny algorytm Fermata wygląda tak:

Kod: Zaznacz cały

Wejście: liczba N
Wyjście: dzielnik liczby N najbliższy pierwiastkowi

Jeśli N jest kwadratem liczby naturalnej
   return sqrt(N);  /*Znaleziono dzielnik*/

w przeciwnym razie
   r := ceil(sqrt(N));
   e := r^2 - N; 
   u := 2r + 1; v := 1;
   Dopóki nie znaleziono dzielnika
      Jeśli  e=0
         return (u-v)/2; /*Znaleziono dzielnik*/

      w przeciwnym razie
         Dopóki e<>0
            Dopóki e<0
               e:=e+u;
               u:=u+2;
            Dopóki e>0
               e:=e-v;
               v:=v+2;

Parę linijek kodu w jakimkolwiek języku programowania. A moja modyfikacja to całe strony A4

[ksetlak]

https://ksetlak.pl/faktoryzacja.php

Napisałem wspomniany skrypt w języku PHP.

Wziąłem na warsztat liczbę RSA-2048.

Ukryta treść:    

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Szanse na jej faktoryzację są nikłe, ale nie zerowe

[Kera]

Po co od razu z motyką na słońce startować. Podaj coś wartościowego na temat RSA-260. W przypadku RSA-260 już na wstępie wiadomo że różnica między dzielnikami wynosi min.

Ukryta treść:    

148080328021435409015172718576233408226345013785711541395786842608

i rośnie.

[ksetlak]

2698317658559544161041722078501334778195667176773966028465758037261188206041712318441449125389912935663860612368708009111201485484742263142326380699307714304077117696807830621394638236055253422359378451608987907037008287239626786573858557875202237146730943430

Ta liczba ma 259 cyfr i powstała w wyniku pomnożenia przez siebie 114 początkowych liczb pierwszych. Jest parzysta, więc można podzielić ją przez 2. Jej wielokrotności są gdzieś w pobliżu liczby RSA-260.

[Brombal]

2...

Ta liczba ma 259 cyfr i powstała w wyniku pomnożenia przez siebie 114 początkowych liczb pierwszych. Jest parzysta, więc można podzielić ją przez 2. Jej wielokrotności są gdzieś w pobliżu liczby RSA-260.

Oznacza to, że sprawdzenie \(\displaystyle{ NWD}\) dla tej liczby i liczby RSA-260 pozwoli na sprawdzenie 114 liczb.

[Kera]

Ukryta treść:    

aby temat się posunął , kto wie ile jest:
2
11056412764764833217640542627513115463806044751235007697206874159564411470701000993256364863284873299542950165015700025585371102275727210558105966513471011544592029341062096178787457490939563262434598160261578882144338509684626535368545505278456190515638730266
mod 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

Ile zajełoby na zwykłym kompie obliczenie algorytmem szykiego potęgowania, tej reszty?

[Brombal]

Do zwykłego zapisania tej liczby potrzeba więcej 1TB dysków niż jest atomów we wszechświecie. Chyba że jakaś sztuczka ...
Może by przedstawić drugą liczbę w postaci
\(\displaystyle{ 2^k \pm l}\)