[ RooTeR @ 28.04.2004. 21:55 ] @
U Polardovom(za ispitivanje da li je broj prost) algoritmu se zadaje "n" koje oznacava koliko ciklusa ce da se vrse provere pre nego sto se saopsti da je broj prost(ili da nije prost). E sad, mene zanima u odnosu na to koliko broj ima cifara, koliko treba da bude n. Na primer, ako broj ima 50 cifara, koliko treba da je n, odnosno koliko ciklusa treba da prodje pre nego sto broj moze da se proglasi prostim ?
[ Nedeljko @ 29.04.2004. 09:36 ] @
Algoritam o kojem pričaš je zastareo. Sada se zna i za polinomijalne testove primalnosti. Dakle, u polinomijalnom vremenu možeš da ispitaš da li je broj prost, pa testovi pseudoprimalnosti gube smisao.

http://www.cse.iitk.ac.in/news/primality.html
[ noviKorisnik @ 29.04.2004. 10:41 ] @
[ RooTeR @ 30.04.2004. 11:41 ] @
kako znati da li je r prost broj ? a kako odrediti q ?
[ Nedeljko @ 30.04.2004. 20:13 ] @
Pa ako ovaj algoritam ima polinomijalnu složenost, onda petlja ne sme da se izvrši mnogo puta. To znači da će vrednosti za r biti relativno male, pa možeš koristiti najjednostavnije algoritme za to što si pitao. Uostalom, pročitaj članke samih autora.
[ RooTeR @ 02.05.2004. 11:25 ] @
Ajde ipak da se vratim na pocetno pitanje. Kolko ciklusa treba da provrtim da bi broj mogao da proglasim prostim ? (u Polardovom algoritmu)