recherche site qui factorise un nombre entier

Kenta

Bonjour tout le monde,

Je suis à la recherche d’un outil, que ce soit un site web, un logiciel ou un programme, qui pourrait m’aider à factoriser de très grands nombres entiers en produits de deux autres nombres entiers. Par exemple, je voudrais pouvoir factoriser les nombres suivants : 1125897758834689 et 75058311923371.

De plus, je suis également à la recherche d’une calculatrice capable de gérer de très grands nombres. Si vous connaissez des ressources qui pourraient m’aider dans ces domaines, je serais très reconnaissant de vos suggestions.

Merci d’avance pour votre aide.

Cordialement, Kenta

Médiat_Suprème

Voir ce site, par exemple : Multiplier de Grands Nombres - Multiplication - Calculatrice en Ligne (dcode.fr)
ou : Calculatrice de grands nombres - Calculatrices.app

Kenta

je suis désolé mais je ne comprends votre réponse.

SiouxLeger

https://www.dcode.fr/2-factors-decomposition

Kenta

merci pour le lien, je vais l'essayer 

Kenta

mince ! dommage ça ne marche pas.
Il me met 
(1125897758834689) invalid (superior to maximum expected 1000000000)

SiouxLeger

Par contre, il accepte des nombres plus grands quand on lui demande une décomposition en nombres premiers: https://www.dcode.fr/prime-factors-decomposition

Pour tes deux exemples: 1125897758834689=524287 × 2147483647 et 75058311923371=7 × 2500213 × 4288681.

Kenta

ah ouai super ! mais c'est bizarre qu'il ne trouve pas mon nombre...

Kenta

dommage que je ne sais pas programmer. je vais essayer de travailler avec chatgpt pour qu'il me fait un programme capable de factoriser un nombre nombre entier en produit de deux nombres.

Kenta

c'est bon, il a factorisé 
75058311923371 =7 × 2500213 × 4288681

Kenta

merci beaucoup.

Heuristique

Pour les petits calculs, j'utilise souvent Wolfram Alpha : https://www.wolframalpha.com/

nicolas.patrois

Dans Linux, on a l’outil factor :

> factor 1125897758834689
1125897758834689: 524287 2147483647
> factor 75058311923371
75058311923371: 7 2500213 4288681

Et voilà en une fraction de seconde.

Si tu veux une calculette qui le fait, il te suffit d’un exemplaire avec Python dedans, mais ça prendra plus de temps.

Kenta

merci les gars, vous êtes super. je ne sais pas programmer alors j'utilise chatgpt pour m'aider à coder un programme qui m'aiderai à factoriser des nombre de plus de 1000 chiffres.

Kenta

nicolas.patrois a dit :

Dans Linux, on a l’outil factor :

> factor 1125897758834689
1125897758834689: 524287 2147483647
> factor 75058311923371
75058311923371: 7 2500213 4288681

Et voilà en une fraction de seconde.

Si tu veux une calculette qui le fait, il te suffit d’un exemplaire avec Python dedans, mais ça prendra plus de temps.

merci beaucoup mais je ne connais pas l'os linux, j'utilise windows 11. Je cherche un programme efficace qui factorisera un nombre simple de plus de 1000 chiffres pour évaluer l'efficacité de l'algorithme. si je le fais avec une calculette de poche, ça me prendrai une dizaine de minute.

Kenta

Heuristique a dit :

Pour les petits calculs, j'utilise souvent Wolfram Alpha : https://www.wolframalpha.com/

merci heuristique, je vais essayer ton site.

Math Coss

Mille chiffres, ça me semble au-delà des possibilités des meilleurs logiciels.

gerard0

Bonjour.

Tu veux factoriser un nombre général de 1000 chiffres ? On ne connaît pas de méthode efficace. En 2020, le record de factorisation pour des produits d'entiers premiers de même taille était 250 chiffres. Avec une méthode super efficace et une énorme capacité de calcul.

