Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Renault Android

Recomandare bicicleta e-bike 20&#...

Bing-Content removal tool

Nu pot accesa monitorulsv.ro de l...
 Cum sa elimini urmele de acnee?

Wc Geberit

Routere detinute in trecut si in ...

Teii din fața casei
 E-Mail in serie prin Excel si Out...

Modul alimentare rulou/jaluzea ex...

Recuperare fișiere dupa form...

Aplicatii stress test RAM
 Asigurare auto hibrid

Asus B550M - PC-ul nu porneste di...

Tzanca Uraganu - Inconjurat de Fe...

explicatie montaj breadboard
 

miller rabin

- - - - -
  • Please log in to reply
1 reply to this topic

#1
NGU_user

NGU_user

    New Member

  • Grup: Members
  • Posts: 7
  • Înscris: 18.01.2011
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.  :mellow:
Multumesc anticipat.  :rolleyes:

#2
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
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

Second Opinion 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

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate