Bonjour,
Je passe beaucoup de temps a inventer des methodes de factorisation.

J'apprends principalement les math en autodidacte, mais je suis informaticien et je crée moi même mes outils d'analyses et mes algorithmes de calculs.
Ce que je vais dire plus bas sera probablement Mathématiquement incorect, mais en tant qu'algorithmes dans un programme, cela marche (bien que je n'expliquerais pas tout les détails, cela serait trop long).


Voici une vielle methode que j'ai inventée, mais je la ressort du placard car je viens de remarquer que certains résultats qui me semblaient triviaux (des solutions qui semblement n'âpparaitre que par le hasard) apparraissent dans des gros nombres tels que RSA 576. Pour autant, il me manque encore quelque chose pour être utilisé sur de gros chiffres. (Je compte utiliser cette methode avec le crible quadratique)
En attendant, cet algorithme factorise un nombre composé de l'ordre du milliards en 4 ou 5 itérations.
D'abord je vais tenter d'expliquer un objet mathématique spécifique:

// Avant propos : explications sur mes polynomes algorithmiques et leurs racines :


J'utilise des objets mathématique que j'appelle "Racines de polynomes générateurs de facteurs", mais je me trompe peut être dans la définition, je pense qu'il s'agit de corps quadratique réel.
Prenons N=P*Q, nous pouvons trouver les facteurs grace a la relation:
X²-Y²=N donc P=X+Y et Q=X-Y
Mais cela dans ma methode n'est que la racine de polynome N°1, ou X est le générateur, et Y la distance carrée a N.
Nous pouvons faire : RX²-RY² +-1 =0 mod N

Prenons la racine polynome 2, elle se subdivise en 4 et se calcule comme ceci:
Poly2=Racine(N)/racine(2)
PosPoly2[0]=Poly2 * Poly2*2
C'est en fait un carré fois 2, mais je le sépare, car pour les 3 subdivisions precedentes avant de revenir sur une racine principale, il faudra pour chaque incrementation I :
PosPoly2[+1] = PosPoly2[0]+Poly2 = Poly2 * (Poly2*2+1)
PosPoly2[+2] = PosPoly2[+1]+Poly2 = Poly2 *(PosPoly2+1)*2
Centre atteint : Poly2=Poly2+1
PosPoly2[+3] = PosPoly2[+2]+Poly2 = Poly2 * (Poly2*2+1)
PosPoly2[+4] : On est de nouveau sur une racine principale.
En fait, il ne suffit que de gerer la position et la valeur Poly2.
A quoi sert ce polynome algorithmique ?
Et bien c'est lui qui génére les facteurs dans sa trainée.
Par exemple :
si N = P*Q et 2*P environ = Q
Alors, pour un nombre relativement petit (<32 bits) on peut le trouver trés rapidement en suivant les racines Polynome de 2.
N=13321
Poly2 =racine(13321)/racine(2)+1 ou plus simplement racine(13321/2)+1 =82

