[ sannyy @ 19.01.2011. 11:48 ] @
Kod S-S testa prostosti otprilike mi je sve jasno osim onog kad u zadatku imam da ispitam prostost broja s vjerojatnoscu npr 0,8. E tu mi nije jasno zasto idemo 3 koraka, tj za b=2, b=3, b=5.... Znam da ima veze s ovim 0,8... 1/2^3, ali ne mogu sebi to predociti u glavi. Treba mi kristalnost u tome da bih bila nacisto sa sobom.
A sto se tice M-R testa, to mi nikako ne ide... Zbunjuje me ono kad biramo proizvoljno b (0<b<n).
Moze li mi neko malo to objasniti?
[ Nedeljko @ 19.01.2011. 12:19 ] @
Citat:
sannyy: Znam da ima veze s ovim 0,8... 1/2^3, ali ne mogu sebi to predociti u glavi. Treba mi kristalnost u tome da bih bila nacisto sa sobom.
A sto se tice M-R testa, to mi nikako ne ide... Zbunjuje me ono kad biramo proizvoljno b (0<b<n).
Moze li mi neko malo to objasniti?


Treba da bude

.

Citat:
sannyy: A sto se tice M-R testa, to mi nikako ne ide... Zbunjuje me ono kad biramo proizvoljno b (0<b<n).
Moze li mi neko malo to objasniti?


Ne baš , već . Ako je broj prost, onda M-R test prolazi za svaki takav broj . Test ponavljaš određen broj puta za razne brojeve . Što je veći broj osnova za koje prođe test, to je sigurnije da je testirani broj prost.
[ sannyy @ 23.01.2011. 16:03 ] @
Hvala na pomoci!
Nisam znala da je b u tim granicama. Ono sto kaze da proizvoljno biramo b, zapravo kaze da idemo redom od 2 pa dok ne padnemo test ako je broj slozen, jer ako je prost onda test prolazi za svako b.
[ Nedeljko @ 23.01.2011. 17:01 ] @
Pa, i ako ne padne test u nekom koraku se zaustavljaš kada dobiješ dovoljnu pouzdanost da je broj prosto.