Factorisation des entiers : étude des grilles de Carrissan ?

2nis

Bonjour

Pardon pour le titre qui ne veut rien dire, sauf pour moi (sauf coïncidence). Mais comme je ne sais pas comment ça s'appelle, j'ai dû inventer un nom.

La machine des frères Carissan ou "machine à congruences" est une machine qui permet la factorisation des entiers en utilisant la méthode de Fermat : on cherche à factoriser le nombre Z en cherchant les nombres A et B tels que Z = A² - B². Les nombres A et B modulo un nombre premier ne peuvent avoir que quelques valeurs. En prenant une base de nombre premiers suffisamment grande par rapport à Z et en recherchant séquentiellement ceux qui répondent aux critères, on trouve un nombre qui est presque certainement celui qui correspond à une différence de carrés, et donc on réussit à factoriser Z.

Ce que j'appelle "Grille de Carrissan", c'est exactement la même chose sauf qu'au lieu d'être sur des cercles, c'est présenté sur une grille rectangulaire. Voici par exemple la grille du nombre 1271 sur la base de nombre premiers {3, 5, 7, 11, 13, 17} :

On voit que la grille "sonne" (toujours l'analogie avec la machine à congruences) pour le nombre 5, et effectivement 1271 = 36² - 5². On a donc trouvé que 1271 = (36 - 5) * (36 + 5).

Trouver un nombre qui sonne n'est pas dur, toute la difficulté est de trouver le premier. D'où l'intérêt de comprendre comment ces nombres s'organisent. L'idéal serait de les avoir dans l'ordre, ou bien, à partir d'un nombre connu, d'en avoir un plus petit.

Je m'intéresse donc à ces grilles, et j'ai trouvé quelques propriétés intéressantes. J'aimerais savoir :

1. Comment s'appellent ces grilles, si elles ont un nom. J'ai cherché sur Google, mais chercher un truc dont on ne connait pas le nom, ce n'est pas facile.
2. Est-ce qu'il existe déjà des études, des théorèmes, quelque chose sur ces grilles ?

Merci pour vos réponses

2nis

On dit généralement que, sur un forum, si une question n'a pas de réponse comme la mienne, c'est qu'elle est mal posée ou pas claire. Je vais donc tenter de clarifier un peu les choses. Ne vous inquiétez pas, je ne remonterai plus le sujet si je n'ai toujours pas de réponse.

Sur la construction de la grille
Bien que que la machine de Carissan soit déjà très documentée dans une multitude d'articles, je vais réexpliquer le principe : soit Z = X * Y = A² - B². on cherche à connaitre X, Y, A ou B (en connaitre un seul suffit à calculer les autres). Modulo un nombre (en général premier mais pas nécessairement), les nombres A et B ne peuvent prendre que quelques valeurs. Voici par exemple les différences des résidus quadratiques de A (en abscisse) moins B (en ordonnée) modulo 5 :


Dans notre exemple, 1271 est congru à 1 modulo 5. On voit qu'il n'y a que quelques valeurs qui peuvent donner 1. Pour A, les seules valeurs sont 0,1 et 4, pour B 0, 2 et 3 (grille que j'ai donné en exemple plus haut). Dans la colonne du 5, on met des "plots" sur les nombres 0, 2, 3 puis 0 + 5, 2 + 5, 3 + 5 et ainsi de suite (dans la machine de Carissan, ce sont des disques qui tournent donc il n'y a pas à répéter). On fait pareil pour chaque nombre de la base. La grille "sonne" lorsque les plots sont alignés, c'est à dire lorsqu'on a une ligne complète.

Sur l'utilité de la grille
Connaitre le premier nombre qui sonne avec une base de nombres premiers suffisamment grande permet presque à coup sûr de factoriser Z, chose qu'on ne sait pas faire actuellement (ou très difficilement) si Z est très grand.

Sur ce que je cherche
Je cherche les propriétés de ces grilles.

L'une des propriétés évidentes est qu'elles sont symétriques verticalement. Si on nomme P le produit des nombres de la base, la ligne P - N est égale à la ligne N.

Une autre de ces propriétés est que les grilles A et B du nombre P - Z sont égales aux grilles B et A du nombre Z. On pourrait donc penser que factoriser P - Z permettrait de trouver les nombres A et B, et donc de factoriser Z (parfois il est plus facile de factoriser un grand nombre qui a certaines propriétés qu'un nombre plus petit). Mais si la grille sonne bien pour A et B, c'est un faux positif parce que P - Z est beaucoup plus grand que Z et que par conséquent la base est devenue trop petite. Les nombres A' et B' trouvés en factorisant P - Z n'ont aucun rapport avec A et B.

On peut aussi s'amuser à prendre une ligne sur deux (ou plus généralement une ligne sur N) d'une grille, on obtient une autre grille de Carissan. En fait on obtient la grille du nombre (Z * inverse modulo de N²) modulo P. Et inversement, en prenant une ligne sur N de la grille Z * N², on retombe sur la grille de Z.

Voici par exemple les trois grilles des nombres 1271 * 4 = 5084, 1271 (la même que plus haut), et 191759 (1271 * inverse modulo de 4 modulo P = 255255). On voit que chaque grille a une ligne sur deux de la grille précédente. Hélas, là aussi, rien qui permette de factoriser Z.


Donc je n'ai rien trouvé de révolutionnaire, mais ça donne une idée de ce que je cherche. Soit une transformation réversible qui permettrait de factoriser Z en factorisant un autre nombre (potentiellement plus facile à factoriser), soit de trouver un nombre différent de Z avec la même grille A ou B.
Je suppose que je ne suis pas le premier à rechercher dans cette voie, et les résultats que j'ai trouvé sont sans doute triviaux. Donc je cherche ce qui a été déjà été fait pour m'éviter de réinventer la roue et/ou explorer des nouvelles idées. Sans illusions, je sais que je ne trouverai probablement jamais une méthode pour factoriser n'importe quel nombre, voyez ça comme un passe-temps.
Merci.