Second Opinion
Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale. Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit. www.neurohope.ro |
miller rabin
Last Updated: Nov 20 2011 08:50, Started by
NGU_user
, Nov 19 2011 23:46
·
0
#1
Posted 19 November 2011 - 23:46
Salut,
In primul rand, sper ca am postat unde trebuie... in caz contrar, scuzele de rigoare. Am gasit pe wikipedia urmatorul algoritm: Input: n > 3, an odd integer to be tested for primality; Input: k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1 LOOP: repeat k times: pick a random integer a in the range [2, n − 2] x ad mod n if x = 1 or x = n − 1 then do next LOOP for r = 1 .. s − 1 x x2 mod n if x = 1 then return composite if x = n − 1 then do next LOOP return composite return probably prime Am cautat si alte surse, m-am uitat peste algoritmi scrisi in C si n-am reusit sa-mi dau seama. Nelamurirea mea este urmatoarea: de ce se testeaza x = 1 si x = n-1, atat inainte de loop cat si in interiorul ei? Din cate-am inteles, de pe wiki, a^d = 1(mod n) sau a^(2^r*d) = -1 (mod n), deci in primul caz ar trebui sa testeze daca x == 1 si in al doilea daca x == n-1. Prin urmare, de ce algoritmul arata ca mai sus? Poate sa-mi explice cineva, va rog? Am nevoie de algoritmul asta pentru o tema, pe saptamana viitoare. Multumesc anticipat. |
#2
Posted 20 November 2011 - 08:50
Nu ai cum sa verifici cu -1, pt ca nu exista verifici doar cu n-1 in for r=1...s-1 . Ma indoiesc ca ai nevoie de neaparat acest algoritm, el se bazeaza pe aritmetica modulara.
|
Anunturi
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users