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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| /*
* fait passer le test de miller rabbin a la variable
* <a href="http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin" target="_blank">http://fr.wikipedia.org/wiki/Test_de...e_Miller-Rabin</a>
*/
bool encrypt::miller_rabbin(long n) //n doit toujours etre pair
{
long d;
d = n -1;
long s;
s = 0;
while ( d % 2 == 0 ) {
d = x/2;
s++;
}
//arrivé ici, on a : n - 1 = 2^s * d
//maintenant, on va tester k fois si le nombre est premier
int k = 10;
int aleatoire;
long r;
for (i = 0; i < k; i++) {
//on prend un nombre aléatoire compris entre 1 et var-1
aleatoire = rand() % ( n - 1 );
if ( pow(aleatoire, d) % n != 1 )
return false;
for (r = 0; r < s; r++) {
if ( pox(aleatoire, ( 2 * r * d ) ) % n != -1)
return false;
}
}
//si le chiffre a passé tous les tests, alors i l est probablement premier.
return true;
}
/*
* fait passer le test de primalitée de fermat
* <a href="http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Fermat" target="_blank">http://fr.wikipedia.org/wiki/Test_de...3%A9_de_Fermat</a>
*/
bool encrypt::Fermat(long n)
{
int tabPrem[4];
tabPrem[0] = 1;
tabPrem[1] = pow(2, n - 1);
tabPrem[2] = pow(3, n - 1);
tabPrem[3] = pow(5, n - 1);
tabPrem[4] = pow(7, n - 1);
int i, j;
int x;
for (i = 0; i < 5; i++) { // on parcouir le tableau tabPrem
x = 0;
while ( tabPrem[i] > x ) {
if ( tabPrem[i] == x*n ) {
break;
x++;
}
if ( x != 1 )
return false;
}
//si le chiffre a passé tous les tests, alors on peut renvoyer vrai => il est probablement premier.
return true;
} |
