Test de primalité de Lucas

Fournissez un entier impair n, un témoin de Lucas proposé et la factorisation première complète de n moins un. Le calculateur valide la factorisation elle-même, évalue les puissances modulaires et les plus grands communs diviseurs requis, puis ne certifie n que si toutes les conditions du théorème de Lucas sont satisfaites. Les chaînes décimales conservent les entiers exacts, y compris au-delà de la plage numérique sûre habituelle de JavaScript.

Préparez un certificat complet

Commencez par l’entier impair que vous souhaitez certifier et factorisez entièrement n moins un. Saisissez n et chaque facteur premier sous forme de chaîne décimale canonique, car les chaînes préservent les valeurs exactes jusqu’à la limite de 64 bits. Chaque facteur apparaît une seule fois avec son exposant positif. Par exemple, pour n = 29, n moins un = 28 = 2 au carré fois 7 : la liste contient donc 2 avec l’exposant 2 et 7 avec l’exposant 1. Vous devez également fournir une base a telle que 1 < a < n. Cette base est le témoin de Lucas proposé. Le vérificateur exige volontairement ce témoin au lieu de le rechercher : la vérification d’un certificat est rapide, bornée et reproductible, tandis qu’une recherche peut durer plus ou moins longtemps selon l’entrée. Si vous ne disposez pas encore d’un témoin, essayez de petites bases avec un outil distinct consacré aux racines primitives, puis soumettez le certificat obtenu. Les espaces, signes, zéros initiaux, notations à virgule flottante, nombres premiers dupliqués, facteurs composés et facteurs manquants sont rejetés plutôt que normalisés silencieusement, ce qui rend le certificat adapté aux journaux d’audit et aux processus automatisés.

Comprenez les deux conditions de Lucas

Le premier calcul vérifie que a élevé à n moins un est congru à 1 modulo n. Il s’agit de la condition familière de Fermat, mais elle ne suffit pas à établir la primalité, car des pseudo-premiers peuvent la satisfaire. La seconde étape, décisive, utilise chaque nombre premier distinct q divisant n moins un. Pour chaque q, le vérificateur calcule a élevé à (n moins un) divisé par q modulo n, retranche un et vérifie que le résultat a pour plus grand commun diviseur 1 avec n. La réussite de tous ces contrôles prouve que l’ordre multiplicatif de a modulo n vaut exactement n moins un. Un élément modulo n ne peut avoir cet ordre que si n est premier : c’est le cœur du théorème de Lucas. Les contrôles renvoyés présentent le résidu modulaire et le plus grand commun diviseur pour chaque q distinct, tandis que l’exposant reste visible dans la factorisation validée. L’exponentiation modulaire emploie des carrés successifs et une arithmétique BigInt exacte ; le calcul ne dépend donc jamais d’un arrondi flottant, de bases aléatoires, d’un service réseau ou d’un niveau de confiance probabiliste.

Interprétez les échecs et le résultat positif

Une réponse positive constitue le résultat d’un certificat de primalité, et non une simple indication de nombre probablement premier. Elle répète n, identifie le témoin accepté, fournit le résidu de Fermat et énumère un contrôle réussi du plus grand commun diviseur pour chaque facteur distinct de n moins un. Conservez l’entrée d’origine avec cette réponse lorsqu’un autre système doit reproduire la preuve. Les échecs sont volontairement précis. Si les puissances des facteurs ne donnent pas exactement n moins un, la factorisation est incomplète ou erronée. Si un facteur indiqué est composé, ou si le même nombre premier apparaît deux fois, la factorisation est mal formée même lorsque son produit brut coïncide. L’échec d’une condition modulaire signifie que la base fournie n’est pas un témoin de Lucas ; il ne permet pas à lui seul de distinguer un n composé d’un nombre premier associé à une base inadéquate. Essayez un autre témoin mathématiquement justifié si la primalité reste attendue. Les entrées sont limitées aux entiers impairs de 3 à 2^64 moins 1, ce qui permet de valider de façon déterministe les facteurs premiers indiqués avant d’évaluer le certificat. Le tarif de l’API est de $0.002 par requête.