Test de primalité avec le théorème de Wilson

[ast]

Bonjour

Sur la page wikipédia du théorème de Wilson:

https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Wilson#Informatique

Il y a ce programme Python de test de primalité:

----------------------------------------------
import math

def isPrime(n):
if n == 4: return False
return bool(math.factorial(n>>1)%n)
----------------------------------------------

qui manifestement ne fonctionne pas correctement puisqu'il
répond True pour n = 9

L'auteur parle "d'augmenter la vitesse de calcul" mais je
ne comprends pas ce qu'il a voulu faire.

Si quelqu'un a une idée ?

[Samuel DEVULDER]

Le 28/07/2021 à 09:49, ast a écrit :

> ----------------------------------------------
> import math
>
> def isPrime(n):
>     if n == 4: return False
>     return bool(math.factorial(n>>1)%n)
> ----------------------------------------------
>
> qui manifestement ne fonctionne pas correctement puisqu'il
> répond True pour n = 9

Ben oui d'une part n==4 n'est pas une exception au théorème (si au moins
ca avait été une congruence à 0 modulo 4, ca aurait plus de sens), et
d'autre part c'est (n-1)! et pas (n>>1)! = int(n/2)! qu'il faut utiliser.

Ce code est complètement à la ramasse. Je ne me sens pas le courage
d'aller modifier la wiki, mais honte à celui qui a écrit ce code sans
donner de justifications. Il est totalement faux et d'ailleurs il ne
figure même pas dans la page anglaise du même théorème.

> L'auteur parle "d'augmenter la vitesse de calcul" mais je
> ne comprends pas ce qu'il a voulu faire.

Il dit que les factorielles sont couteuses. C'est vrai, mais sa version
"optimisée" avec le n>>1 (soit int(n/2)) utilise encore une factorielle.
C'est du grand n'importe quoi vu là comme ca.

Par contre il y a moyen d'éviter les grands nombres en calculant la
factorielle modulo n de bout en bout (soit n produits + modulo), ce qui
reste lent pour un test de primalité où l'on teste des nombres "n" à
plusieurs milliers de chiffres.

sam.

[Samuel DEVULDER]

Le 28/07/2021 à 09:49, ast a écrit :

> ----------------------------------------------
> import math
>
> def isPrime(n):
>     if n == 4: return False
>     return bool(math.factorial(n>>1)%n)
> ----------------------------------------------
>
> qui manifestement ne fonctionne pas correctement puisqu'il
> répond True pour n = 9

Effectivement:
n>>1 = int(n/2) = 4
4! = 12
12 modulo 9 = 3 qui n'est pas nul
L'algo retourne "vrai": 9 est premier !

Cet algo est donc définitivement faux.

Mais, avec n-1 à la place de n>>1, on a n-1 = 8, 8! = 40320, et 40320
modulo 9 = 0. L'algo dit que 9 n'est pas premier. L'application du
théorème de Wilson marche avec (n-1) et pas un truc en n>>1.

Cet algo complètement faux date du 28 juillet 2018 par FLBPériat
https://fr.wikipedia.org/w/index.php?title=Th%C3%A9or%C3%A8me_de_Wilson&diff=prev&oldid=153360821

sam.

[Olivier Miakinen]

Bonjour,

Le 28/07/2021 09:49, ast a écrit :
>
> Sur la page wikipédia du théorème de Wilson:
>
> https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Wilson#Informatique
>
> Il y a ce programme Python de test de primalité:
>

> [...]

>
> qui manifestement ne fonctionne pas correctement puisqu'il
> répond True pour n = 9

Il en est question dans la page de discussions :
https://fr.wikipedia.org/wiki/Discussion:Th%C3%A9or%C3%A8me_de_Wilson#Programme_informatique

<cit.>
Je ne suis pas du tout convaincu de la pertinence de ce programme dans cette
section (il n’est pas vraiment en lien avec le théorème de Wilson). [...] le
programme est faux pour n=9. Et on peut montrer assez facilement qu’il est
correct en dehors de cette valeur (mais sans utiliser le théorème de Wilson).
</cit.>

--
Olivier Miakinen

[Samuel DEVULDER]

Le 28/07/2021 à 10:57, Samuel DEVULDER a écrit :

> Mais, avec n-1 à la place de n>>1, on a n-1 = 8, 8! = 40320, et 40320
> modulo 9 = 0. L'algo dit que 9 n'est pas premier. L'application du
> théorème de Wilson marche avec (n-1) et pas un truc en n>>1.

Heu oui enfin c'est pas la même algo avec juste "n-1" à la place ce
"n>>1", il faut aussi ajouter 1:
return (math.factorial(n-1) + 1 ) % n == 0

Le "factorial % n" peut être calculé par une boucle for où l'on réalise
le "% n" à chaque tour de sorte à ne travailler que sur des nombres du
même ordre de grandeur que "n". Par contre il faut faire "n" tours ce
qui reste couteux.

sam (pas bien éveillé)

[Samuel DEVULDER]

> Il en est question dans la page de discussions :
> https://fr.wikipedia.org/wiki/Discussion:Th%C3%A9or%C3%A8me_de_Wilson#Programme_informatique
>
> <cit.>
> Je ne suis pas du tout convaincu de la pertinence de ce programme dans cette
> section (il n’est pas vraiment en lien avec le théorème de Wilson). [...] le
> programme est faux pour n=9. Et on peut montrer assez facilement qu’il est
> correct en dehors de cette valeur (mais sans utiliser le théorème de Wilson).
> </cit.>
>

Punaise je ne suis pas bien (r)éveillé moi. Donc le test à 4 devrait
être à 9 et l'algo serait bon...

Bref oui dans tous les cas comme il n'est pas justifié, même avec le
test à 9 cet algo est hors sujet car non relatif à Wilson. Merci d'avoir
trouvé le bon passage dans la discussion.

sam (<== reparti faire la sieste)

[Olivier Miakinen]

Le 28/07/2021 10:58, Olivier Miakinen j'écrivais :

>
> Il en est question dans la page de discussions :
> https://fr.wikipedia.org/wiki/Discussion:Th%C3%A9or%C3%A8me_de_Wilson#Programme_informatique
>
> <cit.>
> Je ne suis pas du tout convaincu de la pertinence de ce programme dans cette
> section (il n’est pas vraiment en lien avec le théorème de Wilson). [...] le
> programme est faux pour n=9. Et on peut montrer assez facilement qu’il est
> correct en dehors de cette valeur (mais sans utiliser le théorème de Wilson).
> </cit.>

Je viens d'ailleurs de corriger une erreur dans la démonstration du fait que ce
programme est vrai si n > 9. Il n'empêche que ça n'a strictement rien rien à
voir avec le théorème de Wilson. Du coup je vais le supprimer de la page
principale.


--
Olivier Miakinen

[Samuel DEVULDER]

Le 28/07/2021 à 10:57, Samuel DEVULDER a écrit :

>     4! = 12

Erm... 24

sam ==> Zero pointé :(

[Olivier Miakinen]

Le 28/07/2021 09:49, ast a écrit :
>

> Sur la page wikipédia du théorème de Wilson:
>
> https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Wilson#Informatique
>

> [...]

>
> Si quelqu'un a une idée ?

En conclusion, c'est un test qui fonctionne pour tout n différent de 4 et 9
(qui sont les deux plus petits carrés de nombres premiers) mais qui n'avait
rien à faire sur une page consacrée au théorème de Wilson car ça n'a rien à
voir.

Je viens de le supprimer de la page.

Merci pour ta vigilance, ast.


--
Olivier Miakinen