Petit téorème de Fermat

[joel71]

Bonjour,

J’ai posé récemment une question dans la section informatique, celle-ci relève plus des mathématique.
Je ne suis pas mathématicien mais j’ai fait un petit algorithme basé sur le petit théorème de Fermat qui permet d’extraire les nombres premiers d’un nombre composé. Il n’est pas très rapide mais je peux actuellement avoir le résultat en quelques secondes d’un nombre composé de l’ordre de 10 ^ 7.
Je pourrais encore l’optimiser pour le rendre plus rapide et pour des nombres plus grands.
Je pensais avoir lu que le petit théorème de Fermat le permettait mais je n’en suis plus du tout sur. Donc ma question est : Sait-on déjà qu’avec le petit théorème de Fermat on peut trouver les produits d’un nombre composé ?
Merci de votre réponse.

[GaBuZoMeu]

Bonjour,
T'es-tu renseigné sur les nombres pseudo-premiers et les nombres de Carmichael ? https://fr.wikipedia.org/wiki/Nombre_pseudo-premier

[joel71]

Bonjour GaBuZoMeu,

Mon algorithme fournit systématiquement une réponse juste pour tous nombres composés que je rentre.
Voici des exemples que je viens de sortir après avoir lu ta réponse.
J’ai fais exprès de mettre deux séries de valeurs proches pour bien te faire voir que je n’ai pas fait l’inverse : choisir des nombres premiers et trouver facilement le nombre composé.

20539027 = 739 * 27793
20539033 = 37 * 555109
20539039 = 619 * 33181
20539061 = 73 * 281357
8300779 = 1693 * 4903
8300789 = 7 * 1185827
8300791 = 1949 * 4259
8300821 = 251 * 33071
Donc je renouvelle ma question. Sait-on déjà qu’avec le petit théorème de Fermat on peut trouver les produits d’un nombre composé ?

[GaBuZoMeu]

Que fait ton algorithme sur 561 ?

[joel71]

En général je ne teste pas les nombres divisible par 3. Je l'ai testé pour toi, il me dit que c'est un nombre premier, ça me parait normal puisqu'il utilise le petit théorème de Fermat. Il doit faire les mêmes erreurs sur les pseudo-premiers. J'ai remarqué également qu'il fait de rares erreurs sur d'autres nombres. Je n'ai pas dit qu'il était parfait, mais globalement et très souvent il donne la bonne réponse. Juste je voulais savoir si les mathématiciens disait ou pas que le petit théorème de Fermat est capable de décomposer les nombres composés.