Test de Miller-Rabin

[invited75582db]

Bonjour,

Quelqu'un peut-il me dire s'il est possible d'énumérer rapidement, sur un PC habituel, tous les nombres premiers jusqu'à 1 million en testant chaque nombre impair avec le test de Miller-Rabin ? Et en quel temps à peu près ?

Merci.
-----

[invite4ef352d8]

Salut !

j'ai pas essayer, (et j'ai pas de quoi essayer sous la main) mais je pense que oui sans aucun problème et ca prendrai pas enormement de temps (par contre je saurais pas dire si c'est de l'ordre de quelques secondes ou de une heure...)

ceci dit, si le but est de lister tous les nombres premier <n, les tester tous un par un avec Rabin Miller n'est pas la meilleur methode, les technique de crible (même le crible d'Erathostène) sont plus efficace. Rabin miller ca marche bien quand on veut tester si un nombre (tres grand) est premier.

[invited75582db]

Merci. Le problème avec Eratosthène est qu'il est limité, sur un PC moyen, aux environs de 1 million ... Après c'est très, très lent.

[invite4ef352d8]

certe, mais il existe des rafinement (le crible d'atkin par exemple, il y en à peut-etre d'autre) de cette algorithme qui doivent repousser un peu cette limite... enfin j'ai jammais trop essayer ce genre de choses non plus.

mais dans mes souvenir je n'avais aucun mal à génerer une liste de nombres premier inférieur à 1 million avec erathostène sous maple... donc en utilisant un language plus otpimisé on doit pouvoir atteindre la dizaine voir la centaine de millions sans trop de problème : la seul difficulté c'est l'occupation mémoire et un crible d'un million de nombres ca occupe à peine 1 Mo de mémoir non ?

[A voir en vidéo sur Futura]

[invite8c3c232e]

Bonjour,

J'ai un nombre premier constitué de 7 chiffres. Le test de Miller-Rabin me dit qu'il est probablement premier. En augmentant le nombre de tests à 35 000 000 il me dit pareil. Y a-t-il une valeur pour qu'il me réponde "oui il est premier" ou alors il ne donne qu'une seule réponse par nombre ?

[acx01b]

il y a les tests déterministes et les tests non-déterministes (ou probabilistes)

https://fr.wikipedia.org/wiki/Test_d...e_Miller-Rabin
Le test de primalité de Miller-Rabin est un test de primalité probabiliste

https://fr.wikipedia.org/wiki/Test_d...alit%C3%A9_AKS
le test de primalité AKS est un algorithme de preuve de primalité déterministe

[invite8c3c232e]

Je sais tout cela. Ma question est de savoir dans la pratique si le test fournit toujours la même réponse même en augmentant le nombre de tests pour un même nombre. J'utilise GMP.

[acx01b]

heu attends j'ai oublié de dire que Miller Rabin devient déterministe quand on teste racine de p nombres 'a' différents ou un truc comme ça

le test de fermat fonctionne sur le même principe : le petit théorème de Fermat est vrai pour tous les 'a' si et seulement si p est premier


si on ne teste pas tous les 'a' ça reste non déterministe

je ne vois pas ce que tu veux savoir d'autre

[acx01b]

ou c'est plus compliqué que ça avec le test de Miller Rabin :

https://fr.wikipedia.org/wiki/Test_d...e_Miller-Rabin
En supposant la véracité de l'hypothèse de Riemann généralisée, on peut prouver que, si toutes les valeurs de a comprises entre 1 et 2(log n)2 ont été testées et que n est encore « probablement premier », alors il est en fait assuré d'être premier. Ceci mène à un test de primalité déterministe qui possède un temps d'exécution de O((log n)4).

à voir avec le test de Fermat

[invite9dc7b526]

tiens, je viens de regarder par curiosité, sur mon ordi qui est très ordinaire, la méthode qui consiste à tester tous les diviseurs impairs jusqu'à la racine carrée du nombre prend entre 0.7 et 500 millisecondes pour un nombre de 7 chiffres (j'en ai testé 100 tirés dans la loi uniforme entre 1000000 et 9999999).

[gg0]

Bonjour.

Ceux-là se font à la main ! Avec une table de premiers inférieurs à 10000. Mais comment faire avec 100 ou 200 chiffres ? Il faudra multiplier tes temps par 10⁹⁷ ou 10¹⁹⁷. Ça devient long !

Cordialement.

[invite9dc7b526]

Ceux-là se font à la main ! Avec une table de premiers inférieurs à 10000.

même avec une table, il faut aimer faire des divisions à la main...

Mais comment faire avec 100 ou 200 chiffres ? Il faudra multiplier tes temps par 10⁹⁷ ou 10¹⁹⁷. Ça devient long !

bah oui. Mais pas si long il me semble. On ne cherche que jusqu'à la racine carrée du nombre. Par contre les divisions deviennent de plus en plus longues (comme le log du dividende?). Bref ça croît un peu moins vite que linéairement il me semble.

[gg0]

