Vabljeni na prvo predavanje Famnitovih izletov v matematično vesolje z naslovom The role of dice in world domination - a case study of Risk: the board game. Predavanje bo potekalo v sredo, 21. januarja 2026 ob 16.00, v Veliki predavalnici 3, UP FAMNIT in prek ZOOM povezave. Predaval bo Dr. Balázs Dávid, InnoRenew CoE, UP FAMNIT in UP IAM
“Cikel poljudnih predavanj o matematiki in njeni vlogi v sodobnem svetu”
Najnujnejše o testih praštevilskosti
natisni
Sreda, 20. marec 2026, ob 16.00, Velika predavalnica 3, UP FAMNIT/ ZOOM povezava
Najnujnejše o testih praštevilskosti
Dr. Aleksander Simonič, UP FAMNIT
Predstavljajte si, da morate ugotoviti, ali je dano stomestno liho naravno število praštevilo. Morda se ta naloga sliši kot slaba šala pri pouku matematike, vendar je odgovor ključnega pomena za sodobno kriptografijo. Preprost postopek bi bil, da za vsako naravno število d, večje od 1 in manjše od kvadratnega korena danega števila , preverimo, ali d deli n. To bi zahtevalo približno 1050 operacij deljenja. Tudi če bi vsaka takšna operacija trajala le 1 nanosekundo, bi na odgovor čakali okoli 1033 let, zato to ni učinkovit postopek.
Učinkovit postopek (ali algoritem) je tisti, ki potrebuje p(log n) operacij, kjer je p(x) nek polinom. Na srečo v praksi obstajajo zelo hitri verjetnostni algoritmi, npr. Miller–Rabinov test, ki s precejšnjo verjetnostjo pravilno določijo, ali je število praštevilo. Na predavanju si bomo ogledali nekatere takšne postopke in osnovne ideje v ozadju.
