Factorisation en nombres premiers, code Gray et intégrale de parité

Factorisation des nombres, code Gray et intégrale de parité

Je vous présente ici une méthode révolutionnaire pour factoriser un entier en facteurs premiers. J'ai toujours été fasciné par le problème de la factorisation : pour moi, il doit exister un algorithme polynomial pour factoriser les entiers, même s'il n'a pas encore été découvert. Je suis persuadé que quelque part, chaque nombre doit comporter un code qui en permet la factorisation rapide. La méthode que je vous propose ici est un pas important dans cette direction.
Mais commençons par le commencement : l'intégrale de parité. Sous ce nom barbare, dû au regretté Gérard Langlet, se cache une découverte importante. Au moment ou il a fait cette découverte, Langlet s'intéressait au langage informatique APL. Ce nom ne vous dit peut-etre rien, pourtant il s'agit d'un des premiers langages de programmation, presque aussi vieux que Cobol, Lisp, Basic, Fortran et PL/1. APL n'a pas eu le succès qu'il méritait, saus aucun doute parce qu'il nécessite un clavier spécial. En effet, ce langage, ultra puissant pour la construction de fonctions et d'expressions mathématiques, et en particulier le calcul matriciel, permet de définir tout fonction d'une manière extrêmement condensée, sous forme d'une chaîne de symboles ésotériques (APL est aussi réputé pour être illisible par les profanes) mais ultra-courte. Des fonctions qui nécessitent des pages de code C ou java (des langages "modernes") s'écrivent très souvent en APL sur une seule ligne !
En APL, l'opérateur binaire "#" signifie "différence". Ainsi 1#2 vaut 1 (1 est équivalent à "vrai" en APL), 1#1 vaut 0 parce que le 0 signifie aussi "faux" en APL (comme en Basic). Lorsqu'il est appliqué un un vecteur binaire (une chaîne de bits, valant chacun 0 ou 1), l'opérateur # est équivalent au XOR des langages informatiques modernes (opérateur "^" en C ou en java par exemple). Ainsi 10010#01010 vaut 11000.
En APL, le même opérateur a souvent un sens différent lorsque'il a un ou deux arguments. Par exemple avec un seul argument qui est un vecteur de nombres, "#" signifie "faire les différences successives entre les nombres". Ainsi #2 3 4 vaut 1, parce que #2 3 vaut 1 (en effet 2 est différent de 3) et # 1 4 vaut 1 parce que 1 est différent de 4. Lorsque l'argument est une chaîne de bits, ou un nombre codé en binaire, # est l'opérateur parité : #100110 vaut 1 parce que le nombre de bits "1" est impair.
Gérard Langlet s'intéressait à l'opérateur APL de balayage, noté "\" en APL : cet opérateur unaire prend en argument une fonction à deux arguments, et applique cette fonction entre tous les nombres d'un vecteur. Ainsi en APL "\+1 2 3 4" renvoie la valeur 10, somme des quatre nombres 1, 2, 3, et 4. De même "\* 1 2 3 4" renvoie la valeur 24, produit de ces quatre nombres.
Langlet a donc essayé de trouver les propriétés de l'opérateur suivant : "\#". Cette fonction s'interprète ainsi : "Balayer successivement tous les bits du nombre et appliquer l'opérateur # entre chaque bit et le résultat obtenu pour le bit précédent". Langlet l'a appelé propagation de la parité", ou encore  intégrale de parité, pour des raisons que nous n'expliquerons pas ici. Par exemple #\1010 effectue les opérations suivantes :

• On prend le premier bit à gauche de "1010", qui vaut 1. 
• On applique # entre ce 1 et le second bit, qui vaut 0, le résultat est  1 parce que 1#0=1 
•  on applique encore une fois # entre ce résultat 1 et le troisième bit (1), le résultat est 0
•  puis une dernière fois entre ce 0 et le dernier bit(0), le résultat est encore 0. 
• On collecte tous les résultats intermédiaires : 1100. C'est le résultat de l'opération #\1010

Langlet s'est alors demandé ce qui se passait en iérant à nouveau la propagation de la parité sur ce résultat, et ainsi de suite. On obtient une séquence cyclique de nombres (on revient toujours sur le nombre de départ), que Langlet a appelé le pariton du nombre de départ.
Ainsi, en partant de "1111", on obtient :

1 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0   (ensuite on revient sur le 1 1 1 1)

Une matrice que Langlet appelait le génitond'ordre 4 et notait G4 (il appelait les paritons construits à partir de chaines de "1" des "génitons").
En partant de "11111111" on obtient :

1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0
1 0 0 0 1 0 0 0 
1 1 1 1 0 0 0 0 
1 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0 
1 0 0 0 0 0 0 0

Une matrice que Langlet appelait le geniton d'ordre 8  De telles structures sont récursives et même fractales : les seize nombres situés dans le coin supérieur gauche du géniton-8  constituent précisément  le géniton-4. En fait le géniton d'ordre 8 est précisément composé de :
G4 G4
G4 Z4
où Z4 est la matrice 4x4 remplie uniquement de zéros.
Voici une image du géniton 256 :

