J'ai essayé de faire le petit théorème de Fermat et j'ai remarqué que cela ne fonctionnait pas en C alors je l'ai essayé en Python et cela a bien fonctionné.
Le petit théorème de Fermat
La réponse est censée me donner un 1 mais j'obtiens 13.
Exposant Python (fonctionnant)
double prime_num = pow(13,17-1) >665416609183179904 fmod(prime_num,17) = 13
Exposant C (ne fonctionne pas)
prime_num = 13**(17-1) >665416609183179841 prime_num%17 = 1
3 Réponses :
En C, la fonction pow () prend et renvoie des valeurs à virgule flottante double précision qui sont des approximations.
En Python, l'opérateur ** effectue l'opération en utilisant des entiers Python, augmentant en taille (mémoire utilisée pour contenir la valeur). Si vous obligiez les nombres à être des virgules flottantes avant l'opération, vous obtiendrez probablement les mêmes résultats.
En C, vous pouvez essayer d'écrire une fonction de puissance différente qui fonctionne avec uint64_t (unsigned long long) et voir si cela fonctionne.
Vous devez utiliser long long si vous voulez la précision. Le problème est qu'il n'y a pas de pow, c'est donc une simple multiplication.
long long n, val;
int ii;
n = 13LL;
val = n;
for (ii = 2; ii < 17; ++ii)
val *= n;
printf("%lld\n", val);
printf("%lld\n", val % 17LL);
Le problème était que j'aurais dû utiliser powl () qui renvoie un long double au lieu d'un double et j'aurais également dû utiliser fmodl () qui renvoie le reste qui a un type double long.
Code C fonctionnant
long double prime_num = powl(13,17-1); >665416609183179841 fmodl(primen_num,17); >1
Le
powde C est basé sur une virgule flottante, il y a donc une perte naturelle de précision dans le calcul. Pour les petits nombres, ce n'est pas perceptible, mais vous commencerez à le voir en plus grand nombre comme votre exemple.powf est pour les flotteurs, pow est pour les doubles mais je viens de découvrir la solution que j'aurais dû utiliser powl
Même le type primitif le plus long sera bien trop petit pour autre chose que les plus petits exemples RSA. Si vous renoncez à la fonction intégrée
pow ()et écrivez votre propre exponentiation modulaire , vous pouvez avoir des exemples beaucoup plus grands tout en n'utilisant que des types primitifs. Pour des exemples RSA de taille réelle, vous aurez besoin d'une bibliothèque bignum comme GMP .