Što su prosti brojevi i zašto su toliko vitalni za suvremeni život?

glavni broj

Ako ste završili srednju školu i čitate ovaj članak, vjerojatno barem znate sljedeće o prostim brojevima: Primeri su skup svih brojeva koji se mogu podjednako podijeliti s 1 i sami, bez druge čak i podjele moguće. Brojevi poput 2, 3, 5, 7 i 11 svi su prosti brojevi. Ono što manje ljudi zna jest zašto su ti brojevi toliko važni i kako je matematička logika iza njih rezultirala vitalnim primjenama u suvremenom svijetu.

Evo nečega cool u vezi s prostim brojevima: Matematičari su pokazali da se apsolutno bilo koji cijeli broj može izraziti kao umnožak prostih brojeva, samo prostih i ništa drugo. Na primjer:



Da biste dobili 222, isprobajte 2 * 3 * 37



123,228,940? Pa, to je samo, 2 * 2 * 5 * 23 * 79 * 3391

faktor-stablo-48Ovo se pravilo, koje se naziva glavnim pravilom faktorizacije, naziva i nešto drugo: Temeljni teorem aritmetike. Ima smisla kad razmišljamo o tome što su prosti brojevi, brojevi koji se ne mogu dalje razdvajati. Dakle, dok pokušavamo razdvojiti bilo koji broj na dva broja, a zatim ih razdvojiti na dva broja, ako je moguće, i tako dalje, na kraju ćemo ostati samo s prostim brojevima.



Sve ovo može se činiti kao ništa više od kul matematičke neobičnosti. Ali to postaje važno zahvaljujući jednoj jednostavnoj dodatnoj činjenici: koliko su uspjeli utvrditi najbolji matematičari i informatičari, potpuno je nemoguće iznijeti uistinu učinkovitu formulu za računanje velikih brojeva u proste brojeve.

To će reći, mi imati načine računanja velikih brojeva u proste brojeve, ali ako to pokušamo napraviti s 200-znamenkastim brojem ili 500-znamenkastim brojem, koristeći iste algoritme koje bismo koristili za računanje 7-znamenkastog broja, najnaprednija svjetska superračunala i dalje uzmite apsurdnu količinu vremena da završite. Kao, vremenski okviri dulji od formiranja planeta i, jer krajnje veliki broj, dulji od starosti samog svemira.

titan superračunalo



Dakle, postoji funkcionalno ograničenje veličine brojeva koje možemo podijeliti na proste brojeve, a ta je činjenica apsolutno bitna za suvremenu računalnu sigurnost. Gotovo sve što računala mogu lako učiniti, a da ih ne mogu lako poništiti, bit će od interesa za računalnu sigurnost. Suvremeni algoritmi šifriranja iskorištavaju činjenicu da možemo lako uzeti dva velika broja i pomnožiti ih zajedno da bismo dobili novi, super-veliki broj, ali da niti jedno računalo koje je još stvoreno ne može uzeti taj super-veliki broj i brzo shvatiti u koja su to dva broja čineći ga.

Ova zaštita na matematičkoj razini omogućuje ono što se naziva kriptografijom javnog ključa ili šifriranjem, pri čemu se ne moramo brinuti o objavljivanju ključa za šifriranje prijenosa, jer jednostavno posjedovanje tog ključa (vrlo velik broj) neće pomoći nikome da poništi šifriranje koje je stvorilo. Da biste poništili šifriranje i pročitali poruku, trebaju vam glavni čimbenici ključa koji se koristi za šifriranje - a kao što smo vidjeli, to nije nešto što možete sami shvatiti.

Soba Summita o sigurnosti

To nam omogućuje da zaobiđemo glavni paradoks šifriranja: Kako uopće sigurno komunicirate početne detalje potrebne za postavljanje sigurne komunikacije? U kriptografiji javnog ključa, koja je okosnica računalne enkripcije, to možemo zaobići jer specifičnosti načina stupanja u siguran kontakt same po sebi ne moraju biti sigurne. Upravo suprotno - ljudi uglavnom objavljuju poveznice do svojih javnih ključeva na društvenim mrežama, pa će im što veći broj ljudi moći šifrirati poruke. Iako danas postoji popriličan broj algoritama za šifriranje koji koriste glavno faktoriziranje, povijesno najznačajniji i još uvijek konceptualni nacrt za to područje naziva se RSA.

Bilo da se radi o prenošenju podataka o vašoj kreditnoj kartici Amazonu, prijavi u banku ili ručnom šifriranju e-pošte kolegi, mi stalno koristimo računalnu enkripciju. A to znači da se neprestano služimo prostim brojevima i oslanjamo se na njihova neparna numerička svojstva radi zaštite cyber-age načina života. To nije besmislena akademska potraga, nastojanje da se bolje razumiju prosti brojevi, jer se gotovo sva moderna sigurnost oslanja na trenutna ograničenja tog razumijevanja.

To sve ne znači da nije bilo napretka u faktoringu velikih brojeva. 2009. istraživači su umrežili nekoliko stotina računala i potrošili oko 2000 godina za jedno računalo, koristeći napredne algoritme za faktoring da bi izračunali broj 'RSA-768' - to jest, broj s 232 znamenke koje je postavila RSA grupa kao faktoring izazov. Dokazivanje da je moguće razbiti 768-bitnu enkripciju u neuniverzalnim vremenskim razmjerima topline i smrti neprihvatljivo je za svijet sigurnosti, pa se standard sada preselio na RSA-1024, koristeći brojeve s 309 znamenki.

glava za šifriranje

1024-bitna enkripcija i dalje bi trebala biti sigurna od svih koji nemaju vremenski stroj, koliko nam je poznato - premda na internetu obiluju glasine o tajnim projektima kvantnih računala u NSA-i ili negdje drugdje, onima koji mogu prožvakati i do 2048. godine. bitna enkripcija kao da nije ništa. Apsolutno nema dokaza da takvo što postoji.

Prosti brojevi su cool. Kao što Carl Sagan tako rječito ističe u romanu Kontakt, postoji određena važnost za njihov status kao najtemeljnijeg gradivnog elementa svih brojeva, koji su i sami gradivni elementi našeg razumijevanja svemira. U toj knjizi vanzemaljci odabiru poslati dugački niz prostih brojeva kao dokaz da je njihova poruka inteligentna i da nije prirodnog porijekla, jer su prosti brojevi jedno što se ne može promijeniti zbog razlika u psihologiji, načinu života ili evolucijskoj povijesti. Bez obzira na to kako napredni vanzemaljski oblik života izgleda ili misli, ako razumije svijet oko sebe, gotovo sigurno ima koncept premijera.

Zbog toga mnogi matematičari teoriju brojeva doživljavaju pomalo poput arheologije. Osjećaj nije u izmišljanju novih tehnologija, već u otkrivanju logičnih temelja svemira, onih koji opisuju njegovo ponašanje posvuda, tijekom svih vremena.

Pogledajte našu seriju 2007es.com Explains za detaljnije izvještavanje o najnovijim tehnološkim temama današnjice.

Copyright © Sva Prava Pridržana | 2007es.com