Factorisation des naturels

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

Factorisation des naturels

Messagepar euzenius » Jeudi 27 Mars 2008, 20:35

Bonjour,

On sait le problème complexe et le but de ce post est de fournir une piste algorithmique qui est peut-être inutilisable dès lors qu'il apparaîtrait qu'elle s'étire en longueur ce qui évidemment ne la rendrait pas plus avantageuse que l'algorithme de division par les naturels impairs de carré inférieur au nombre donné (lequel algorithme peut être amélioré en ne prenant que les impairs premiers mais encore faut-il disposer de cette liste).

Une autre solution consiste à rechercher des "décompositions de Fermat" du nombre donné i (supposé impair bien évidemment), c'est à dire de la forme :

$i = a^2 - b^2$

et naturellement distincte de la décomposition de Fermat triviale :

$i = 2k+1 = (k+1)^2 - k^2$

qui ne permet pas une factorisation propre (ie en facteurs propres)

La encore on est vite dépassé car il faudrait en première et naïve analyse environ le quart de i de valeurs à tester :
k-2, k-4, k-6,etc...

On peut améliorer les choses pour une certaine classe de naturels, dits alfrédiens (dont tous les nombres premiers), selon leur classe modulo huit s'il s'écrit :

$ i = a^2+2b^2$

$ i = a^2 +4b^2$

$ i = a^2- 2b^2 $

avec pour ce dernier cas :

$ 2b^2<i$

i est en effet premier ssi il n'existe qu'une seule. telle décomposition de surcroît primitive (pgcd(a,b)=1)

Si on trouve une décomposition non primitive alors pgcd(a,b) divise i.

Si l'on a deux décompositions primitives distinctes leur produit via l'identité de Brahmagupta (voir post divine identité) donne deux décompositions du même type non primitives et les pgcd sont des facteurs propres de i (constat non démontré).

Mais là encore c'est peu performant et en plus cela n'est pas applicable à tous les naturels (et bien sûr faute de démonstration de la constatation rien ne garantit la justesse d'un tel algorithme qui n'a de justification que parce qu'il fonctionnerait à chaque fois qu'on l'utilise).

En m'intéressant aux représentations quadratiques avec entiers impairs de naturels (voir ce post) j'ai en fait fait un pas supplémentaire vers la factorisation des naturels car on exhibe facilement des décompositions qui sont très proches de celle de Fermat et d'ailleurs les contiennent dans le cas 3M8 et 5M8, par exemple :

$35 = 18^2 -17^2 = 9^2+9^2+9^2+9^2 -17^2 $

Il faut en fait accepter que les quatre carrés de même signe puissent en fait être pairs (et donc certains nuls) ce qui ne devrait pas changer profondément l'algorithme de factorisation qui cherche à étendre celui évoqué dans le cas "alfrédien". Cela permet alors de récupérer les cas 1M8 et 7M8.

"L'algorithme" est alors le suivant :
1) Exprimer la décomposition de Fermat triviale
2) Extraire l'une des diverses représentations quadratiques de i en naturels impairs
3) Faire le produit entre cette représentation et la décomposition de Fermat triviale via la Divine Identité (attention les termes uniques - impairs - doivent être de même rang ce qui oblige aussi à prendre éventuellement à la place de la décomposition de Fermant triviale son opposé si bien que l'on obtient une représentation de l'opposé du carré de i, désolé pour cette petite cuisine que je suis incapable de justifier pour le moment)

Constate-t-on (mais cela doit être plus largement vérifié faute de pouvoir le faire moi-même hors quelques cas simples et notamment le cas alfrédien qui guide ici ma démarche) que, soit tous les termes (non nuls) de la représentation du carré de i sont premiers entre eux soit leur pgcd est un facteur propre de i soit encore ce pgcd est i lui-même et en fait il suffirait de tester le pgcd du terme unique (impair) et de i (ce qui limiterait le nombre de recours à l'algorithme d'Euclide en cascade) mais peut-être sur ce point là aussi vais-je un peu vite en besogne. L'algorithme finit pour une représentation ad hoc par fournir un facteur propre si i n'est pas premier et bien sûr tout le problème est d'exhiber assez "vite" cette judicieuse représentation permettant de craquer le nombre (si toutefois il est composé ce qui est le cas dans dans le système de codage RSA).

Comprenez bien qu'il s'agit encore d'une piste très imprécise livrée à votre sagacité et à vos critiques (surtout si je me suis planté) et qui doit donc être validée, surtout sur le plan de la rapidité du craquage. Les représentations candidates sont beaucoup plus accessibles que les représentations alfrédiennes (qui en font partie) et a fortiori que les décompositions de Fermat. La question posée est donc : "peut-on les utiliser simplement ?"

.


Bonne réflexion


Euzénius
euzenius
Kilo-utilisateur
 
Messages: 131
Inscription: Jeudi 03 Mai 2007, 16:32

Publicité

Re: Factorisation des naturels

Messagepar euzenius » Vendredi 28 Mars 2008, 17:12

Bien,

Petite indication supplémentaire : à quoi correspond la notion de "représentation primitive" que l'on peut définir simplement dans le cas alfredien (ou de Fermat) par le fait que pgcd(a,b)=1 ?

Par exemple si i = 35, une représentation immédiate de 35 est :

$35 = 3+32 = 1^2+1^2+1^2 + 9^2 - 7^2$

or cette représentation n'est pas réellement "primitive" car elle admet 7 comme diviseur qui divise donc 35 et ici 7 apparaît même être un terme de la représentation quadratique.

Par conséquent si la représentation n'est pas primitive et si le diviseur n'est pas le nombre i lui-même alors on a résolu la factorisation. Si la représentation est primitive alors il convient de la multiplier avec la Fermat triviale et voir si l'on obtient alors un facteur propre. Si l'on obtient 1 ou i alors il faut rechercher une autre représentation immédiatement accessible.

Peut-on être certain de craquer ainsi tout nombre composé rapidement ou bien cette méthode est-elle tout aussi laborieuse que les méthodes usuelles ?


Euzenius
euzenius
Kilo-utilisateur
 
Messages: 131
Inscription: Jeudi 03 Mai 2007, 16:32


Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité