Jei reikia skaičių, pasirinkite pirminių

Sausio 31, Antradienis

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:

skaidymas_2

skaidymas_3

skaidymas_4

skaidymas_5

patiko(0)



RSS

Atsakymai (18)

Burgis, Sausio 31 11:36  #

Pagirkite mane… :-)

patiko(0)



A., Sausio 31 13:28  #

33331*3331
n*4+3

patiko(0)



Burgis, Sausio 31 13:44  #

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!…

patiko(0)



Pentium100, Sausio 31 13:56  #

Tokį mažą skaičių tai ir WolframAlpha sugeba išskaidyt…
http://www.wolframalpha.com/input/?i=factor+111025561

patiko(0)



Burgis, Sausio 31 14:02  #

Ačiū, Pentium100, aš ir nežinojau, kad jau tokia paslauga yra… :-(
Beje, gal A. gali parašyti, kaip išskaidė?

patiko(0)



petras, Sausio 31 14:05  #

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ų ?:)

patiko(0)



A., Sausio 31 14:35  #

Tiesiog excel’yje padalinau sandaugą iš pirmųjų 64000 pirminių skaičių… :-)

patiko(0)



Burgis, Sausio 31 16:28  #

A.: o tai kaip eksel’yje tuos skaičius pasigaminote?

patiko(0)



Manfredas, Sausio 31 20:06  #

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!

patiko(0)



Burgis, Sausio 31 20:43  #

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…

patiko(0)



A., Sausio 31 22:32  #

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 :-)

patiko(0)



Pentium100, Vasario 1 15:23  #

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

patiko(0)



Vainius, Vasario 24 22:53  #

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.

patiko(0)



Burgis, Vasario 25 10:18  #

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“…

patiko(0)



Vainius, Vasario 26 23:34  #

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

patiko(0)



Audrius, Gruodžio 30 17:19  #

333333333333333331 taip pat pirminis.
http://web.math.princeton.edu/math_alive/Crypto/Lab2/Factorization.html

patiko(0)



Audrius, Gruodžio 30 17:55  #

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.

patiko(0)



Audrius, Gruodžio 31 19:18  #

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ų!

patiko(0)



XHTML

Leistinos XHTML žymos:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>