Test de primalité de Miller & Rabbin. Qui peut démontrer la probabilité d'erreur?

[zoela]

Bonjour, voilà le théorème:
Si $n$ est un entier premier, l'algorithme de Miller Rabbin afiche "premier" ou "pseudopremier". Dans le cas contraire, il affiche "Composé" avec une probabilité plus grande que $1-4^k$.

Merci d'avance

[mtschoon]

@zoela , bonjour,

La politesse n'est pas une option.

Les scans d'énoncés ne sont pas autorisés.

Il faut écrire ton énoncé (à la main ).

[zoela]

Ce message a été supprimé !

[mtschoon]

Rebonjour @zoela
Pour plus de carté, je t'indique les consignes avant de poster :
https://forum.mathforu.com/topic/1378/stop-lire-ce-sujet-tu-devras-avant-de-poster-ton-message

Merci d'avoir écrit ton énoncé.

J'espère que quelqu'un te répondra ; personnellement, je ne connais pas Miller & Rabbin.

Remarque : quelque chose est très étrange dans ce que tu écris...

@zoela a dit dans Test de primalité de Miller & Rabbin. Qui peut démontrer la probabilité d'erreur? :

voilà le théorème:
Si $n$ est un entier premier, l'algorithme de Miller Rabbin afiche "premier" ou "pseudopremier". Dans le cas contraire, il affiche "Composé" avec une probabilité plus grande que $1-4^k$.

Tu parles d'un probabilité supérieure à $1-4^k$

Toute probabilité est comprise entre 0 et 1.
Cela n' a donc de sens que pour $0\le 4^k\le 1$ Bizarre, bizarre....
Tu as peut-être écrit $4^k$ au lieu de $\frac{1}{4^k}$ ?

[mtschoon]

@zoela , un lien ici , à consulter éventuellement :
http://defeo.lu/in420/DM3 - Test de Miller-Rabin

La probabilité d’identifier erronément un nombre composé comme étant "premier" ou "pseudopremier" est inférieure ou égale à $\frac{1}{4^k}$

( C'est la probabilité de l'évènement contaire qui , lui, a une probabilité supérieure ou égale à $1-\frac{1}{4^k}$ )