Test de primalité de Proth avec témoin

Il vérifie d’abord que k est positif et impair, que n est positif et que k est inférieur à 2^n. Il calcule ensuite exactement la puissance modulaire requise. Une congruence réussie prouve que le nombre de Proth est premier ; un témoin négatif reste indécis, sauf s’il révèle un facteur.

Saisissez un véritable nombre de Proth et un témoin

Un nombre de Proth possède exactement la forme N = k × 2^n + 1, où k est un entier positif impair, n un entier positif et k est strictement inférieur à 2^n. Chaque condition est indispensable. Le calculateur reçoit k et le témoin sous forme de texte décimal afin de préserver les grandes valeurs sans arrondi en virgule flottante. Saisissez n comme entier compris entre 1 et 10,000. L’outil construit N au lieu de vous demander de le fournir séparément, ce qui empêche toute divergence entre le nombre annoncé et ses paramètres de définition. Il vérifie également que le témoin se situe strictement entre 1 et N. Une valeur paire de k, une valeur non positive ou un k supérieur ou égal à 2^n provoque un rejet explicite : le théorème n’est pas appliqué lorsque ses hypothèses ne sont pas satisfaites. Le nombre, l’exposant, le témoin et le résidu sont renvoyés sous forme de chaînes décimales lorsque nécessaire, afin que vous puissiez auditer le calcul et les copier dans un autre outil d’arithmétique exacte.

Comprenez précisément ce que prouve la congruence

Pour un nombre de Proth valide N, le théorème indique que N est premier s’il existe un entier a tel que a^((N−1)/2) soit congru à −1 modulo N. Le témoin fourni joue le rôle de a. Le calculateur évalue cette puissance modulaire par exponentiation binaire, sans construire au préalable l’immense puissance ordinaire. Dans le résultat, `residue` désigne le plus petit résidu non négatif et `passes_test` vaut true exactement lorsqu’il est égal à N−1, représentation modulaire de −1. Dans ce cas, `prime_proven` vaut true et le verdict est `prime` : sous les conditions de Proth déjà vérifiées, il s’agit d’un certificat déterministe, et non d’une simple indication de nombre probablement premier. La réponse fournit l’exposant exact (N−1)/2 afin que vous puissiez reproduire la congruence indépendamment. L’algorithme emploie uniquement des opérations entières, ne choisit aucun témoin au hasard et ne consulte ni table ni service distant. Une même entrée produit donc toujours le même résultat et expose toutes les valeurs importantes du théorème.

Interprétez correctement l’échec d’un témoin

Un témoin qui ne produit pas −1 ne démontre pas, à lui seul, que le nombre est composé. Il signifie seulement que ce témoin précis ne satisfait pas la condition suffisante du théorème de Proth. Le calculateur renvoie donc `inconclusive`, et non `composite`, lorsque le résidu diffère et que le témoin est premier avec N. Vous pouvez alors essayer un autre témoin choisi selon un critère mathématique ou employer une autre méthode déterministe de primalité. Une exception est utile : avant d’interpréter la congruence, l’outil calcule le plus grand commun diviseur du témoin et de N. Si cette valeur est un facteur propre, le verdict devient définitivement `composite` et le facteur est renvoyé. Cette distinction évite de transformer à tort un théorème à sens unique en test réciproque invalide. Elle facilite aussi l’automatisation : acceptez `prime` comme preuve, rejetez `composite` lorsqu’un facteur apparaît et dirigez `inconclusive` vers un autre test au lieu de le traiter silencieusement comme un échec définitif.