Fais-le seulement pour un nombre de 31 chiffres. Il faut tester jusqu'à environ 10¹⁶, au lieu de 10⁴ pour tes nombres de 7 chiffres, soit 1 000 000 000 000 fois plus longtemps sans tenir compte du temps de division.
0,7x1 000 000 000 000 millisecondes ça fait 700 000 000 s soit environ 8100 jours.
J'ai pris la valeur basse, car il y a moins fréquemment des premiers, mais si c'est un premier, ça va être jusqu'à 700 fois plus long (voire encore plus), et on dépasse les 15000 ans.

Effectivement, en fonction de la valeur de n, la croissance n'est pas linéaire. Mais ce qui compte, c'est la taille (il est facile de rajouter 2 ou 3 chiffres à n), et là la croissance est exponentielle.

Cordialement.

NB : "même avec une table, il faut aimer faire des divisions à la main..." les gens de ma génération ne disposaient pas de calculette. On calculait souvent plus vite de tête ou à la main que la plupart des jeunes actuels quand leur calculette est rangée au fond du cartable. Rappel : les calculs pour fabriquer la première bombe atomique ont été faits avant les ordinateurs.

[invite8c3c232e]

Quelqu'un peut-il me dire s'il est possible d'énumérer rapidement, sur un PC habituel, tous les nombres premiers jusqu'à 1 million en testant chaque nombre impair avec le test de Miller-Rabin ? Et en quel temps à peu près ?

J'ai testé Miller-Rabin avec uniquement des nombres premiers. Sur les 203 280 221 premiers nombres premiers (4 octets) le test Miller-Rabin (reps=25) annonce:

1 nombre compose
203 201 723 nombres probablement premiers
78 496 nombres premiers

Hum... oui bon il est probable (lol) d'améliorer le résultat en augmentant la valeur de reps MAIS... ce test a déjà pris plusieurs heures !

si le but est de lister tous les nombres premier <n, les tester tous un par un avec Rabin Miller n'est pas la meilleur methode, les technique de crible (même le crible d'Erathostène) sont plus efficace. Rabin miller ca marche bien quand on veut tester si un nombre (tres grand) est premier.

Je confirme que le crible est la méthode la plus efficace pour les petits nombres: moins d'une minute pour obtenir les 203 280 221 premiers nombres premiers (4 octets) !

Je veux bien croire que Miller-Rabin est efficace pour les grands nombres (sinon personne n'en aurait parlé) mais la question est de savoir à partir de quelle valeur de reps le résultat peut-il être considéré comme fiable. Allez prenons un cas concret, disons un nombre composé de 100 000 000 de chiffres, reps = ?

[acx01b]

MathMathMath : la répartition des nombres premiers n'est pas aléatoire, c'est déterministe. D'une certaine manière, tous les grands problèmes sur les nombres premiers, comme l'hypothèse de Riemann, consistent à savoir si cette répartition s'apparente à une répartition aléatoire.

De la même manière, la valeur de si est composé n'est pas aléatoire, donc dire qu'en testant beaucoup de différents la probabilité que soit premier augmente n'a pas beaucoup de sens : ce n'est pas probabiliste. Mais si on suppose que la valeur de est aléatoire et suit une loi uniforme sur alors pour chaque testé on divise la probabilité de se tromper par ...

Les nombres de Carmichael montrent bien que cette histoire de probabilités n'a pas vraiment de sens, mais comme ils sont très rares, finalement c'est bien ce qu'on fait quand on cherche un nombre probablement premier pour le cryptage RSA par exemple.

Le seul truc un peu rigoureux qu'on peut dire c'est qu'il existe vraiment une probabilité de se tromper quand on teste par exemple nombres différents sur un entier pris au hasard entre et , mais on ne connait pas cette probabilité.

Ce n'est pas ça que tu voulais savoir ?

[invite8c3c232e]

MathMathMath : la répartition des nombres premiers n'est pas aléatoire, c'est déterministe.

Entièrement d'accord, le crible d'Ératosthène le montre très bien.

Voici ce que dit la doc GMP sur la fonction Miller-Rabin.

The argument reps controls how many such tests are done; a higher value will reduce the
chances of a composite being returned as “probably prime”. 25 is a reasonable number; a
composite number will then be identified as a prime with a probability of less than 2−50.

D'où ma question de la valeur de reps pour les grands nombres à 100 000 000 chiffres.

Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers
which fail are known to be composite but those which pass might be prime or might be
composite. Only a few composites pass, hence those which pass are considered probably
prime.

Sauf qu'avec reps=25 le test a annoncé composé dans un cas alors que c'était bien un premier.

[acx01b]

Tu as compris mes messages ? Tu connais le petit théorème de Fermat ? Et le test de pseudo-primalité utilisant le petit théorème de Fermat ? Je n'ai pas vraiment l'impression.

Ton 'reps' c'est le nombre de testés.

C'est le du petit théorème de Fermat :


Pour voir si un nombre est (pseudo)premier, on prend des nombres et on teste si

Le test de Miller Rabin utilisant la même chose avec une petite subtilité en plus.

Sauf qu'avec reps=25 le test a annoncé composé dans un cas alors que c'était bien un premier.

Non impossible, à moins que le programme contienne des bugs