Caractérisation nombres premiers

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Rouvire
Membre Naturel
Messages: 30
Enregistré le: 02 Fév 2014, 16:16

Caractérisation nombres premiers

par Rouvire » 05 Mar 2017, 21:28

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).



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Caractérisation nombres premiers

par Ben314 » 05 Mar 2017, 23:15

Salut,
En fait, je comprend pas bien l'intérêt de tout ce mic-mac :

Si je comprend bien,

Puis tu calcule modulo .

-Bon, déjà, que soit premier ou pas, le du sert évidement à rien vu qu'on travaille modulo (et ça accélère en rien les calculs vu que de toute façon vu la taille de l'exposant le nombre qu'on manipule va très très rapidement dépasser , quelque soit le nombre "exposé").
Donc en fait qui déjà à le bon gout d'être lisible (et c'est évidement kif-kif au niveau calcul vu que c'est exactement la même chose...)

Arrivé à ce point, effectivement, si est premier, le petit théorème de Fermat te dit que donc que (selon que est ou pas un carré modulo ).

Mais par contre, même lorsqu'on a , ça ne prouve pas la primalité de : Par exemple, pour on a et
(De même, pour , le nombre donne un contre exemple).
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 8 invités

cron

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite