Factorisation sans utilisation de nombres premiers comme diviseurs

[invite02dd6e78]

Bonjour,

Quelqu'un peut'il me dire si cela représente un intérêt quelconque à factoriser un nombre entier naturel sans avoir besoin d'un liste des nombres premiers à hauteur de sa racine carrée.

merci d'avance pour vos réponses

gg
-----

[phys4]

Bonsoir,
La factorisation avec des nombres non premiers sera d'un intérêt limité pour les démonstrations, car cette décomposition n'aura pas la propriété d'unicité des nombres premiers.
Cela pourrait être un moyen intermédiaire pour accéder à la factorisation en nombres premiers, si un moyen génial pour faire cette factorisation aisément.

[invite4492c379]

tu parles bien de factoriser en facteurs premiers un nombre sans avoir à disposition une liste de premiers inférieurs à sa racine carrée.

avantage :
ne pas avoir besoin de disposer d'une telle liste de premiers, disposer signifiant la précalculer, la conserver en mémoire, etc ...

[invite02dd6e78]

merci photon57

oui c'est bien ça,

n= 534 446 174 677 871
me renvoi: 23 154 143 * 23 082 097

mon objectif est de factoriser un grand nombre naturel produit de 2 grands nombres premiers.

malheureusement j'utilise Excel et je suis limité à 15 chiffres, mes tests sont probants pour n=15 chiffres

peut-tu me confirmer que logiquement cela devrais valoir pour n= 50 ou 100 chiffres et me dire si il existe un tableur qui peut gérer des nombres +> que 15 chiffres (Je ne sais pas programmer)

merci encore

[A voir en vidéo sur Futura]

[invite02dd6e78]

Bonjour phys4,

en faite j'aurais du dire que je n'utilise que des nombres entiers naturels

dont la congruence est # de 0 dans modulo 2, 3 et 5
par exemple :

n= 534 446 174 677 871
me renvoi: 23 154 143 * 23 082 097

mon objectif est de factoriser un grand nombre naturel produit de 2 grands nombres premiers.

malheureusement j'utilise Excel et je suis limité à 15 chiffres, mes tests sont probants pour n=15 chiffres

peut-tu me confirmer que logiquement cela devrais valoir pour n= 50 ou 100 chiffres et me dire si il existe un tableur qui peut gérer des nombres +> que 15 chiffres (Je ne sais pas programmer)

merci encore

[invite4492c379]

merci photon57

oui c'est bien ça,

n= 534 446 174 677 871
me renvoi: 23 154 143 * 23 082 097

Qu'est-ce qui te renvoie ça ?

mon objectif est de factoriser un grand nombre naturel produit de 2 grands nombres premiers.

malheureusement j'utilise Excel et je suis limité à 15 chiffres, mes tests sont probants pour n=15 chiffres

Comment effectues-tu tes tests ?

peut-tu me confirmer que logiquement cela devrais valoir pour n= 50 ou 100 chiffres et me dire si il existe un tableur qui peut gérer des nombres +> que 15 chiffres (Je ne sais pas programmer)

merci encore

Tout dépend de ta méthode. Tu as un algo ? Il y a des algorithmes sophistiqués pour factoriser de grands nombres. Si tu ne programmes pas ça va être difficile. Les tableurs ne sont pas la panacée ...

[kaderben]

Bonjour

Ta decomposition est fausse Ggharissa

n= 534 446 174 677 871
n= 23082097 * 23154143
Ma calculette "Voyage 200" l'a fait en 10 secondes
Mais sûrement elle ne fait pas les grands nombres

[invite02dd6e78]

tu m'as fais peur

je ne voudrais pas faire de faute de frappe c'est déjà très gentille de votre part

de répondre à mes questions.

du coup j'ai refait le calcul .

ouf..... c'est bien ça.

peut être que ta calculette avait un chiffre en mémoire ou que sa capacité et inférieure à 14 chiffres?

merci

[Tryss]

Heu kaderben... sa décomposition est exactement la même que la tienne, juste dans l'ordre inverse -_-'

[invite02dd6e78]

pas de problème,

je sais que le nombre d'opérations pour factoriser un nombre de 15 chiffres est rapide, mais plus le nombre de chiffre

est grand 50, 100 ou 200 plus le nombre d'opération augmente de façon vertigineuse (exponentiel)

C'est pourquoi j'ai travaillé 3 ans pour trouver cette méthode

À ta connaissance y a t'il un tableur qui prend en charge des nombres plus grand que 15 chiffres.

merci


gg

[invite4492c379]

pas de problème,

je sais que le nombre d'opérations pour factoriser un nombre de 15 chiffres est rapide, mais plus le nombre de chiffre

est grand 50, 100 ou 200 plus le nombre d'opération augmente de façon vertigineuse (exponentiel)

C'est pourquoi j'ai travaillé 3 ans pour trouver cette méthode

À ta connaissance y a t'il un tableur qui prend en charge des nombres plus grand que 15 chiffres.

merci


gg

Un tableur ça va être difficile, mais si tu as une méthode elle doit être programmable. Si tu nous l'explique on pourra en tirer un algorithme, en calculer la compléxité et finalement le programmer.

[invite02dd6e78]

bonsoir photon57

Qu'est-ce qui te renvoie ça ?
Comment effectues-tu tes tests ?

