Crible Quadratique - résolution de la matrice
dans Arithmétique
Bonjour.
Dans l’article de Wikipédia consacré au crible quadratique https://fr.wikipedia.org/wiki/Crible_quadratique il est donné un exemple de matrice et ce commentaire :
On aurait pu utiliser d'autres congruences de carrés déduites de cette matrice. Par exemple en combinant la deuxième ligne et la quatrième (puisque leur somme est paire). »
Ma question : comment faire pour retrouver une congruence de carrés dans une matrice bien plus grande, comme celle ci-dessous :
847169 x 781799 = 662315877031, avec 1266984; 841664; 831341; 1125255; 1047566.
J’ai retrouvé les lignes de cette matrice dont l’addition modulo 2 donne 0 en procédant ainsi :
En prenant la dernière ligne comme référence, j’ai cherché dans la matrice la ligne dont l’addition avec la dernière ligne permettait de se rapprocher le plus possible de 0. J’ai donc retenu la ligne 3 (qui représente 841664 ici) et j’ai additionné ces deux lignes. J’ai répété le processus de recherche de la plus faible addition sur les autres lignes restantes dans la matrice en additionnant la ligne nouvellement retenue avec les autres déjà retenues. Jusqu’à obtenir la solution.
Existe-t-il un procédé plus rigoureux ?
Connaissez-vous des liens qui parlent de ce sujet ?
Merci d’avance.
Dans l’article de Wikipédia consacré au crible quadratique https://fr.wikipedia.org/wiki/Crible_quadratique il est donné un exemple de matrice et ce commentaire :
0 5 0 0 0 1 0 0 0 4 0 1 0 0 0 1 0 4 2 0 = 0 0 0 0 ( MOD 2 ) 0 10 0 1 0 0 0 1 0 3 4 0 0 1 0 0« La troisième ligne (qui correspond à (z, y) = (9, 784)) est nulle modulo 2 donc est déjà une congruence de carrés, qu'on peut utiliser pour factoriser n : modulo 1817.
On aurait pu utiliser d'autres congruences de carrés déduites de cette matrice. Par exemple en combinant la deuxième ligne et la quatrième (puisque leur somme est paire). »
Ma question : comment faire pour retrouver une congruence de carrés dans une matrice bien plus grande, comme celle ci-dessous :
[b]x 2 3 5 7 13 19 29 31 41 53 83 97[/b] 814091 1 1 1 1 0 0 0 0 0 0 0 1 831341 1 0 1 0 1 0 0 0 1 0 0 0 841664 0 0 1 1 0 0 1 1 1 0 0 0 853841 1 1 0 1 0 0 0 0 1 0 0 0 909151 1 1 1 1 0 1 0 1 0 0 0 1 964591 1 0 1 1 1 1 0 0 1 0 0 0 1047566 0 0 0 1 0 1 0 0 0 0 0 0 1050604 0 1 1 1 1 1 0 1 0 0 0 0 1092347 1 1 0 0 0 1 0 0 0 0 0 1 1125255 1 0 0 1 0 1 0 0 0 0 0 0 1198291 1 1 0 0 0 1 0 0 1 0 0 0 1266984 0 0 0 1 1 0 1 1 0 0 0 0Soit la solution :
847169 x 781799 = 662315877031, avec 1266984; 841664; 831341; 1125255; 1047566.
J’ai retrouvé les lignes de cette matrice dont l’addition modulo 2 donne 0 en procédant ainsi :
En prenant la dernière ligne comme référence, j’ai cherché dans la matrice la ligne dont l’addition avec la dernière ligne permettait de se rapprocher le plus possible de 0. J’ai donc retenu la ligne 3 (qui représente 841664 ici) et j’ai additionné ces deux lignes. J’ai répété le processus de recherche de la plus faible addition sur les autres lignes restantes dans la matrice en additionnant la ligne nouvellement retenue avec les autres déjà retenues. Jusqu’à obtenir la solution.
1266984 0 0 0 1 1 0 1 1 0 0 0 0 841664 0 0 1 1 0 0 1 1 1 0 0 0 [b]Mod 2 0 0 1 0 1 0 0 0 1 0 0 0[/b] 831341 1 0 1 0 1 0 0 0 1 0 0 0 [b]Mod 2 1 0 0 0 0 0 0 0 0 0 0 0[/b] 1125255 1 0 0 1 0 1 0 0 0 0 0 0 [b]Mod 2 0 0 0 1 0 1 0 0 0 0 0 0[/b] 1047566 0 0 0 1 0 1 0 0 0 0 0 0 [b]Mod 2 0 0 0 0 0 0 0 0 0 0 0 0[/b]Je ne suis pas sûr que ce procédé permette de toujours trouver la solution...
Existe-t-il un procédé plus rigoureux ?
Connaissez-vous des liens qui parlent de ce sujet ?
Merci d’avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si je lis bien (en lisant le renvoi) si on part de la matrice $M$ qui a ses coefficients qui sont $0$ ou $1$ il faut considérer la matrice transposée $t_M$ et déterminer son noyau (ou au moins un vecteur non nul de ce noyau). Cela peut se faire par la méthode du pivot de Gauss.
En espérant ne pas avoir écrit trop d'énormités.
Dans l'exemple qui est donné dans la version anglaise cela conduit à résoudre, sauf erreur, le système d'équations:
$y+z=0$ et $x+z=0$ dans le corps à deux éléments $\mathbb{F}_2$.
PS:
En fait, cette histoire de transposée on s'en cogne on doit résoudre un système linéaire homogène: $v.M=0$ où $v$ est le vecteur ligne des inconnues (les coefficients qu'on cherche pour notre combinaison linéaire des lignes de la matrice)
Je pense qu'il y a une incohérence dans les deux derniers coefficients de la première colonne, à savoir $b = 1198291$ et $b' = 1266984$
Pour le nombre $N = 662315877031$ que tu as donné, ce n'est pas vrai que $b^2 \bmod N$ se factorise sur les premiers de la ligne du haut. Idem pour le coefficient $b'$.
@Claude Quitté, les chiffres repris dans la 1ère colonne sont les valeurs brutes.
11982912 - 662315877031 = 773585443650 qui se décompose en 2 x 3 x 5 x 5 x 19 x 31 x 31 x 41 x 83 x 83
12669842 - 662315877031 = 942932579225 qui se décompose en 5 x 5 x 7 x 7 x 7 x 13 x 29 x 31 x 97 x 97
La décomposition est transposée en modulo 2 pour remplir la matrice, où j'ai filtré les colonnes des nombres premiers dont la somme donne 0 (par exemple 11, mais j'ai oublié 53 et 83 dans mon messages, deux colonnes qui peuvent aussi être filtrées).
@Fin de partie, je pense que tu as compris le problème. Ma question est de savoir s'il existe un "pseudo code" pour résoudre le problème et trouver les lignes dont l'addition modulo 2 donne 0 ?
Algorithme du pivot de Gauss.
https://fr.wikipedia.org/wiki/Élimination_de_Gauss-Jordan
Je ne pense pas que ce soit ce qui est utilisé dans la pratique. Le système à résoudre typiquement a des milliers de lignes. Il y a beaucoup de $0$ en coefficients il doit y avoir des méthodes plus performantes.
J'ai pigé (disons un traitement spécial pour les deux derniers coefficients i.e. $b^2 - N$ versus $b^2 \bmod N$, je me comprends, laisse béton si pas clair pour toi). Voici la matrice $M$ des exposants et $M \bmod 2$. Ainsi que le noyau de $M$ qui est de dimension 4. Noyau à l'anglo-saxonne i.e. ``sur les lignes'' (les 12 lignes). La détermination du noyau est indépendante de la première colonne (les 12 nombres) si bien que je n'ai pas compris ta stratégie. C'est de l'algèbre linéaire sur un corps, ici le corps $\mathbb F_2$.
Avec chaque vecteur non nul du noyau (donc $2^4 - 1 = 15$ vecteurs possibles), je peux fabriquer comme tu le sais un couple $(x,y)$ tel que $N \mid x^2 - y^2$ en espérant que $a = \gcd(x-y,N)$ et $b = \gcd(x+y,N)$ soit une factorisation pertinente de $N$. Perdu pour les 2 premiers vecteurs de la base mais gagné pour le troisième vecteur.
Pseudo-code pour la détermination du noyau ? Hum. Tu n'as pas accès à un logiciel qui fera cela mieux que toi si je peux me permettre, et en tout cas vachement plus sûr ? Sage par exemple.
"Solving Large Sparse Linear Systems Over Finite Fields" de B. A. LaMacchiaA. M. Odlyzko (vers 1990)
https://link.springer.com/content/pdf/10.1007/3-540-38424-3_8.pdf
Laisse tomber ma remarque concernant $b^2 \bmod N$ versus $b^2 - N$ : je n'avais pas remarqué que les 10 premiers coefficients vérifient $b^2 \bmod N = b^2 - N$. Donc tu travailles sous le régime $b^2 - N$. Si pas clair pour toi, laisse béton.
Si ce n'est pas indiscret, comment as tu élaboré tes 12 valeurs $b$ (la première colonne pour toi) telles que $b^2 - N$ soit ``friable'' ? Ou encore, tu es parti vraiment d'un nombre $N = N_1N_2$ et tu as joué le jeu ? Comment ? Ou bien tu as produit $N$ de manière artificielle ``à l'envers'' (par exemple pour produire un exemple dans le cadre de l'enseignement) ?
De mon côté, j'ai essayé la fonction polynomiale $x \mapsto (x + \lfloor \sqrt {N}\rfloor)^2 - N$ dont j'ignore les vertus (le polynôme de Kraïtchik) mais cela s'est avéré catastrophique comme tu vois. Note : le crible quadratique, je n'y connais pas grand chose (comme tu vois) et je me demande même si à l'instant je ne me mélange pas les pinceaux. Je laisse quand même, histoire de participer (?).
Je pars de la racine carré de N, soit u = 813828.
Je calcul v = u2 - N = 136553.
Je décompose v en facteurs premiers, pour vérifier qu'ils soient tous parmi une liste définie arbitrairement de 2 à 97 (en utilisant la méthode de Pomerance).
Ici ça ne marche pas puisque : 136553 se factorise en 19 x 7187.
J'incrémente donc u de 1 et je boucle jusqu'à trouver une solution.
Par exemple : quand u vaut 814091 alors v vaut 428279250 qui se décompose en 2x3x5x5x5x7x29x29x97.
C'est le premier élément de ma matrice modulo 2 des facteurs utilisés.
Je boucle ainsi jusqu'à obtenir la matrice en modulo 2 des factorisations que je vous ai présentée à mon premier message.
A chaque fois je teste la matrice à la recherche d'une solution, bien sûr en éliminant les cas où un facteur n'est repris qu'une seule fois.
Et c'est là que je coince, pour trouver à coup sûr les lignes de la matrice dont l'addition fait zéro, soit la solution car je récupère de ces lignes les valeurs u et v utilisées pour calculer le pgcd(X+Y, N) et pgcd(X-Y, N) avec X = le modulo de u/N et Y le modulo de v/N.
Il me reste donc à trouver une bonne méthode pour résoudre la matrice.
Je ne peux pas (et ne souhaite pas) passer par une fonction toute faite d'un langage de programmation.
Il me faut l'écrire à la mimine.
Encore merci pour votre implication.
Vu la manière dont tu as procédé. C'est bien ce que j'avais envisagé mais je n'avais pas assez insisté : il fallait aller bien plus loin (ce qui prouve que je ne connais la musique que de loin).
Quant à résoudre une matrice comme tu dis, tu pourrais peut-être étudier de manière indépendante, sur le corps $\F_2$ ou sur un corps quelconque, l'échelonnement en lignes ? J'ignore si ce qui suit va t'être utile. Je tente quand même. Note : ci-dessous, tout est à l'anglo-saxonne : on travaille en termes de lignes, vecteurs couchés, $v \cdot P$ ...etc.. Ce qui est compatible/cohérent avec tes notations.
Soit une matrice $A$ au hasard sur $\F_2$ à $n = 8$ lignes et $m = 5$ colonnes, de manière à ce qu'il y ait de la matière (du monde) dans le noyau de $A$ Voilà ce que tu pourrais étudier : la mise sous forme échelonnée. Que je note $B$ ici avec $P$ inversible $n \times n$, vérifiant $B = PA$ Détermination du noyau par le logiciel. Ce n'est PAS ce qui nous intéresse ici mais je le donne quand même pour comparaison (cf plus loin). Obtention du noyau d'une autre manière via $(B,P)$. Ce qui fait que la détermination de $(B,P)$ te donne ce que tu cherches. Je n'ai pas détaillé. J'ignore si tu connais l'algèbre linéaire. Ci-dessus, j'utilise le lien entre le noyau de $A$ et le noyau de $B = PA$ : $v$ est dans le noyau de $B$ si et seulement si $v \cdot P$ est dans le noyau de $A$. Et le noyau de $B$, on le connaît : il a pour base les $k$ derniers vecteurs de la base canonique de $\F_2^n$ où $k$ est le nombre de lignes nulles ``en bas'' de $B$.
Après quelques déboires, j'ai réussi l'exercice et ça marche.
Mais j'ai remarqué que l'ordre du traitement des lignes avait une importance dans le résultat du pivot.
Par exemple avec le tableau suivant : le pivot de Gauss me donne 3 résultats possibles :
lignes L01+L03+L04+L06+L07+L15;
lignes L00+L03+L05+L08+L14;
lignes L03+L05+L06+L07+L08+L11.
Mais si ce même tableau est classé en ordre décroissant des lignes, le pivot de Gauss me donne 4 autres résultats possibles :
lignes L06+L07+L09+L12+L15 ;
lignes L03+L13+L10;
lignes L02+L06+L07+L10+L12+L15;
lignes L01+L04+L06+L07+L10+L13+L15.
D'où une question : existe t'il un ordre particulier à respecter pour avoir le plus de chance d'avoir une bonne solution ? Dit autrement, existe t'il un ordre particulier de traitement des lignes qui permet d'obtenir toutes les solutions possibles ou à défaut un maximum de solutions ?