Matematyka.pl

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

Ukryta treść:

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ść:

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

Ukryta treść:

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 }\)

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

Kera pisze: 26 paź 2024, o 00:24 \(\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

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".

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.

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

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.

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?

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

https://ksetlak.pl/faktoryzacja.php

Napisałem wspomniany skrypt w języku PHP.

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

Ukryta treść:

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

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ść:

i rośnie.

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.

ksetlak pisze: 20 kwie 2025, o 20:31 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.

Ukryta treść:

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

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}\)

Matematyka.pl

RSA-260

RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260

Re: RSA-260