Testovi prostosti i metode faktorizacije : diplomski rad - Ivić, Marko (M. Ivić, 2014)
Sažetak na hrvatskom: U konstrukciji kriptosustava s javnim ključem, tj. osobnih jednosmjernih funkcija, obično se koriste neki „teški“ matematički problemi. Jedan od tih problema je problem faktorizacije velikih prirodnih brojeva. Najpoznatiji takav kriptosustav je RSA, kod kojega se pomoću velikih prostih brojeva p i q gradi javni modul n. U ovom diplomskom radu obrađene su osnove RSA kriptosustava s ciljem predstavljanja problematike na koju sustav nailazi. Sigurnost RSA kriptosustava temelji se na tajnosti dva slučajno izabrana velika prosta broja i na problematici faktoriziranja velikih složenih brojeva. Što je broj veći, to je teže odrediti da li je prost ili ne. Metode kojima se za promatrani broj n određuje da li je prost zovu se testovi prostosti. S ciljem lakšeg shvaćanja i stvaranja ukupnog dojma težine problema predstavljeni su Solovay-Strassenov i Miller-Rabinov test prostosti te njihova programska implementacija. Testovi prostosti dijele se na vjerojatnosne i determinističke. Zbog svoje brzine izvođenja češće se koriste vjerojatnosni testovi. Ako neki broj n ne zadovolji neki od vjerojatnosnih testova prostosti, tada se sa sigurnošću može reći kako je broj složen. Definiranjem da je broj složen ne dobiva se informacija o njegovim faktorima. Kod složenih brojeva postoji više različitih metoda faktorizacije i u tom dijelu obrađene su najčešće korištene kao što su faktorske baze te metoda verižnog razlomka i kvadratnog sita. Metodom kvadratnog sita faktoriziran je RSA-640 broj (193 znamenke), a uspjesi u faktorizaciji tako velikih brojeva skreću pozornost na to koliko velik bi trebao biti RSA modul kako bi komunikacija bila sigurna (danas, ali i u skoroj budućnosti).