Tu parles de coder, c'est donc que tu as un algorithme. Essaye de le tester sur 1403572498718577743 (mon logiciel Maple le factorise en 0,3 s), et si ça marche, essaie 140357244133814862620192135668294445784912528912046205482604154100059559486974771895816052344443017

On est encore loin des 1000 chiffres. Mais une algorithme efficace peut factoriser le produit de deux nombres d'environ 50 chiffres.

Cordialement.

Kenta

oui je sais, je sais que pour le moment c'est impossible de factoriser les nombres de plus de 1000 chiffres c'est pourquoi je ne veux que factoriser les nombres de plus de 1000 chiffres que si ces nombres sont issues d'un nombre de la forme  (2^x-1).  
Exemple : AxB=N, pour le moment je ne sais que factoriser N que si A et B sont de la forme (2^x-1)(2^y-1)=N pour tout x et y entiers positifs impairs

Kenta

Avec A et B sous cette forme là donnant un nombre à 1000 chiffres, serait très facile à factoriser avec un calculette de poche ; si elle permettait d'affiche 1000 décimales mais ce n'est pas possible pour les calculatrices actuelles. Du coup je pourrais le faire à la mains mais ce serait bien trop long, je dirais que cela me prendrais peut-être une bonne journée. C'est pourquoi je trouver un site factoriserait un nombre de 1000 chiffres, cela me permettrais de généraliser la factorisation quelque soit le forme de A et B.

Kenta

On m'avait dit qu'il était facile de factoriser de tel nombres quelque soit la taille, j'étais curieux alors j'ai cherché la méthode pour factoriser de tel nombre.

je vous remercie pour vos réponse, ça fait plaisir de discuter avec vous.

gerard0

Ah !

Alors ça n'a pas grand intérêt, il n'y a pas tellement de facteurs possibles pour N (disons moins de 350 pour un nombre de 1000 chiffres de la forme (2^x-1)*m; la moitié si les deux facteurs sont de cette forme ) et une recherche exhaustive est rapide : on essaie 2^2-1, puis 2^3-1, etc.

Kenta

gerard0 a dit :

Bonjour.

Tu veux factoriser un nombre général de 1000 chiffres ? On ne connaît pas de méthode efficace. En 2020, le record de factorisation pour des produits d'entiers premiers de même taille était 250 chiffres. Avec une méthode super efficace et une énorme capacité de calcul.

Tu parles de coder, c'est donc que tu as un algorithme. Essaye de le tester sur 1403572498718577743 (mon logiciel Maple le factorise en 0,3 s), et si ça marche, essaie 140357244133814862620192135668294445784912528912046205482604154100059559486974771895816052344443017

On est encore loin des 1000 chiffres. Mais une algorithme efficace peut factoriser le produit de deux nombres d'environ 50 chiffres.

Cordialement.

non, je ne pense pas encore savoir factoriser ce nombre, je ne l'ai pas encore étudier sa forme. Pour le moment, je ne sais que factorisé les nombre issue d'un produit tel que de deux nombre tel que A=(2^x-1) et B=(2^y-1)

Kenta

par contre je ne sais pas comment vous les mathématiciens, procédé pour réussir à factoriser de tel nombre.   

Heuristique

Voici un programme Python qui répond à ta question (je teste tous les $2^x-1$ par force brute).

import numpy as np