PosPoly2 = 82* (82*2) = 13448
nous somme sur une racine principale les facteurs s'eloignent de la racine comme ceci :
Pospoly-2Y² possede les facteurs Poly-Y et Poly+Y
En fait cela genere un nombre = (Poly-Y)*(Poly+Y)*2
Car c'est une racine principale, mais les subdivisions generent les couples Poly+Y et Poly-Y de facon decalé.
Passont a la subdivision precedente par la même occasion n rapprocher de N:
PosPoly2 =PosPoly2 -Poly = 13448-82 = 13366
puis la difference avec N : Diff= 13366-13321 = 45
On divise par 2 (grossierement, car une subdivision ne tombe juste qu'a 1 pres) : Diff=Diff/2= 45/2 = 22.5
On calcule la racine : Y= racine(22.5) = 4.7 donc arrondit= 5 (car les subdivisions ne sont pas pile poil des carrés mais oscillent autour sans dépasser 1)
On teste : GCD(N,Poly-5) GCD(N,Poly+5) ( +Y ou -Y selon la la partie a scanner, mais a defaut on teste les 2)
On en conclu : Poly-5 = 82-5= 77 = 0 mod N donc 77 divise N.

// Fin de l'explication sur les polynomes algorithmiques


Maintenant une methode qui utilise ce genre de polynomes:
Soit N=P*Q un nombre à factoriser.

Prenons Nm1=(N-1)/2 et Nm2=(N+1)/2
Nm2²-Nm1² = N , bien que ce soit une relation triviale.
Par contre :
Nm2²-X² = Nm1²-Y² = N2
N2= ( (P-1)*(Q-1) /2) * ( (P+1)*(Q+1)/2 )
ET
N2= ( (P-1)*(Q+1) /2) * ( (P+1)*(Q-1)/2 )

Ainsi:
Nm2-X= ( (P-1)*(Q-1) /2) , Nm2+X= ( (P+1)*(Q+1)/2 )
Nm1-Y= ( (P-1)*(Q+1) /2), Nm1+Y=( (P+1)*(Q-1)/2 )
Soit N2, un nombre ou NM1²-Y² et Nm2²-X² converge sur la même ligne pour donner le même nombre mais avec des facteurs différents a 1 prés.

Le problemme est inversé, avant on avait N mais des racines inconnues, maintenant des racines connues (au moin les centres) mais nous devons chercher N2, le nombre ou converge ces racines.

Maintenant que l'environnement est posé, nous allons accélérer la recherche grace aux autres racines de polynome.
Soit P et Q non divisibles par 6, donc aprés quelques constatations, nous pouvons en deduire que N2 composé de : (P-1 , P+1 , Q-1 , Q+1) possede le facteur 144 (6*6*2*2), mais probablement 288, voir même souvent 576.

Par exemple N2 possede (P-1*Q-1 , P-1*Q+1 , P+1*Q+1 , P+1*Q+1) mais n'est pas le produit de ces 4 couples de nombres car :
N2= ( (P-1)*(Q-1) /2) * ( (P+1)*(Q+1)/2 )
ET
N2= ( (P-1)*(Q+1) /2) * ( (P+1)*(Q-1)/2 )

Mais avec les polynomes que nous allons utiliser nous pouvont tomber sur n'importe quelle combinaison de facteurs possibles par exemple sur (P-1)*(Q+1) ou sur (P-1)*(Q+1) *A /B


En fait pour mon algorithme on peut supposer N2 possedant le facteur 576, même s'il ne l'est pas, cela marchera dans la grande majoritée des cas. Il suffit juste d'un nombre qui posséde suffisament de multiple communs avec le nombre N2 recherché.


Maintenant que l'on a Nm1², Nm2² et que l'on sait que un peu avant Nm1², il y a un nombre N2 qui possede les facteur P-1, P+1, Q-1, Q+1, nous allons faire converger le "polynome racine de 576 générateur de facteurs" sur N2.

Pour cela, calculont simplement la racine principale de ce polynome racine :
Poly576=arrondit( Racine(Nm1)/racine(576) )+1
Puis Multipliont le au carré * 576
PositionPoly576 = Poly576²*576
Voila nous avons notre polynome et sa position, il marche de la même facon que le polynome de 2 expliqué plus haut.

Il y a exactement 2*576 subdivisions entre 2 Racines principales.

Ainsi, il suffit de diviser la distance entre PositionPoly576 et un nombre quelquonque par 576 puis de prendre la racine du reste :Y Et l'on sait QU'AUCUN autres facteurs entre Poly-Y et Poly+Y ne peut exister avant le Polynome (ou subdivision du polynome)de 576 precedent.

Maintenant comment savoir si N2 sera a un carré * 576 de notre polynome ?
C'est une de mes conjonctures, je n'essaierais pas de la prouver, mais elle s'avere vrai sur des nombres tels que RSA 576 :
Si pour un polynome donné (ici 576), lui ou l'une de ses subdivisions se trouve a un carré de Nm1² et une autre ou la même a un carré de Nm2² alors les facteurs généré par les 2 polynomes et ceux de Nm1 et Nm2 convergent sur une même ligne.

Ainsi les Nm1 et Nm2 donneront les (P-1,P-1,Q-1,Q+1) (/4)
Et les Polynomes 576 donneront des assortiments de facteurs environs divisé par des multiples de 576.
Mais pourtant N2 n'est peut être pas divisible par 576 ?
Deux explications :
- Les facteurs supérieurs a la racine d'un nombre N peuvent se trouver en couple tout les 2 multiple d'un même nombre même si le nombre N n'est divisible que par un seul de ces nombres:
ex 2*5*7 possede 10 et possede 14 mais pas 10*14 (un seul 2)
- Selon la distance carré ou se trouve les poly576 de Nm1 et Nm2, les facteurs qu'ils donneront seront automatiquement plus ou moin multiples de 576 mais en tout cas convergeront sur la même ligne.


Si les poly 576 ne convergent pas sur la même ligne, c'est simple :
C'est qu'ils ne se trouvent pas a un carré de Nm1² et de Nm2².
Il peut y avoir des exceptions (car c'est une conjoncture que j'ai faite par déduction, de facon completement empirique), mais d'apres mes tests sur de grands nombres, les polys qui convergent sur la solution ont leurs racines qui se trouvent quasiment tous tres pres de NM1² et de NM2². (de l'ordre de 30² a 60²) et encore plus etonnant : pour de gros nombres >100 chiffres constitués de 2 nombres premiers de même taille, non seulement les poly solutions sont extrement prés de Nm1² et Nm2², mais ils convergent également souvent souvent sur Nm1*Nm2 (la subdivision au centre des racines principales Nm1 et Nm2)

