Une famille d’algorithmes pour retrouver un rationnel p/q à partir de son image modulo un entier N ou d’un résidu modulaire approché, sous des bornes de taille sur numérateur et dénominateur, en utilisant généralement les fractions continues ou l’algorithme d’Euclide étendu.

Principe

Interpréter le résidu r ≡ p·q^{-1} (mod N) comme une approximation rationnelle r/N et calculer les convergents par fractions continues ou utiliser le pgcd étendu pour trouver des entiers petits (p,q) satisfaisant |p|≤P, 0

Démonstration

Exemple concret : N=97 et r ≡ 57, supposé correspondre à p/q avec q≤12. L’inverse modulaire de 12 est 89, 5·89≡57 (mod 97), donc r=57 se reconstruit en 5/12 par vérification par fraction‑continue/pgcd étendu sous la borne q≤12.

Mauvaise application

Tenter la reconstruction sans bornes valides (dénominateur trop grand) ou à partir de résidus obtenus avec un module N insuffisant, ce qui peut produire des candidats rationnels erronés ou plusieurs solutions spurielles.

Conséquence

Permet de récupérer des coefficients rationnels exacts depuis des calculs modulaires, effectuer des reconstructions modulaires en algorithmique symbolique et l’interpolation rationnelle, et éviter l’arithmétique sur grands entiers jusqu’à l’étape finale.

Inversion

La projection directe (réduire p/q modulo N pour obtenir r) est simple ; la reconstruction inverse requiert des contraintes de taille — inverser sans bornes entraîne des ambiguïtés plutôt qu’une récupération unique.

Limite

Nécessite des bornes explicites pour numérateur et dénominateur et un N choisi suffisamment grand pour éviter les collisions ; s’applique aux rationnels de taille modérée et aux modules entiers ; ne s’applique pas aux nombres irrationnels ou aux rationnels dont le dénominateur est arbitrairement grand par rapport à N.

Tension sémantique

Tension entre les classes d’équivalence modulo N (de nombreux rationnels peuvent donner le même résidu) et l’unicité obtenue seulement sous bornes de taille ; tension également entre l’approche par fractions continues et les méthodes basées sur les réseaux/pgcd étendu.

Synthèse

La reconstruction rationnelle unit arithmétique modulaire et approximation diophantienne : donné un résidu et des bornes de taille, les fractions continues ou le pgcd étendu produisent le rationnel petit unique dont l’image modulaire coïncide avec le résidu.