Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 317

Décomposition en facteurs premiers

Bonjour,

Nous sommes ici dans la partie « programmation » dédiée aux algorithmes, aux programmes, au codage, bref au numérique dans tout ce qu’il peut avoir d’automatisé, je vais donc détailler ma démarche pour factoriser dans un temps raisonnable n’importe quel nombre même avec des dizaines de décimales.

Premier point, je vais faire le truc en html+javascript. Avantage, cela fonctionne avec un seul fichier texte capable d’être exécuté par n’importe quel navigateur. Inconvénient, je n’y connais rien ni en html (sauf que je sais qu’il y a une histoire de balises) ni en javascript (bourré d’instructions très spécifiques) ni en algorithmes de factorisation (à part la recherche brute qui consiste à diviser par 2, 3 et 6k±1 jusqu’à racine(N)).

Problème, la recherche brute jusqu’à $10^{15}$ ça va encore assez vite, mais au-delà ça devient carrément pas vite du tout. Si le nombre est composé ça passe, parce que dès qu’on a divisé on se retrouve avec des morceaux bien plus petits – donc ça va vite – mais avec un grand nombre qui est premier il faut épuiser toutes les divisions, pas top.

Je demande à l’IA s’il y a moyen d’accélérer le bousin. Il me parle d’algorithmes probabilistes, par exemple un certain Miller-Rabin (enchanté) qui permet de savoir rapidement si un nombre est premier ou non, avec une bonne marge de confiance. C’est quoi cette marge ? Eh bien on essaie avec plusieurs bases (qu’on ne me demande pas ce que c’est) et plus il y en a plus c’est fiable. Ah bon. Après essais je lui demande de m’en coller direct cinquante dans le code, avec ça le résultat est une quasi-certitude et il exécute le truc en quelques millisecondes, pourquoi se priver ? Donc où bien c’est premier et c’est immédiat, ou bien ce n’est pas premier et il n’en dit pas plus.

Ok, le nombre n’est pas premier. Sil est petit, on sait faire. S’il est grand, est-ce qu’il existe d’autres algorithmes efficaces ? Eh bien oui, l’IA me parle d’un certain Pollard rho également probabiliste qui trouve, dans la plupart des cas, des facteurs s’il y en a. Le problème, c’est que chaque facteur n’est pas obligatoirement le plus petit ni obligatoirement dans l’ordre.

Je me dis pas grave, une fois qu’il a un facteur il en a automatiquement un deuxième (le résultat de la division) et là il suffit de considérer les deux nombres comme deux autres recherches indépendantes jusqu’au moment où il ne reste plus que du facteur premier et rien d’autre. Je demande à l’IA si elle sait faire ce genre de morcellement ? Réponse, oui, c’est sans problème. Le programme en html+javascript encapsulé, le Miller-machin, le Pollard-truc et la moulinette 6k±1, le tout récursif, clé en main ? Sans problème, qu’elle répète, et sans même demander confirmation, pof elle me pond un code qui marche !

Le résultat est là :
https://sites.google.com/view/ernst01/facteurs-premiers

Bon, d’accord, faut pas lui demander de miracle non plus, mais jusqu’à $10^{30}$ c’est vraiment honnête.

(ou comment faire un truc qui aurait fait baver les auteurs des récréations mathématiques du siècle dernier sans rien connaître à la théorie mathématique, aux modulos, aux nombres premiers, aux algorithmes, à la programmation, au javascript, etc.)

Ernst

Membre

Inscription : 30-01-2024

Messages : 317

Re : Décomposition en facteurs premiers

Bonjour,

Allez hop, code amélioré et finalisé en ligne, même URL.

Pour le test de Miller-Rabin, 64 bases sont utilisées, 32 bases fixes (les 32 premiers nombres premiers, de 2 à 131) et 32 bases aléatoires (intervalle 2, n−2). Chaque base de test réduit par au moins 75% la probabilité de faux positifs (c’est la propriété de Miller-Rabin). Ainsi, la probabilité de déclarer "premier" un nombre qui est en réalité composé est maintenant d'environ 5.4 × 10⁻³⁹. Autrement dit, le test satisfait largement les exigences des usages généraux de la cryptographie courante (RSA, Diffie-Hellman, etc.) et même des outils comme OpenSSL, GnuPG ou GMP (qui utilisent en général 25 à 64 tests).