(image affichée sur un Atari ST, j'en ai possédé un en 1988...)
On remarque qu'il s'agit d'une structure en tapis de Sierpinski, bien connu des matheux parce qu'il s'agit de la représentation de la parité des nombres dans un triangle de Pascal.
 

Longueur des cycles

D'une manière générale, les cycles de l'intégrale de parité ont toujours une longueur qui est une puissance de 2. Si l'on part d'un nombre N, dont le nombre "1" est n (on l'appelle la masse du nombre n), alors la taille du cycle est la première puissance de 2 supérieure ou égale à n. Pour les génitons, ont part d'une chaîne de "1" dont la masse est  par définition le nombre de 1, et le cycle est toujours de longueur 2 puissance ce nombre.
Si l'on part d'une chaîne de bits représentant un nombre binaire n quelquonque, et non d'une chaîne contenant uniquement des 1, on obtient un pariton qui n'est pas sans rappeler un automate cellulaire (en fait, c'en est un !) :

La colonne de bits la plus à droite d'un pariton est, en lisant de bas en haut, un nombre binaire que Langlet appelle le Cogniton de n, noté C(n). On y reviendra.

Pariton et code de Gray

Langlet a découvert des propriétés extrêmement surprenantes des paritons. Nous allons y revenir, mais  je voudrais ici introduire une chose qu'il n'avait pas vue, et que j'ai découverte : la propagation de la parité est l'inverse de la transformation d'un nombre en code Gray binaire cyclique !
Qu'est ce que le code Gray binaire cyclique ? C'est un code inventé par Frank Gray, construit ainsi : on associe à chaque nombre entier n un autre nombre, son code Gray g(n). Et ce codage doit avoir la propriété suivante : pour tout n, g(n) et g(n+1) ne différent que d'un seul bit. Le code est le suivant, par exemple pour des nombres de 4 bits :

Pour coder un entier n en code Gray, l'algorithme est très simple ; g(n) = n#(n/2) où # est l'opérateur XOR. Par exemple pour trouver le code Gray de 11 (soit 1011 en binaire) on effectue :
   1 0 1 1
#    1 0 1    (soit 1011 divisé par 2, ou décalé d'un bit à droite)
-----------
   1 1 1 0, et on vérifie dans la table ci-dessus que c'est bien ça !
Par contre, pour décoder un nombre codé en  Gray, l'opération est... l'intégrale de parité "\#" ! Par exemple pour décoder 1 1 1 0, on effectue
    1= 1 (bit de gauche : premier bit=1)
1#1 = 0 (second bit = 1, XOR résultat précédent 1)
1#0 = 1 (troisième bit = 1, XOR  résultat précédent 0)
0#1 = 1 (quatrième bit (à gauche) = 0, XOR résultat précédent 1)
et le résultat est bien 1 0 1 1.  Autrement dit, l'intégrale de parité de Langlet est l'inverse du codage Gray !
Et de fait, en itérant successivement le codage Gray : n, g(n), g(g(n)), etc, on obtient naturellement une structure cyclique. Et dire qu'il y a encore quelques sites internet qui se demandent comment déterminer la longueur de ce cycle pour un n donné : réponse, voir plus haut...
Vous demandez quel est le lien avec la factorisation en nombre premiers ? Patience, j'y viens, j'y viens.... Mais auparavant, continuons à regarder quelques propriétés étonnantes des paritons et de l'intégrale de Langlet (et donc aussi du code Gray) :

Surprises de l'intégrale de parité

En considérant les génitons comme des matrices G, on peut construire leurs puissance successives G², G³...  Le résultat surprenant est que l'on trouve pour tout géniton G que G² est le symétrique Gd de G (son image miroir par rapport à un axe vertical), et que son cube est la matrice unité I. Gd est donc la racine carrée de G. G, G² et I constituent un système ayant une symétrie d'ordre 3. Quant à la matrice inverse de G,  c'est encore son symétrique Gd. En considérant d'autre symétries, comme la symétrie Gh par rapport à un axe horizontal, ou les rotations de ces matrices,  on trouve que ces matrices sont leurs propres inverses (donc symétrie d'ordre 2). En combinant ces symétries d'ordre 3 et d'ordre 2, on constitue des symétries cubiques et hexagonales.
Appelons nombre primaire un nombre qui est :
- soit une puissance de 2 (2^n)
- soit l'un des n-1 nombres extraits du pariton de 2^n (ou du géniton Gn)
Il y a exactement n nombre primaires à n bits ;
pn₀ = 2^n, pn₁ = #\ pn₀, pn₂ = #\ pn₁, etc. (\# est l'intégrale de parité)
pn_n = pn₀
Alors tout nombre N à n bits est décomposable de manière unique en XOR de nombre primaires à n bits (au maximum n)
Les nombres primaires de la décomposition sont précisément ceux  indiqués par les bits à 1 dans le cogniton de N.
Langlet définit la transformée de Langlet de N : L(N) = c, le cogniton de N. Comme la transformée de Fourier, elle est réversible : L(c) = N, et L(L(N)) = N
Elle possède d'ailleurs d'intéressantes analogies avec la transformée de Fourier, tout en étant beaucoup plus rapide à calculer (et même plus rapide que la FFT)
(je ne m'étendrai pas plus sur ce sujet passionnant, que Langlet explore dans son papier toward the ultimate APL-TOE ).

Surprises du code Gray

Voici quelques propriétés que j'ai découvertes à propos de la fonction g(n) qui associe à tout nombre entier son code de Gray g(n) = n # (n >> 1) où >> est l'oprateur de décalage à droite :

• g(a # b)  = g(a) # g(b)    où # est l'opérateur XOR 
• g(n+1) = g(n) # 2^nz(n)  où nz(n) est le numéro du bit valant "0" le plus à droite de n (le bit 0 étant ici le bit de droite, ou de poids faible)
• g(#\n) = n  où #\ est l'intégrale de parité définie ci dessus.
• g(a+b) = g(a) ^ g(b) ^ g(a ^ b ^ (a+b))
• g(2^k) = 2^k # 2^(k-1),  k >= 1 ; g(1) = 1, g(2) = '11', g(4) == '110' , etc
• g(2a)-g(2a+1) = a%2*2-1    où % est l'opérateur "modulo" ou "reste de la division".
• XOR(k=0..n) {g(a<<k)} = (a>>1) ^ (a<<n),  n >= 0

Revenons à la factorisation

Considérons un nombre n à factoriser, par exemple 4097 = 17 x 241, et écrivons son pariton :

 1 [1 0 0 0 0 0 0 0 0 0 0 0 1 ] (n=4097 en base 2)
 2 [1 1 0 0 0 0 0 0 0 0 0 0 1 ] g(n)
 3 [1 0 1 0 0 0 0 0 0 0 0 0 1 ] g(g(n))
 4 [1 1 1 1 0 0 0 0 0 0 0 0 1 ] etc.
 5 [1 0 0 0 1 0 0 0 0 0 0 0 1 ] 
 6 [1 1 0 0 1 1 0 0 0 0 0 0 1 ]
 7 [1 0 1 0 1 0 1 0 0 0 0 0 1 ]
 8 [1 1 1 1 1 1 1 1 0 0 0 0 1 ]
 9 [1 0 0 0 0 0 0 0 1 0 0 0 1 ]
10 [1 1 0 0 0 0 0 0 1 1 0 0 1 ]
11 [1 0 1 0 0 0 0 0 1 0 1 0 1 ]
12 [1 1 1 1 0 0 0 0 1 1 1 1 1 ]
13 [1 0 0 0 1 0 0 0 1 0 0 0 0 ]
14 [1 1 0 0 1 1 0 0 1 1 0 0 0 ]
15 [1 0 1 0 1 0 1 0 1 0 1 0 0 ]
16 [1 1 1 1 1 1 1 1 1 1 1 1 0 ]
17 [1 0 0 0 0 0 0 0 0 0 0 0 1 ] n

En binaire, 17 s'écrit 1 0 0 0 1  : or on retrouve ces bits dans le pariton, au début de la ligne 5 et de la ligne 13, et à la fin de la ligne 9
et 241 s'écrit  1 1 1 1 0 0 0 1  : on en retrouve les 7 premiers bits au début de la ligne 4 et de la ligne 12, et les 4 derniers aussi à la fin des lignes 4 à 8...
Curieuse coïncidence ! En fait ce n'en n'est pas une : pour tout nombre n de b bits qui est le produit de 2 nombres premiers a et b, on retrouve les premiers bits de a et b au début des lignes du pariton, et les derniers bits à la fin... il devient alors très facile de factoriser n en écrivant son pariton (dont le nombre de lignes est au maximum celui du nombre de bits de n),  et en cherchant à concaténer les p premiers bits d'une ligne i et les q derniers bits d'une ligne j... (avec p+q <= b), soit un algorithme de factorisation polynomial, dont le temps de calcul est en O(b³) !
Voici un Fichier Excel qui vous aidera à calculer les paritons.
Il y a un bémol : cela marche pour presque tous les nombres (j'ai testé tous les nombres de la forme a*b avec a et b premiers, de moins de 32 bits, et un bon paquet de nombres jusqu'à 64 bits), mais pas tous !  Dans certains cas, il faut chercher en plus des bits au milieu des lignes du pariton, et même les inverser (0<->1). Mais globalement ça va très vite !
Je livre donc à votre sagacité cet algorithme, certainement améliorable (par exemple dans les cas d'échec on peut chercher des bits au centre des lignes et pas seulement au début et à la fin). De plus il reste à le prouver formellement : il faudrait trouver un moyen de déterminer à l'avance les lignes i,j... du pariton, sur lesquelles chercher les bits des diviseur. Enfin, je n'ai pas testé en remplaçant le pariton tel que décrit par Langlet par la suite (équivalente) des codes Gray itérés engendrés par n.
Bons calculs !
Plus d'infos sur Gérard Langlet et l'intégrale de parité : la liste des pages web consacrées à ce sujet !

---

Home Mes livres Mes tableaux

---

Partagez / votez pour cette page :