J'ai implémenté une série de calcul qui s'enchevêtrent, mais j'avoue avoir mis près de 3 ans pour y arriver.

bien que depuis plusieurs mois j'ai obtenue des résultats beaucoup moins rapide bien que dans la même ligne
de pensé

donc dans mon fichier je rentre le nombre que je veux factoriser et j'effectue une recherche

dans ma feuille de calcul de ce nombre et en regard de celui-ci j'ai le multiplicande et le multiplicateur.

ça ne dure qu'une fraction de seconde

Je sais que les tableurs ne sont pas la panacée ... mais je ne peux tout de même pas donner le fruit de mon travail

à je ne sais qui......

en plus je suis persuadé que casser un grand nombre serais très rapide et je te laisse imaginais la suite....

c'est pourquoi je voudrais savoir si il existe un tableur qui peut prendre en charge des nombres +> que 15 chiffres

merci de me dire si à ta connaissance il en existe.

encore merci

[invite4ef352d8]

Bonjour,


un tel algorithme est effectivement interessant, mais il y en a déjà plusieurs !

il existe des algorithme de factorisations infiniement plus subtile et plus efficace que de juste tester tout les nombres premier jusqu'à en trouver un qui fonctionne.

les exemples classiques :

http://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard
http://fr.wikipedia.org/wiki/Factori...que_de_Lenstra

[invite4492c379]

bonsoir photon57

Qu'est-ce qui te renvoie ça ?
Comment effectues-tu tes tests ?

J'ai implémenté une série de calcul qui s'enchevêtrent, mais j'avoue avoir mis près de 3 ans pour y arriver.

bien que depuis plusieurs mois j'ai obtenue des résultats beaucoup moins rapide bien que dans la même ligne
de pensé

donc dans mon fichier je rentre le nombre que je veux factoriser et j'effectue une recherche

dans ma feuille de calcul de ce nombre et en regard de celui-ci j'ai le multiplicande et le multiplicateur.

ça ne dure qu'une fraction de seconde

Je sais que les tableurs ne sont pas la panacée ... mais je ne peux tout de même pas donner le fruit de mon travail

à je ne sais qui......

en plus je suis persuadé que casser un grand nombre serais très rapide et je te laisse imaginais la suite....

c'est pourquoi je voudrais savoir si il existe un tableur qui peut prendre en charge des nombres +> que 15 chiffres

merci de me dire si à ta connaissance il en existe.

encore merci

Malheureusement je ne pense pas qu'un tel tableur existe ...
Il va falloir que tu te mettes à un langage de programmation qui te propose des entiers sans limite de taille ou des logiciels mathématiques qui travaillent aussi avec des entiers longs.

[invite02dd6e78]

bonsoir Ksilver

je n'utilise pas les nombres premiers

gg

[invite02dd6e78]

merci de ta promptitude

peut tu me recommander un langage qui peut traiter des entiers sans limite de taille

et qui ne soit pas trop difficile à apprendre pour un néophyte

ou un logiciel mathématique qui travaillent avec des entiers longs.

merci

[invite4492c379]

Je te dirais que pour commencer il ne faut ni chercher à apprendre un langage, ni chercher à apprendre un logiciel.
La première chose à faire est d'écrire en Français sur du papier ce que tu fais faire à ton tableur. Il faut que tu décrive ta méthode en Français en des termes simples. Cette étape est indispensable et cruciale.

Une fois cela fait tu pourras essayer de le «programmer» ou de le faire avec un autre logiciel.
Tous les langages modernes ont des bibliothèques qui vont te permettre de manipuler des entier dont la taille ne sera que limité par la mémoire disponible sur ton ordinateur (C, Java, C++, C#, ...).
Je ne peux te conseiller pour un logiciel dédié, sur wikipedia il y a une liste de logiciels : http://en.wikipedia.org/wiki/Comparison_of_computer_algebra _systems#Functionality
Je suppose que ceux qui ont YES dans la colonne "Arbitrary precision" vont convenir. Mais je ne peux te conseiller celui qui conviendrait le mieux.

Je peux aussi te conseiller de lire ce qui a déjà été fait sur le sujet, autant les algo proposés par KSilver, que les algorithme que tu peux trouver dans des tutoriels basiques.

[invite02dd6e78]

merci photon57

je vais suivre tes conseilles et te tiendrais au courant

un grand merci encore

[invite986312212]

ou un logiciel mathématique qui travaillent avec des entiers longs.

Mathematica (cher) ou R (gratuit)

[invite4ef352d8]

que veux tu dire par "je n'utilise pas les nombres premiers" ?

savoir factoriser un nombre, ou le factoriser en facteur premier algorithmiquement c'est la même chose : si tu recommence ton algo plusieur fois sur les facteurs que tu obtiens tu fini par trouver les facteurs premiers. d'ailleur les algo que j'ai présenté ne factorise en général pas en facteur premier. la problématique est "si j'ai un nombre n, je veux trouvé un diviseur de n autre que 1 et n "


mais dans aucun de ces algorithmes il n'est questions d'utiliser une liste préalable de nombre premier connu pour faire la factorisation (de toute facon, vu la taille des nombres qu'on espère pouvoir factoriser ca serait illusoire d'espérer en avoir une... )

[kaderben]

Bonjour Tryss
Mais bien sûr, je n'ai pas fait attention
Maintenant si je ne sais même pas que 2x3=3x2, alors c'est grave !