def factorise(n):
    for x in range(2,int(np.log2(n))):
        p = 2**x-1
        if n % p == 0:
            return(p,n // p)
    return(0,0)

Kenta

merci. Mais comment fonctionne ce programme ?  Je l'ai essayé sur python mais je ne sais pas le faire fonctionner (désolé je suis débutant sur python)

Je cherche un programme capable de décomposer un grand nombre en deux facteurs, où chaque facteur est un nombre premier de Mersenne de la forme

2^n−1

. Par exemple, si je rentre dans le programme le nombre 83076749736557232824108705158004737, il devrait être capable de me dire quelles sont les valeurs de n pour les deux nombres premiers de Mersenne qui, lorsqu’ils sont multipliés ensemble, produisent ce nombre.
Je suis particulièrement intéressé par la décomposition de nombres très grands, peut-être avec des milliers de chiffres, car nous avons découvert de très grands nombres de Mersenne. Ce programme me serait utile pour décomposer n’importe quel nombre ayant une grande quantité de chiffres et étant le produit de deux nombres premiers de Mersenne.”

En fait, je viens d'apprendre qu'on appelait ce type de nombre, nombre de Mersenne et je sais qu'il est facile de décomposer tout nombre très grand en produit de 2 nombres premiers à partir du moment qu'ils soient de cette forme.

Kenta

Heuristique a dit :

Voici un programme Python qui répond à ta question (je teste tous les $2^x-1$ par force brute).

import numpy as np

def factorise(n):
    for x in range(2,int(np.log2(n))):
        p = 2**x-1
        if n % p == 0:
            return(p,n // p)
    return(0,0)

par "force brute", ça veut dire qu'il test toutes les possibilités jusqu'à ce qu'il retrouve le nombre rentré ?

Heuristique

Si tu mets ce programme dans Python et que tu compiles, il te suffit ensuite de taper factorise($217$) pour que le programme renvoie $(7,31)$. Attention, le programme ne fonctionne que si le nombre en entrée est un produit de 2 nombres premiers de Mersenne !

gerard0

"par contre je ne sais pas comment vous les mathématiciens, procédé pour réussir à factoriser de tel nombre"

Si tu lisais vraiment les réponses qu'on te fait, tu saurais !!

Kenta

gerard0 a dit :

"par contre je ne sais pas comment vous les mathématiciens, procédé pour réussir à factoriser de tel nombre"

Si tu lisais vraiment les réponses qu'on te fait, tu saurais !!

haha oui désolé, effectivement tu avais expliqué, il essaye tout les nombres 2^n-1 en faisant évoluer jusqu'à ce qu'il trouve une valeur satisfaisante. 
Mais je pensais qu'il y avait d'autres méthodes sans tester autant de valeurs.

Kenta

Heuristique a dit :

Si tu mets ce programme dans Python et que tu compiles, il te suffit ensuite de taper factorise($217$) pour que le programme renvoie $(7,31)$. Attention, le programme ne fonctionne que si le nombre en entrée est un produit de 2 nombres premiers de Mersenne !

merci pour ton programme.

Kenta

merci pour votre aides à tous.

Kenta

Juste pour info, c'est bon j'ai réussi à faire mon programme pour factoriser le produit de 2 nombres de Mersenne !

pour un nombre de 1070 chiffres, le programme met 0.0s pour trouver A et B.
pour un nombre de 10701 chiffres, ça prend 0.58099s
pour un nombre de 107010 chiffres, ça prend 38.37s
154037 = 63.34s
170984 = 108.34s
218371 = 182.76s
317404 = 433.48s

C'est fou comment le temps de calcul augmente au fur et à mesure que la tailles du nombre augmente.
Je vais voir combien de temps le programme va mettre pour factoriser un nombre de 1 000 000  de chiffres.

Kenta

Kenta

voilà, difficile de trouver un algorithme plus rapide et mon programme ne me permet pas de rentrer des nombre ayant plus de 999 999 chiffres.

Heuristique

Je pense qu'on peut largement optimiser le temps de calcul d'un programme par force brute. Avant de s'embêter à réfléchir à gagner du temps et gérer des entiers plus grands, simples questions : pourquoi vouloir factoriser de tels entiers à 1 million de chiffres ? Et pourquoi vouloir un programme efficace pour faire cela ?

Pour la factorisation d'entiers, je comprends, mais pour factoriser un produit de Mersenne, je ne vois pas vraiment...

Kenta

C'est un amusement personnel. Améliorer ce temps de factorisation de nombre simple me permet d'optimiser le calcul et voir si ma méthode de factorisation d'un nombre est plus que de passer par la force brut. Si j'arrive à rendre le calcul plus rapide que la force brut, je l'étendrai pour factoriser les nombre issue d'un produit de 2 nombre A et B qui est soit un nombre de Mersenne ou soit un nombre de fermat quelconque.

Kenta

• Avoir un programme de calcul rapide pour des nombres aussi simples sera moins long si on lui demande factoriser d'autre nombre plus complexe.  Je voulais juste partir sur une bonne base.

lourrran

Ce n'est pas plus rapide que la force brute, c'est la force brute. 
Tu dis : j'ai un nombre. Je sais que ce nombre est le produit de 2 nombres extraits de telle liste (Mersenne... ou une autre). Et donc, tu testes 1 par 1 tous les nombres de la liste (Mersenne), et tu regardes si la division tombe juste.  C'est la force brute, on teste tous les candidats.

Kenta

Ok merci pour l'explication. C'est ça que je ne comprends pas, si par la force brute, il doit tester tous les nombres d'une liste précise, il devra tester un paquet de nombre et comparer un paquet de résultat avant d'arriver au bon produit. Surtout si le nombre possède 1 000 000 de chiffres.
Ma méthode consiste simplement à résoudre une simple équation pour ce type de nombre. Il ne teste même pas un quelconque nombre ni même comparer un seul résultat et pourtant le programme ne factorise pas plus vite que le force brute.

L'intérêt pour moi est de tester les deux méthodes et voir à partir de quel taille de nombre, l'algorithme est la plus efficace, d'où le besoin de pousser le programme dans ses limites.

Kenta

Mais je commence à comprendre la simplicité pour un programme de factoriser par la force brute de tel nombres. Si je comprends bien, pour un nombre issure d'un produit de deux nombre de mersenne d'un million de chiffres, il devra faire moins de 1900 000 opérations pour trouver les deux valeurs, ce n'est pas énorme pour un ordinateur. 

gerard0

Mais non, la force brute, dans ce cas est rapide. Tu dis "il doit tester tous les nombres d'une liste précise, il devra tester un paquet de nombre et comparer un paquet de résultat avant d'arriver au bon produit." Pas "un paquet de résultat", seulement quelques divisions. Par exemple, pour un million de chiffres, les nombres de Fermat ne sont que 21 puisque le 22-ième nombre de Fermat a 1 262 612 chiffres.

Kenta

D'accord donc pour les nombres de fermat, ce ne sera pas intéressant de comparer un algorithme de force brute contre un aldorithm qui la résout quelques équations pour trouver le produit AxB. 
Mais pour les nombres de mersennes de type 2^n-1, il doit quand même tester un paquet avant d'arriver au million de chiffres,  c'est pour çà que je voulais savoir s'il était plus intéressant de trouver des équations qui résoudraient une factorisation ou s'il serait mieux de tester chaque nombre.

gerard0

À priori, un programme qui calcule directement est plus intéressant, c'est par exemple ce qu'on fait pour trouver les plus grands nombres premiers, parmi les nombres de Mersenne. Mais trouver une méthode qui factorise des produits de nombres de Mersenne n'a aucun intérêt mathématique; tout au plus la démonstration de la méthode peut faire un petit exercice d'arithmétique. Il n'y a aucune utilisation des produits de nombres de Mersenne, qui d'ailleurs ont souvent une décomposition en facteurs premiers facile. Et ça peut faire, pour toi, un petit exercice de programmation.

Puis tu pourras sans doute étudier plus sérieusement l'arithmétique et la théorie des nombres pour t'attaquer à des problèmes sérieux.

Cordialement.

Kenta

Oui exactement, c'est juste pour m'exercer un peu en programmation. Mais en fait, les équations qui me permettent de factoriser directement le produit de deux nombres de mersennes ne sont qu'une partie des équations,  je les aient étendu à d'autres nombres de forme (2^(2n+1)-1)/(2^n-1)), ce qui veut dire que A et B peuvent être, soit de la forme 2^n-1, soit de la forme (2^(2n+1)-1)/(2^n-1)), ce qui va amplifier la difficulté à factoriser un nombre. J'ajouterais petit à petit d'autres forme pour voir à quelle taille de chiffre le programme ralentira de manière drastique (bien sûr en résolvant de manière direct). 

Kenta

.