Passa al tema normale
Questioni di statistica, calcolo delle probabilità, calcolo combinatorio

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

altro problema!

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
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.