Discussion :

[bestmomo]

Bonjour,

Dans le cadre d'une recherche de nombres premiers je me suis inspiré de cette page :

http://rosettacode.org/wiki/Miller-Rabin_primality_test

en utilisant le code C#.

Hors j'ai la surprise de ne trouver que quelques nombres :

5 - 7 - 11 - 13 - 17 - 97 - 193 - 257 - 641 - 5581
5953 - 7937 - 8681 - 8929 - 27905

Et en plus le dernier n'est même pas premier !

Est-ce que l'implémentation est incorrecte ? Je n'arrive pas à trouver la faille...

Merci...

[benDelphic]

il suffisait de lire c'est un teste probabiliste !!!

[bestmomo]

il suffisait de lire c'est un teste probabiliste !!!

Ca je l'avais lu mais étant donné le nombre de tests internes la probabilité d'avoir un faux premier est infime et je devrais par contre obtenir tous les premiers, ce qui est très très loin d'être le cas

[pseudocode]

Hors j'ai la surprise de ne trouver que quelques nombres :

5 - 7 - 11 - 13 - 17 - 97 - 193 - 257 - 641 - 5581
5953 - 7937 - 8681 - 8929 - 27905

Et en plus le dernier n'est même pas premier !

Est-ce que l'implémentation est incorrecte ? Je n'arrive pas à trouver la faille...

Que certains nombres ne soient pas premier, c'est normal (c'est un test probabiliste). Par contre, il ne devrait pas en manquer.

[Jean Dumoncel]

Salut,

le code en python semble fonctionner (pas tous vérifié mais la liste est beaucoup plus longue que celle que tu trouves et 27905 ne fait pas parti des résultats trouvés).

Vérifie le code c#, ou refait le code à partir de l'algorithme, il n'est pas très compliqué.

[bestmomo]

Merci pour les réponses, j'ai effectivement réécrit le code en partant de l'algo proposé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
        bool isPrime(int n, int k)
        {
            if (n == 2) return true; 
            else if (n < 2 || n % 2 == 0) return false;
            int d = n - 1;
            int s = 0;
            while (d % 2 == 0)
            {
                d /= 2;
                s++;
            }
            while (k-- > 0)
            {
                int a = new Random().Next(n - 3) + 2;
                int x = (int)((Math.Pow((double)a, (double)d))) % n;
                if (x != 1 && x != n - 1)
                {
                    for (int r = 1; r < s; r++)
                    {
                        x = (x * x) % n;
                        if (x == 1) return false;
                        if (x == n - 1) break;
                    }
                    if(x != n - 1)return false;
                }
            }
            return true;
        }

Mais je continue à ne pas avoir tous les premiers listés. Je fais un test des nombres jusqu'à 10000 et j'obtiens ça (avec k = 40) :

3
5
7
11
13
17
19
29
41
49
97
193
257
641
769
5581
5953
7937
8681
8929

Mais j'ai peut-être un bug dans mon code

[pseudocode]

Cette ligne là :

int x = (int)((Math.Pow((double)a, (double)d))) % n;

provoque un dépassement de capacité et de précision. Il vaut mieux effectuer le calcul par exponentiation binaire.

int x = modpow(a,d,n)

(exemple de code en java)

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
int modpow(int base, int exp, int m) {
	int result = 1;
	while (exp > 0) {
		if ((exp & 1) > 0)
			result = (result * base) % m;
		exp >>= 1;
		base = (base * base) % m;
	}
	return result;
}

[bestmomo]

Cette ligne là :



provoque un dépassement de capacité et de précision. Il vaut mieux effectuer le calcul par exponentiation binaire.



(exemple de code en java)

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
int modpow(int base, int exp, int m) {
	int result = 1;
	while (exp > 0) {
		if ((exp & 1) > 0)
			result = (result * base) % m;
		exp >>= 1;
		base = (base * base) % m;
	}
	return result;
}

Merci !

Cette ligne ne me plaisait pas vraiment mais je ne pensais pas qu'elle créait le problème

[pseudocode]

Merci !

Cette ligne ne me plaisait pas vraiment mais je ne pensais pas qu'elle créait le problème

Faire des calculs en virgule flottante au milieu de calculs sur les entiers, ca se termine généralement par ce genre de problème. :/

[bestmomo]

Faire des calculs en virgule flottante au milieu de calculs sur les entiers, ca se termine généralement par ce genre de problème. :/

Oui effectivement, je serai plus attentif à l'avenir. Il est quand même malheureux de retrouver du code aussi détestable sur une page wiki.

[pseudocode]

Oui effectivement, je serai plus attentif à l'avenir. Il est quand même malheureux de retrouver du code aussi détestable sur une page wiki.

c'est une page "rosettacode". Pas une page "wikipedia".