Tests de primalité comparés

[nodjim]

Bonjour à tous.
On sait, depuis Fermat, que pour tout p premier, a^p=a modulo p, si a premier avec p. Trouver, en a^p, une valeur autre que a est une certitude pour établir la non primalité d'un entier. Mais pas l'inverse: Certains nombres composés n donnent aussi "a" comme résultat de a^n modulo n. Pour a=2, on dénombre plus de 30 nombres faussement premiers dans les 16384 premiers entiers.
En comparaison avec la suite de Fibonacci modulo n, celle ci est nettement plus performante, puisqu'on n'en dénombre moins d'une dizaine faussement premiers dans le même intervalle (un nombre premier p donne comme résultat: Fp=+-1 modulo p,et F(p-1) ou F(p+1)=0 modulo p, sauf pour 5) Curieusement, ce ne sont pas les mêmes nombres. D'ailleurs, aucun des nombres faussement premiers par le test Fibonacci n'est un nombre de Carmichael. Je rappelle que les nombres de Carmichael nc sont les nombres composés qui donnent comme résultat "a" pour a^nc modulo nc, quel que soit a premier avec nc, donc qui se comportent comme des nombres premiers.
Est ce à dire que le test de primalité Fibonacci ne peut donner aucun nombre faussement premier identique à ceux du test 2^n=2 ?
C'est là la question.
Quel est le plus petit nombre composé n faussement premier à la fois avec le test Fibonacci et le test 2^n=2 ?

[Doraki]

271*811 = 219781 ?

[nodjim]

C'est OK.
Ce nombre étant relativement petit, sans aller plus loin, ça donne une idée sur la fréquence d'arrivée d'un tel événement: Le double filtre Fibo croisé avec 2^n n'est pas très efficace. il en existe des probabilistes meilleurs, celui de Rabin-Miller par exemple, utilisé pour trouver les grands "fort-probablement" premiers du cryptage RSA.

[Reiffuppy]

Èíòåðåñíî êàêèå áû áûëè ãðàôèêè åñëè áû ñâåðõó áûëî íàïèñàíî, íàïðèìåð : "Performance Tests for IE7" ?