Stratégie de factorisation

FACTORISER un nombre semi-premier p consiste donc à  trouver les deux nombres premiers m et n dont le produit (m*n) donne p.
Notre stratégie de factorisation consistera non pas à  factoriser directement un nombre semi-premier p, mais à factoriser le produit de ce nombre semi- premier p
par un multiplicateur k.

Soit p un nombre semi-premier tel que p = m * n avec 2 < m < n
Classiquement pour factoriser p, on cherche à  résoudre l’équation x² – y² = p, avec l’UNIQUE SOLUTION non triviale.

Mais si on multiplie p par un autre nombre semi-premier, NOMBRE MULTIPLICATEUR k, nous avons 4 solutions non triviales pour factoriser le produit de (p*k)
et par conséquent, factoriser indirectement p.

Soit k, un nombre semi-premier tel que k = a * b avec  2 ≠ a ≠ b ≠ m ≠ n
Si on MULTIPLIE p par k on obtient donc :

p * k = m * n * a * b

ou p * k = (m*a) * (n*b)

ou p * k = (n*a) * (m*b)

ou p * k = (n*a*b) * (m)

ou p * k = (m*a*b) * (n)

Il y à  donc 4 façons d’écrire le produit (p * k)  qui permettent de factoriser le nombre semi-premier p de départ.

Exemple :
Soit le nombre semi-premier p = 21 à  factoriser.
Choisissons un autre nombre semi-premier qu’on va multiplier par p ; donc soit k = 143.

(p*k) = 21 * 143
Mais (p*k) peut aussi être exprimé autrement :

(p*k) = 77 * 39

(p*k) = 33 * 91

(p*k) = 429 * 7

(p*k) = 1001 * 3
Des cas, qui permettent de factoriser le p de départ.
Donc au lieu de chercher 1 seule et unique solution de pouvoir écrire p sous forme de différence de deux carrés, on a 4 fois plus de possibilités d’écrire (p*k) sous forme de différence de deux carrés :

p = 21 = 5² – 2² ,ce qui est l’unique solution non triviale.

Par contre pour (p*k) on a :

(p*k) = 50² – 49²

(p*k) = 218² – 211²

(p*k) = 142² – 131²

(p*k) = 122² – 109²

(p*k) = 82² – 61²

(p*k) = 62² – 29²

(p*k) = 58² – 19²

Donc on ne cherche plus l’unique solution d’exprimer p sous forme de différence de deux carrés, mais une des nombreuses possibilités  d’écrire (p*k) sous forme de différence de deux carrés.

D’autre part, la façon la plus évidente de factoriser un nombre  p semi-premier sous forme de différence de deux carrés, c’est quand l’UN  des carrés est de la forme :

 

Par exemple prenons 143 :
On a bien

  permet de factoriser 143, en effet 143 = 

C’est à  dire 143 = 12² – 1²

De sorte que pour rendre plus évidente la factorisation d’un  semi-premier p, c’est à  dire pour que l’un des membres carrés qui  permettent de factoriser p soit de la forme , il  suffit donc de trouver un autre semi-premier ou un autre nombre tout  simplement qu’on multiplie par p et il en devient que factoriser p  revient à factoriser (p*k) sachant que l’un des membres carrés qui permet de factoriser (p*k) est de la forme

De façon générale cette stratégie de factorisation est basée sur la résolution de l’équation diophantienne :

Avec un cas particulier évident où y² = 1 ; l’équation devient donc :

Où p est le nombre semi-premier à  factoriser et x, un multiplicateur qui permet de factoriser (p*x) sous la forme la plus évidente.

Pour p = 21 on a :

Des solutions possibles pour x sont : {3;8;19;40;55;80;88;119  etc…}
C’est à  dire les solutions non triviales de l’équation Diophantienne :