Journal d'un Terrien
Web log de Serge Boisse
On line depuis 1992 !
Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/factorisation-langlet-code-gray.php
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 lorsqu'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éniton d'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 (dans les langages informatiqus usuels, différents de APL, il faut remplacer '#' par "|"). 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 G2, G3... Le résultat surprenant est que l'on trouve pour tout géniton G que G2 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, G2 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 ;
pn0 = 2^n, pn1 =#\ pn0, pn2 =#\ pn1, etc. (\#est l'intégrale de parité)
pnn = pn0
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'opérateur 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(b3) !
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 !
Commentaires (12) :
Page : [1]Le 25/05/2013 à 14h52
c'est mieux que tout ses trucs sans solution puisque Godel a montrer que l'arithmétique est incomplete donc la démonstration direct du théorème fondamental de l'arithmétique n'est logiquement et relativement pas possible si se théorème est fondamental . (pas de formule {F_i} tel que quel que soit N , F_i(N)=P_i = ieme facteur premier de l'entier N à k diviseur premier (à une permutation prés) .
Le 29/09/2012 à 11h21
Le 28/09/2012 à 23h14
JEAN-PAUL DELAHAYE en parle aussi dans "Pour la science" d'aout 1997 dans un article consacré au code Gray.
Le 19/10/2010 à 10h46
Le 12/09/2010 à 17h24
A la réflexion, je me demande si la présence d'une partie des facteurs dans le géniton n'est pas uniquement due au hasard:
Pour un nombre de 32 bits, un des facteurs fait moins de 16 bits, et l'ordre du géniton est de 32. Comme le premier bit de chaque ligne est forcément égal au premier bit des facteurs (c'est à dire un 1), il est donc "assez probable" de trouver les 6 premiers bits parmi les 32 débuts (2 puissance 5) de lignes du géniton, ainsi que les 5 derniers parmi les 32 fins de lignes, soit en tout 11 bits sur 16. Si en plus on s'autorise à chercher des bits en milieu de ligne et à inverser les bits, on est statistiquement certains de trouver les facteurs quelque part dans la matrice (mais ça serait également vrai pour une matrice de nombres aléatoires).
Par contre, dès que le nombre de bits augmente (de 32 à 64, par exemple), le géniton ne fait que doubler, alors que les possibilités sont élevés au carré. On trouve donc de moins en moins de coïncidences. En fait je n'ai pas trouvé d'exemple où on retrouvait plus de 7 ou 8 bits des facteurs en début ou en fin de ligne (ce qui doit être conforme à la statistique).
Dommage, l'idée semblait séduisante.
Le 09/08/2010 à 15h26
ça m'étonnerait que "lakar" ait trouvé une "méthode très simple" qui soit également *rapide*(polynomiale ?)... Je n'y crois pas, raison pour laquelle je ne lui ai pas répondu...
@lakar : envoie-moi quelques exemples de factorisation sur des grands nombres, avec leur temps de calcul, et je te dirai si ta méthode est intéressante ou pas !
Le 06/08/2010 à 16h55
Par contre, trouver les facteurs premiers d'un nombre composé est autrement plus difficile. Si ce que tu dis est vrai, je te promet que les exploitants (et les militaires de tous pays, vu que c'est utilisé en cryptographie) vont te proposer des millions, tu n'aura pas à chercher.
Pour prouver que ta méthode est efficace, peux-tu, s'il te plaît, me factoriser les quelques nombres qui sont sur cette page: http://www.rsa.com/rsalabs/node.asp?id=2093 (ceux qui sont notés "not factored") ?
Le 07/05/2010 à 13h48
Je suis un simple curieux dans l'arithmétique, et je vous le dit en toute clarté, j'ai trouvé une méthode très simple pour déterminer les facteurs premiers d'un nombres ou de dire que le nombre est premier.
Ma méthode elle inédite et unique.
j'ai cherché partout et j'ai rien trouvé de similaire.
c'est une méthode avec le pgcd.
je cherche un exploitant pour lui céder cette méthode.
Pouvez vous m'aider
Merci
Le 30/12/2009 à 14h21
Il y avait une erreur. J'ai corrigé la page.
Je n'utilise pas APL, mais gnuplot et Excel (j'ai inclu dans la page un lien vers un fichier Excel à titre d'exemple).
Dans gnuplot, g(n) se définit par g(n)=n^(n/2)
(pour gnuplot ^ est le XOR)
Mais dans cette page Web j'ai noté # pour XOR et ^ pour les puissances. J'espère que cela reste clair.
Le 26/12/2009 à 03h47
Merci!
Mais certaines d'entre elles n'a pas de sens.
1111111111110 est non 4097, c' est 8190!
Utilisez-vous l'espace de travail de Langlet - Generie?
Est une copie de vos fonctions APL disponibles? Le navigateur Web ne présentent pas les symboles correctement.
Par exemple, le operatoeur XOR est indiqué que «#» de sorte qu'il est presque impossible de suivre vos exemples.
S'il vous plaît écrivez-moi -> jimserac(at)gmail(dot)com
Le 19/11/2009 à 03h12
Le 25/10/2009 à 20h37
Dans l'article : "NOTE sur LALGEBRE BINAIRE
ET LA METHODE des MOINDRES CARRES", Les Nouvelles dAPL N° 34
Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.