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 ?
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.
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Veliki prosti brojevi, Polardov algoritam ...
Registrovani: 3 ( vjova, kumkat, Nebojsa Milanovic )