Pasimėgaukime! Kai nusibosta kasdienybės rutina, vargai, skausmai ir nepritekliai, keliaukite į skaičių šalį. Ten – paslaptinga romantika! Ten – tyra ir tikslu! Ten viską gali pakartoti vėl ir vėl – niekas nesensta, neišblėsta.
*
Berods, esu čia rašęs apie RSA algoritmo genialųjį paprastumą? Tada skaičiau Simon Singh „Code book“ ir baltai pavydėjau – kodėl man į galvą nešovė tokia mintis? Bet, matyt, mano galva neparengta šaudymui… Nes net ir tada nepagalvojau apie štai tokią, panašią į RSA, pirminių skaičių magiją…
*
Mažesniems skaitytojams priminsiu, kad pirminis skaičius yra toks natūralusis (aš taip noriu!) skaičius, kuris be liekanos dalijasi tik iš vieneto ir iš savęs. Savo penktokams jau paaiškinau Eratosteno rėčio metodą pirminiams skaičiams rasti. Šiandien pasitikrinsiu, ar jie išmoko, ar prisimena…
*
Dabar stebėkite. Tarkime, jūs norite mesti monetą ir išsiaiškinti, kuris pirmas pradės žaisdamas šachmatais. Bėda, kad partneris – Kinijoje. Nėra bėdos! Gera žinoti, kad visi pirminiai skaičiai yra dviejų rūšių – tokie, kuriuos padalijus iš keturių lieka vienetas, ir tokie, kurių liekana yra trys. Vienos ir kitos rūšies skaičių yra maždaug „po lygiai“. Taigi jūs pasirenkate porą pirminių, tarkime, pirmos rūšies skaičių, juos sudauginate ir el. paštu pasiunčiate partneriui į Kiniją. Jis el. paštu parašo jums, kad renkasi, tarkime, antrojo tipo skaičius. Jūs jam parašote kitą el. pašto laišką ir nurodote vieną sandaugos daugiklį. Kinas mato, kad jo pasirinkimas blogas, todėl pirmąjį ėjimą šachmatų lentoje darote jūs. Supratote?
*
Kur čia šuo pakastas? Ogi tai, kas yra ir RSA algoritmo pagrindas: kinas negali iš sandaugos sužinoti, kurie du pirminiai skaičiai sudauginti. Kodėl negali? Todėl, kad tie skaičiai labai dideli! Pabandykite. Aš jums siunčiu sandaugą 111025561 (tai dar mažas skaičius!). Parašykite čia, kurio tipo ir kokie skaičiai sudauginti…
***
PAPILDYTA pagal diskusijos rezultatus:
Atsakymai
Burgis, 2012-01-31 11:36:56
Pagirkite mane… 🙂
A., 2012-01-31 13:28:39
33331*3331
n*4+3
Burgis, 2012-01-31 13:44:07
A.: nieko sau! Sveikinu! Aš maniau, kad ilgai niekas „nenulauš“…
Ta proga parodysiu, koks čia įdomus pirminių skaičių rinkinys:
31
331
3331
33331
333331
3333331
33333331
Tik nepamanykite, kad taip tęsis amžinai!…
Pentium100, 2012-01-31 13:56:11
Tokį mažą skaičių tai ir WolframAlpha sugeba išskaidyt…
http://www.wolframalpha.com/input/?i=factor+111025561
Burgis, 2012-01-31 14:02:26
Ačiū, Pentium100, aš ir nežinojau, kad jau tokia paslauga yra… 🙁
Beje, gal A. gali parašyti, kaip išskaidė?
petras, 2012-01-31 14:05:28
ne į temą.
kažkada senai, dėstytojas pasakojo, kad jav kuriam tais universitete studentai ieškojo didžiausio iki tol žinomo pirminio skaičiaus. tai buvo pajungę celeron 800 pusei ar gal visiem metams. ir gavo skaičių nesveiko ilgumo. įdomu, ar kas bando šiais laikais pasiekt dar didesnių skaičių ?:)
A., 2012-01-31 14:35:20
Tiesiog excel’yje padalinau sandaugą iš pirmųjų 64000 pirminių skaičių… 🙂
Burgis, 2012-01-31 16:28:24
A.: o tai kaip eksel’yje tuos skaičius pasigaminote?
Manfredas, 2012-01-31 20:06:09
O jeigu truputį pratęsiant?
Aš jums siunčiu sandaugą 111025561 (tai dar mažas skaičius!)
O koks būtų didelis? Kad net Kinijos vyriausybė neišspręstų? Kodėl?
… kinas negali iš sandaugos sužinoti, kurie du pirminiai skaičiai sudauginti. Kodėl negali? Todėl, kad tie skaičiai labai dideli!
O sudauginti didelius skaičius kinas tai gali?..
Tai kuo vis tik skiriasi daugyba nuo “faktorizavimo”? O gal yra dar panašių uždavinių, kurių partneris iš Kinijos negalėtų išspręsti? O ką reikštų, jeigu kaip nors išspręstų?
(Čia jau pažengusiems:) o jeigu kinas naudotų kvantinę mechaniką, ar galėtų greičiau išspręst? Kaip?
…
Šauni tema!
Burgis, 2012-01-31 20:43:50
Ačiū, Manfredai, už gerus klausimus. Tai mane ir stulbina šiuose metoduose: tu paimi du didelius didelius pirminius skaičius, matai juos, sudaugini ir… niekas, išskyrus tave, nebegali pasakyti, kurie skaičiai buvo sudauginti! Tik todėl, kad sandauga yra milžiniška, pavyzdžiui, 500 skaitmenų ar daugiau. Faktorizavimas reiškia išskaidymą į daugiklius. Metodų daug, bet ne milžiniškoms sandaugoms. Mane labai sudomino ta nuoroda į skaidymo svetainę – kiek ten pajėgūs išskaidyti?
Jei kas nors išmoktų išskaidyti į daugiklius neriboto dydžio sandaugas, nei RSA šifravimo algoritmas, nei čia aprašytasis nebeturėtų prasmės. Kalbama, kad kvantiniai kompiuteriai tai mokės, bet negirdėjau, kad jau moka…
A., 2012-01-31 22:32:40
Tai galima juk su visais iš eilės skaičiais tikrinti (ne tik pirminiais), bet tam, kad jų būtų mažiau pasiskolinau iš interneto platumų tik pirminius 🙂 na nelabai matematiškai, bet juk reikėjo tik atsakymo, o šitas būdas pasirodė greičiausias 🙂
Pentium100, 2012-02-01 15:23:32
Dėl WolframAlpha – nežinau kokį didžiausią skaičių ten gali išskaidyt, bet tas puslapis labai tinkamas visokiem dalykam, susijusiem su matematika (ir ne tik). Lygčių sprendimas, skaičių sekos (suvedus seką bando surasti jos formulę) ir taip toliau. Tik kartais užklausas reikia pasistengt parašyt taip, kad suprastų.
Bet ir šiaip informacijos galima paklaust.
Dėl pirminių skaičių sąrašo – manau jį galima atsisiųst iš kur nors 🙂
Iš duomenų saugos dar labai įdomus yra Diffie–Hellman apsikeitimas raktais – naudojamas kai reikia naudojant nesaugų kanalą perduoti slaptą raktą.
Vainius, 2012-02-24 22:53:09
Kažkas čia ne taip. Jei iš anksto žinai, kad sudauginti du pirminiai skaitmenys, tai gali pasirašyt algoritmą, kuris užtruks maximum šaknis iš n (n – sandaugos skaitmenų skaičius) laiko. Tiesiog algoritmas turi patikrint visus skaičius iki šaknies iš n.
Kaip suprantu, sunku būtų, jeigu nežinotum, kelių pirminių skaičių tai sandauga, tada reikėtų tikrint visas įmanomas kombinacijas ir algoritmo trukmė pailgėtų iki faktorialinės.
Burgis, 2012-02-25 10:18:42
Vainiui: esmė – sandaugos dydis. Jūs matote paveikslėlyje – 10^98 laipsniu kompiuteriui tapo neįveikiamu skaičiumi, išskaidyti daugikliais nebepajėgė. Taip, ir mane stebina, kad paprastas buitinis kompiuteris sugeba skaidyti toooookio dydžio skaičius! Ir vis tik negirdėjau, kad RSA algoritmas būtų pripažintas „neveiksniu“…
Vainius, 2012-02-26 23:34:29
Aš įtariu, jei wolframui būtų nurodyta, kad sudauginti būtent du skaičiai, tai būtų išskaidęs ir 10^98 eilės skaičių. Tuo labiau, kad čia tik online versija. Bet gal jei siunčiamos labai ilgos žinutės ir naudojami labai ilgi skaičiai, tai susideda ir net tą šaknį iš n variantų patikrint darosi per brangu. O wiki kažkaip sudėtingiau žymiai tą RSA algoritmą aiškina, per įvairius public key, private key..
Audrius, 2012-12-30 17:19:22
333333333333333331 taip pat pirminis.
http://web.math.princeton.edu/math_alive/Crypto/Lab2/Factorization.html
Audrius, 2012-12-30 17:55:46
Sveiki, Naujųjų Metų proga pastebėsiu, kad dviejų pirminių p1=4*k+1 ir p2=4*m+1 sandaugą visada galima išreikšti dviejų kvadratų suma p1*p2=r^2+s^2. Kai p1=4*k+3 ir p2=4*m+3 sandaugą išreikšti dviejų kvadratų suma galima tik kai p1=p2. http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares ,todėl gerbiamam kiniečiui, norint žaisti baltaisiais, nereikės faktorizavimo, užteks patikrinti, ar gautasis skaičius užrašomas kaip dviejų kvadratų suma.
Audrius, 2012-12-31 19:18:39
Ir štai programėlė, kuri labai šauniai išreiškia didelius skaičius kvadratų sumomis: http://www.alpertron.com.ar/FSQUARES.HTM .
Dėkoju už labai gražų uždavinį, buvo nuostabu jį spręsti. Linkiu, kad 2013 Jums būtų kupini atradimų!