Donc Poly576N°1 est a 15² de NM1² et Poly576N°2 est a 12² de NM2², il faut partir de ces deux racines.
Deja, la distance minimale est NM2²-NM1² qui correspond a N en tant que distance.
donc Y2=racine(N/576)
ensuite Poly576N°2 - 576*Y2² doit être égal a Poly576N°1 -576*Y1²

Comme on le voit ici, les carrés Y1 et Y2 s'incrementent par multiples de 576.
Pour un nombre N de l'ordre de 100 millions dont la racine est de 10000, si les facteurs ont environt même nombre de chiffres, alors il faut au plus 17 tests (tres rapides) pour couvrir toute la zone qui correspondra a racine(N)<=X<= 2*Racine(N) dans l'equation N=X²-Y².
On incremente Y2 de 1 a 17 (pour un nombre de 100 millios ou 170 pour 1 milliard) dans Poly576N°2 - 576*Y2² et on regarde si le nombre obtenu se trouve a 576*Y1 (Y1 quelqconque) de la position de Poly576N°1

Si c'est bon alors on calcule la différence avec Nm1² qui doit obligatoirement être un carré qui correspondra a Y² et la difference avec Nm2² qui correspondra a X² dans l'equation : X²-Y² = N = (X+Y)*(X-Y) = P*Q

Recapitulatif :
N=P*Q
- Prendre Nm1=(N-1)/2 et Nm2=(N+1)/2
Prendre la racine du polynome 576 (dans l'exemple) qui est :
Poly576= racine(Nm1²/576)
et sa position qui est :
PosPoly576= Poly576* 576*Poly576
Puis incrementer ou decrementer les positions pour obtenir 2 polynomes chacun a un carré de Nm1² et de Nm2²
Aligner les Y1 et Y2 dans l'equation :
Poly576N°2 - 576*Y2² = Poly576N°1 - 576*Y1²

La position corresponds a :
N2= ( (P-1)*(Q-1) /2) * ( (P+1)*(Q+1)/2 ) = ( (P-1)*(Q+1) /2) * ( (P+1)*(Q-1)/2 )

// Améliorations :
- Chercher tous les polynomes qui sont a un carré de Nm1² et Nm2²
- Genérer un super-polynome synthese de tout les autres
- Chercher la ligne ou converge ce polynome.
// Ou (ce qu je tente de faire)
- Coupler cet algorithme pour trouver plus rapidement des Y porteurs de carrés dans l'algorithme du crible quadratique)