Novo

Forum kao aplikacija na telefonu

Dodajte forum na početni ekran i koristite ga kao aplikaciju, sa menijem na dnu ekrana.

Veliki prosti brojevi, Polardov algoritam ...

Veliki prosti brojevi, Polardov algoritam ... 28.04.2004. u 22:55 · pre 274 meseca #1
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 ?
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Re: Veliki prosti brojevi, Polardov algoritam ... 29.04.2004. u 10:36 · pre 274 meseca #2
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
Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Re: Veliki prosti brojevi, Polardov algoritam ... 30.04.2004. u 21:13 · pre 274 meseca #5
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.
Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Re: Veliki prosti brojevi, Polardov algoritam ... 02.05.2004. u 12:25 · pre 274 meseca #6
Ajde ipak da se vratim na pocetno pitanje. Kolko ciklusa treba da provrtim da bi broj mogao da proglasim prostim ? (u Polardovom algoritmu)
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme