[C] Aiuto sviluppo Miller-Rabin

[mikeb90]

salve a tutti,
qualcuno potrebbe darmi una mano, una spiegazione "terra terra" di questo algoritmo? Ho inserito la dicitura del linguaggio C perchè dovrei creare un programma in quel linguaggio, ma in primis mi servirebbe capire che cribio fanno le parti di questo algo. Grazie in anticipo.

Input: n > 2, an odd integer to be tested for primality;
       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 randomly in the range [2, n − 1]
   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

[bancodeipugni]

Originariamente inviato da mikeb90

salve a tutti,
qualcuno potrebbe darmi una mano, una spiegazione "terra terra" di questo algoritmo? Ho inserito la dicitura del linguaggio C perchè dovrei creare un programma in quel linguaggio, ma in primis mi servirebbe capire che cribio fanno le parti di questo algo. Grazie in anticipo.

Input: n > 2, an odd integer to be tested for primality;
       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 randomly in the range [2, n − 1]
   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

potevano anche scrivere un testo in italiano

devi creare un filtro che in input riceve un intero dispari maggiore di 2 e verificare che sia un numero primo k un parametro indicatore dell'accuratezza del test

in uscita il programma deve saper dire se il numero è composto oppure probabilmente primo
scrivere n − 1 come 2s·d con d dispari della potenza del 2 -1 .... ma che cazzo è s ???

quindi:
ciclo da ripetere k volte (usa il for)
scegli un random nel range da 2 a n-1
x ← ad mod n ma che cazzo è ?? ad chi ??? devi fare una operazione di mod ... forse x mod n boh...
se x = 1 or x = n − 1 prosegui il ciclo altrimenti esci
altro ciclo
for r = 1 .. s − 1
x ← x2 mod n anche qui cazzo è ? x2 sarà xquadro penso...
se x = 1 allora esci con numero composto
altrimenti se x = n − 1 allora ripeti il primo ciclo (ti conviene fare una funzione e indicare globale qualcosa)
esci con composto
esci con probabile primo


mah... sei sicuro che il testo ci sia tutto ?

[mikeb90]

la pagina da dove l'ho preso riportava la fonte come la pagina di wikipedia... ma ora che ci sono andato ed ho visto meglio, è lievemente diverso lo pseudocodice:

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 (2^s) ·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x^2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

PS: Si è un test sulla primalità, in quanto stabilisce che vi è una buona probabilità che quel numero sia primo, ma non dà la certezza al 100%, e quindi tutto il mondo informatico si basa su congetture e statistiche... xD
PPS: copia/incollando non ha preso le potenze come "a^d", ergo mi ha scritto "ad" ecc ecc, mea culpa D:

[bancodeipugni]

ah ecco

x= a^d mod n

x = x^2 mod n

x sarebbe da mettere globale per lasciare withnessloop come procedura, altrimenti è da passare x e da ritornare

resta comunque il mistero di chi sia s

[onbi]

http://it.wikipedia.org/wiki/Test_di_Miller-Rabin