Pollard Rho est également amélioré par la version Brent qui s’y prend autrement et mieux, ce qui en moyenne gagne ici un facteur deux.

Et enfin le calcul parallèle. Javascript permet d’implémenter des Web Workers capables de travailler indépendamment, ce qui tombe bien puisque chaque base fait une recherche autonome. On va donc lire le nombre de threads disponibles, on implémente autant de blocs qui calculeront en parallèle, et en gros pour des factorisations compliquées, sur mon PC je passe d’une quarantaine de secondes avec thread unique et Pollard simple à six secondes avec Pollard Rho Brent amélioré et web workers.

En dehors de la cryptographie qui cherche des décompositions compliquées, la plupart des nombres se décomposent maintenant super vite et super bien, et cela a été un vrai plaisir de bricoler ce genre de truc sans avoir à mettre trop les mains dans le cambouis.

Rescassol

Membre

Lieu : 30610 Sauve

Inscription : 19-09-2023

Messages : 320

Re : Décomposition en facteurs premiers

Bonjour,

Aurais tu la même chose en Python ?

Cordialement,
Rescassol

Ernst

Membre

Inscription : 30-01-2024

Messages : 317

Re : Décomposition en facteurs premiers

Bonjour Rescassol,

En Python c'est nettement moins rigolo, il n'y a plus rien à faire : il existe des bibliothèques spécialisées très efficaces qu'il suffit de charger avec pip pour que le résultat soit excellent. Avec 'sympy' par exemple, 'factorint' enchaîne Miller-Rabin, force brute, Pollard-Rho et ECM sans rien demander à personne et à la vitesse max, c’est fou.

Pour dire, décomposer 466751831375951548784665726729 sur mon PC avec mon programme met environ 6 à 7 secondes en multi-threading alors qu’avec ce programme mono-thread en Python c’est dix fois plus rapide.

À noter qu’à cause des paramètres variables dans Pollard et ECM, les temps d’exécution peuvent eux aussi varier d’un facteur dix, aussi bien en JavaScript qu’en Python, normal.

import sys
import time
from sympy import isprime, factorint

def compact_factors(factor_dict):
    parts = []
    for base in sorted(factor_dict.keys()):
        exp = factor_dict[base]
        parts.append(f"{base}^{exp}" if exp > 1 else str(base))
    return " × ".join(parts)

def main():
    while True:
        try:
            input_str = input("\n> ").strip()

            if input_str.lower() == 'q' or input_str == '':
                print("Fin du programme.")
                break

            if not input_str.isdigit():
                print("Erreur : veuillez entrer un entier positif composé uniquement de chiffres.")
                continue

            n = int(input_str)
            if n <= 1:
                print(f"Entrée triviale : {n}")
                continue

            print("Calcul en cours...")

            start = time.time()
            if isprime(n):
                factors = {n: 1}
            else:
                factors = factorint(n)
            end = time.time()

            print(f"\nNombre initial :\n{n}")
            print(f"\nDécomposition en facteurs premiers :\n{compact_factors(factors)}")
            print(f"\nTemps écoulé : {round((end - start) * 1000, 3)} ms")
            print(f"(Nombre de facteurs trouvés : {sum(factors.values())})")

        except Exception as e:
            print(f"Erreur pendant la factorisation : {str(e)}")

if __name__ == "__main__":
    print("Entrez un entier (≥ 2) à factoriser. Tapez 'q' ou appuyez sur Entrée pour quitter.")
    main()

 

Dernière modification par Ernst (26-07-2025 14:38:50)

Rescassol

Membre

Lieu : 30610 Sauve

Inscription : 19-09-2023

Messages : 320

Re : Décomposition en facteurs premiers

Bonsoir,

Merci, Ernst.

Cordialement,
Rescassol