Bonjour,
Si p est un entier impair > 3. On prend c le carré impair immédiatement supérieur à p.
On prend i = (√c -1)/2.
On prend j = sup((c-p)/4), c'est l'entier supérieur ou égal à (c-p)/4.
On pose k = 1 si sup((c-p)/4) > (c-p)/4 et k = 0 sinon.
Si p est premier, on a alors: (c-p)^((i^2)+i-j) . (2i+1)^k congru à 1 ou à p-1 modulo p.
Pour p = 89 on a: c = 121; i = 5; c-p = 32; (c-p)/4 = 8 donc j = 8 et k = 0; (i^2)+i-j = 22; 2i+1 = 11
et on a: 32^22 . 11^0 = 1 mod(89)
Pour p = 87 on a: c = 121; i = 5; c-p = 34; (c-p)/4 = 8,5 donc j = 9 et k = 1; (i^2)+i-j = 21; 2i+1 = 11
et on a: 34^21 . 11^1 = 47 mod(87)
Je crois qu'en informatique les calculs modulo peuvent se faire rapidement. En partant d'un carré assez grand est-ce-que cet algorithme (s'il est juste) serait efficace pour trouver des nombres premiers? (s'il est congru à p-1 il est premier, s'il est congru à 1 il est "très probablement" premier).