altro problema!

Messaggioda nochipfritz » 09/08/2006, 09:41

Salve,
Vi sottopongo un serio problema che non riesco a risolvere.
Ho letto la definizione di test di primalità probabilistico....ed è la seguente :

Per un dato intero dispari n, definiamo test di primalità su n, un predicato Pr(n,a) tale che
1) n è composto se e solo se esiste a tale che 1<=a <n e Pr(n,a) =true
2) Pr(n,a) è computabile in tempo efficiente
3) Se n è composto, detto L(n) l'insieme degli 1<=a<n tali che Pr(n,a) = false allora #L(n) / (n-1) <= 1/2

Adesso, io ho 2 predicati e devo dimostrare che vale la prima proprietà per entrambi. In realtà mi basterebbe dimostrare che questi predicati sono equivalenti. Infatti come notate nell'immagine per un predicato la condizione vale (ho trovato la dimostrazione). Ma per l'altro ancora No. (le frecce indicano le implicazioni già dimostrate o per le quali ho già trovato le dimostrazioni). Il problema nasce dal fatto che un algoritmo (il test di primalità di miller rabin) è basato sul predicato Pr, ma l'idea da cui nasce l'algoritmo è quella del predicato Pr' (come affermato in un paper). Si sceglie Pr per motivi di efficienza. In qualche modo ci deve essere questo legame! Può essere sbaglio a decifrare i predicati???? e quindi...è ovvio che non riesco a dimostrare la mia ipotesi?

PS. $n-1 =m2^{\nu_0}$ con m dispari.

Immagine
nochipfritz
 

Torna a Statistica e probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 16 ospiti