Sur cette page je vais vous présenter toutes mes recherches sur un nouveau moyen de factorisation en nombres premiers

tout mes moyens de factorisations viennes de test de primalité

Premier moyen : test de primalité de fermat

Ce moyen venant du test de primalité le plus rapide et le moins sûr parmis les tests probabilistes mais précurseur du test de miller-rabin et du test de Solovoy-Strassen dit que si n est premier, alors pour toutes base b b^(n-1) ≡ 1 (mod n)

Donc je me suis dit : si n est composé, alors b^(n-1) ≡ c (mod n) et c doit avoir un lien avec un diviseur de n, et ça donne quoi si on calcule le pgcd(n;c-1). Réponse : déjà le résultat c'est forcément 1 ou un diviseur de n ou n, le tout est de savoir quelle base b donne un diviseur, ou quel calcul on peut faire avec le résultat c pour donner un multiple d'un diviseur de n. J'ai recherché dans un premier temps une base b qui donne le résultat voulue où une suite dépendant de n permettant d'en trouver une, ou une fonction qui en donne une et le meilleur résultat dans cette voie là est le programme ci-dessous, qui est aussi la seul fonction provenant de mes recherches donnant une rapidité supérieure à la factorisation naïve :

from math import gcd def aide(n, b):return gcd(n, pow(b, n, n)-b) def factor(n, maxi=10, f=aide): for i in range(n-1, 1, -1): b = i c = 1 q = f(n, b) if 1 != q != n:return q, n//q, b, b, 0, (n-i)*maxi while (1): b = pow(b, b, n) q = f(n, b) if 1 < q < n:return q, n//q, i, b, c, maxi*(n-i)+c # dernier du tuple:nombre d'étape pour factoriser n c += 1 if c > maxi:break

Deuxième moyen : partie du test de primalité AKS

La partie nous intéressant c'est le fait que si n est premier, alors pour tout X et pour tout a, (X+a)^n ≡ X^n+a (mod n)

De la même manière, la fonction pouvant donner un multiple d'un diviseur de n est f:n, X, a -> ((X+a)^n (mod n))-((X^n (mod n))+a (mod n))

Il suffit de calculer pgcd(f(n, X, a);n) pour trouver un facteur de n, en créant de nouveau le problème de choisir X et a selon n et n'ayant pas encore assez cherché de chaque coté, je doit encore attendre un peut pour publier une fonction factorisant plus rapidement que la fonction naïve.

Troisième moyen : suite d'entiers

C'est maintenant que l'on se rend compte que la première fonction (factor) est que c'est une suite où l'on exécute sur les nombres qui en résulte(de la suite).

J'ai donc décidé de testé plein de suite pour trouver des résultat satisfaisant ou pas, et j'ai trouvé une suite executé dans un programme ci-dessous, qui s'exécute très rapidement ( 50 étapes au maximum en dessous de 10⁷ ).

def power_try(n): r = pow(2, n, n) i = (pow(2, n+2, n-2)+3)%n while (1): yield r r = pow(r, i, n) i = (pow(i, n+i, n-i)+i+1)%n try_all = (lambda self, n, X, a:gcd(n, pow(X+a, n, n)-(pow(X, n, n)+a)%n)) # c'est la dernière méthode def alltest(n, a, X, dec): # pour tester la dernière méthode pour X, a = X, (a ou a-dec ou a+dec) d1 = self.try_all(n, X, a) d2 = self.try_all(n, X, a-dec) d3 = self.try_all(n, X, a+dec) if 1 < d1 < n:return d1, n//d1, a, 1 elif 1 < d2 < n:return d2, n//d2, a, 2 elif 1 < d3 < n:return d3, n//d3, a, 3 def power_try_exp(n): a = 1 m = 1 for i in power_try(n): d = alltest(n, m, i, m+i >> 1) if d is not None:return d[:2]+(1, a) if i < 2:return rho_pollard(n)+(2, 0) a += 1 if n%a == 0:return a, n//a, 3, 0 m = i