Forum de mathématiques - Bibm@th.net

Matou

Invité

Re : Decouverte Factorisation (nombres premiers

Bonjour,

Si on resume :
Soit $p$ un produit à décomposer.
On pose $d=7$ (on va quand même travailler avec des entiers).
Pour décomposer $p$, on divise $2 \cdot p$ par tous les nombres de la forme $d + 6 \cdot i$ où $i$ est un entier, jusqu'à obtenir un quotient entier.
Comme on n'obtient pas tous les nombres premiers avec $d + 6 \cdot i$, j'imagine qu'on choisit d'autres valeurs pour $d$ et qu'on recommence...
Bref, on obtient une version dégradée de l'algorithme banal qui consiste à diviser par l'ensemble des nombres premiers inférieurs à $\sqrt{p}$.

Matou

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

avec modestie
cette methode je l'est appelé (1,25+1,5) (3,5+3)
mais avant de clarifier ,je suis entarain de chercher quelq'un pour lui confié mes travaux et je laisse à lui de les soumettre à une revue spécialisée qui pourra me permettre de garder le secret tout en validant la méthode (puis la diffuser ensuite)
mais pourquoi pas un membre de ce forum

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

et si python en lui donne une carte ou un tableau des nombres premiers

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

RE,

et si python en lui donne une carte ou un tableau des nombres premiers

Là, je ne comprends pas ce que tu veux...

Mais je sais pourquoi tu n'as demandé que des nombres à 9 ou 10 chiffres : faire ça avec un tableur t'obligerait à utiliser beaucoup trop de lignes et te demanderait trop de temps.

Je viens de tester mon script avec trois produits l'un de 11 chiffres, l'autre de 13 chiffres et un de 14 : ça fonctionne au-delà de 10 chiffres...
-------------------------------------------------------------------

Nombre à décomposer : 42 676 492 303

Le 1er quotient entier a été obtenu par 42676492303/(3.5+3*20575)
42676492303/61728.5 = 691358.0
691358/2 = 345679
42676492303/345679 = 123457

               -- Factorisation --
        42676492303 = 345679 x 123457

Après quand même 20575 additions et autant de multiplications et divisions !!

-----------------------------------------------------------------------------------

         Nombre à décomposer : 1 539 248 135 363

Le 1er quotient entier a été obtenu par 1539248135363/(3.5+3*20760)
1539248135363/62283.5 = 24713578.0
24713578/2 = 12356789
1539248135363/12356789 = 124567

               -- Factorisation --
        1539248135363 = 12356789 x 124567

Après quand même 20760 additions et autant de multiplications et divisions !!

--------------------------------------------------------------------------------------------------

         Nombre à décomposer : 29 493 048 060 521

Le 1er quotient entier a été obtenu par 29493048060521/(3.5+3*397797)
29493048060521/1193394.5 = 24713578.0
24713578/2 = 12356789
29493048060521/12356789 = 2386789

               -- Factorisation --
        29493048060521 = 12356789 x 2386789

Après quand même 397797 additions et autant de multiplications et divisions !!

                 ------------------------------------------------------

Pour ce dernier produit, l'affichage n'a pas été instantané, il y a eu un petit délai de l'ordre de la demi-seconde...

@+

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

tres bien
je vien d'essayer 135310597297

avec la dividio sur187755,5
ça donne 720674
divisé par 2 egale
360337
l'autre est 375511

mon  probleme c'est que la matrice n'accepte pas plus de 12 chiffres elle ecrit des symbole

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

pour le 61728.5 dans le 1er exemple est ce que tu recomence des le debut ou tu dedui 3 du 61728,5 puis tu remet +3

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

Re,

Pour le 61728.5 dans le 1er exemple est ce que tu recomence des le debut ou tu dedui 3 du 61728,5 puis tu remet +3

Pour chaque essai je suis reparti du début...

J'ai un souci avec 135310597297
J'ai d'abord trouvé que :
135310597297 = 220735069 x 613 
613 étant premier, j'ai testé 220735069 et obtenu 220735069 = 114193 x 1933.
Donc 220735069 n'était pas premier. Bizarre : tu as bien dit que ta décomposition donnait le produit de 2 nombres premiers, non ?
Enfin :
135310597297  = 114193 x 1933  x 613 avec 114193, 1933 et 613 premiers...
Or tu as écrit que 135310597297 = 360337 x 375611 (premiers)

Là, j'ai été très surpris : la décomposition en facteurs premiers est unique !!!

J'ai passé du temps à chercher où était l'erreur !
Et bien, elle est là : 360337 x 375611= 135310597207

Alors, j'ai testé ...
Surprise... Ca ne marchait pas ! Mon script tourne dans le vide !
Alors j'ai essayé l'algorithme de Rho-Pollard : il ne tourne pas dans le vide mais s'arrête comme si 135310597207 était premier...
J'ai essayé sur le site dcode.fr : pas de résultat !

Quel nombre as-tu réellement utilisé ?
Soit mon script a une erreur parce que j'ai mal interprété les images de ta video muette, soit ta méthode présente un problème...

@+

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

essaye le 1,25 +1,5 au lieu 3,5+3
je vais vérifier

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

tu a fait cela tu a chercher dans le net tu a trouvé la factorisation suivante
135310597297=613x1933x114193
tu a multiplier (1933x114193)x613
ça ne marche pas
essaye une autre fois

Matou

Invité

Re : Decouverte Factorisation (nombres premiers

Bonsoir,

Sauf erreur de ma part, avec GeoGebra, sur mon téléphone, j'ai :
360337*375611=135346540907

Et, toujours avec GeoGebra 135310597207 apparaît comme un nombre premier.

Cordialement

Matou

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

Bonsoir,

Non, je n'ai pas eu besoin d'Internet  pour décomposer 135310597297 : tu m'insultes ou tu ne comprends pas ce que tu lis ?
Sur Internet, j'ai cherché, mais pas trouvé, la décomposition de 135310597207, Matou nous dit pourquoi.

En ce qui concerne le nombre 135310597297 que toi tu as dit avoir essayé (voir ton post #30), voilà ci-dessous la preuve de ce que j'ai fait sans Internet, par copie d'écran :

Nombre à décomposer : 135310597297

Le 1er quotient entier a été obtenu par 135310597297/(3.5+3*101)
135310597297/306.5 = 441470138.0
441470138/2 = 220735069
135310597297/220735069 = 613

               -- Factorisation --
        135310597297 = 220735069 x 613

Après quand même 101 additions et autant de multiplications et divisions !!

============ RESTART: C:\Python38\Progs_persos\V3.x\Factoriser_produit de 2 premiers.py ============
         Nombre à décomposer : 220735069

Le 1er quotient entier a été obtenu par 220735069/(3.5+3*321)
220735069/966.5 = 228386.0
228386/2 = 114193
220735069/114193 = 1933

               -- Factorisation --
        220735069 = 114193 x 1933

Après quand même 321 additions et autant de multiplications et divisions !!

Donc on a bien : 135310597297 = 220735069 x 613 = 114193 x 1933 x 613
Tu veux l'adresse d'un site où tu pourras par simple copier/coller du script, tu pourras reproduire ce que tu vois dans le cadre ci-dessus ?
Moi, je dispose de Python v. 3.8 installé sur ma machine : je programme souvent, et des scripts compliqués que tu ne saurais pas reproduire sur ton tableur...

tres bien
je viens d'essayer 135310597297:

   
360337*375511 = 135 310 507 207  et non 135 310 597 297

Maintenant, je vais tester 135310507207, le bon nombre:

Nombre à décomposer : 135310507207

Le 1er quotient entier a été obtenu par 135310507207/(3.5+3*60055)
135310507207/180168.5 = 751022.0
751022/2 = 375511
135310507207/375511 = 360337

               -- Factorisation --
        135310507207 = 375511 x 360337

Après quand même 60055 additions et autant de multiplications et divisions !!

Mais alors où était l'erreur ?
Simple : je n'avais pas testé le bon nombre
Voir #32...

Il n'en reste pas moins que
1. 375511 x 360337 =135310507207 et non 135310597297 comme tu l'as écrit dans ton post #30
2. ça, si tu confirmes ce que je comprends, c'est n'importe quoi :   

   
    tu a fait cela tu a chercher dans le net tu a trouvé la factorisation suivante
   135310597297=613x1933x114193
   tu a multiplier (1933x114193)x613
   ça ne marche pas (*)

613 x 1933 x 114193 et (1933 x 114193) x 613 donnent le même résultat : la multiplication est associative et commutative...

3. Le nombre que j'avais testé posait un problème parce que premier (merci Matou)

Mais je suis rassuré : mon script Python n'a pas d'erreur...

@+

[EDIT]
(*) Si, ton "ça ne marche pas", veut dire que $613 \times 1933 \times 114193  \neq (1933\times 114193) \times 613$ tu n'as qu'à calculer les 2 (moi je n'ai pas besoin de calculs)...
Mais j'espère que tu t'es mal exprimé !

- Sans calculs -
Je mets des parenthèses : Associativité de la multiplication.
$613 \times 1933 \times 114193 = (613 \times 1933) \times 114193$ :

Dans les parenthèses, j'intervertis 613 et 1933 : Commutativité de la multiplication
$(613 \times 1933) \times 114193 = (1933 \times 613) \times 114193$

Je déplace les parenthèses : Associativité de la multiplication
$(1933 \times 613) \times 114193 = 1933 \times (613 \times 114193)$

Dans les parenthèses, j'intervertis 613 et 114193 : Commutativité de la multiplication
$1933 \times (613 \times 114193) = 1933 \times (114193 \times 613)$

Je redéplace les parenthèses : Associativité de la multiplication
$1933 \times (114193 \times 613) = (1933 \times 114193) \times 613$

CQFD

Ce que j'ai appris il y a bien longtemps, avant de connaître les propriétés d'Associativité ou Commutativité, avec cette simple règle :

Un produit de facteurs est indépendant de l'ordre de ses facteurs.

@+

Dernière modification par yoshi (19-05-2023 10:31:00)

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

bonjour
je voudrais savoir avec le programe python pour decomposer un nombre en deux facteurs premier  combien faut il du temps , utilisez une autre methode que 3,5+3 et montre nous le resultat de la machine , un nombre de  13 chiffres par exemple
ça m'interesse de le saovoir
et est ce qu'il scan ou il te donne directement les deux nombre?
et excuse moi ce n'est une insulte

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

https://fr.quora.com/Y-a-t-il-une-suite … s-premiers
Y a-t-il une suite logique des nombres premiers ?
la reponse OUI
je l'ai entre mes mains

Wiwaxia

Membre

Lieu : Paris 75013

Inscription : 21-12-2017

Messages : 438

Re : Decouverte Factorisation (nombres premiers

Bonjour,

https://fr.quora.com/Y-a-t-il-une-suite … s-premiers
Y a-t-il une suite logique des nombres premiers ?
la reponse OUI
je l'ai entre mes mains

Là, je brûle de curiosité et voudrais bien savoir laquelle, s'il ne s'agit pas d'un algorithmique apparenté au crible d'Eratosthène ...
Si tu penses à l'une des formules citées dans l'article de Wikipedia
https://fr.wikipedia.org/wiki/Formules_ … de_Rowland
on peut douter de leur intérêt pratique !

PS: la factorisation 135310597297 = 613x1933x114193
s'obtient aussi sur une calculatrice programmable.
Python peut évidemment décomposer des nombres beaucoup plus grands, et beaucoup plus vite.

Dernière modification par Wiwaxia (20-05-2023 08:39:57)

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

tu le dois mais ,en presence d'un jurés en mathématique
ou une revue en mathématique gerer par des chercheures reconus
la mienne est pratique

Wiwaxia

Membre

Lieu : Paris 75013

Inscription : 21-12-2017

Messages : 438

Re : Decouverte Factorisation (nombres premiers

tu le dois mais ,en presence d'un jurés en mathématique
ou une revue en mathématique gerer par des chercheures reconus ...

Je vais donc être contraint de rester sur ma faim ... Dur, dur ...

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

tu seras le premier à le savoir

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

connaissez  vous un moyen pour connaître si un nombre est un produit de la multiplication de 2 nombres premier surtout quand il est grand

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

Bonjour,

je voudrais savoir avec le programe python pour decomposer un nombre en deux facteurs premier  combien faut il du temps , utilisez une autre methode que 3,5+3 et montre nous le resultat de la machine , un nombre de  13 chiffres par exemple
ça m'interesse de le saovoir
et est ce qu'il scan ou il te donne directement les deux nombre?

Pourqoui cette question ?
Tu as pourtant tout ce qu'il te faut pour ça :
- le script écrit en Python qui est un langage clair et simple à lire et comprendre,
- les explications détaillées qui permettent de suivre ce qu'il fait en prenant un stylo et une feuille de papier
- ce que le programme écrit à l'écran, qui est aussi détaillé,
- Et last but not least, je t'ai déjà dit que j'avais adapté la méthode de ta video en Python...

Alors ?

Puisque ça ne te suffit pas, voilà un exemple où j'ai rajouté une ligne pour qu'il écrive TOUS LES calculs préparatoires :

          Nombre à décomposer : 4453

 3.5  1272.2857142857142
 6.5  685.0769230769231
 9.5  468.7368421052632
12.5  356.24
15.5  287.2903225806452
18.5  240.7027027027027
21.5  207.11627906976744
24.5  181.75510204081633
27.5  161.92727272727274
30.5  146.0

Le 1er quotient entier a été obtenu par 4453/(3.5+3*9)
4453/30.5 = 146.0
146/2 = 73
4453/73 = 61

               -- Factorisation --
        4453 = 73 x 61

Après quand même 9 additions et autant de multiplications et divisions !!
Temps 0.097 s

Et le script s'arrête dès qu'on obtient un quotient entier.

Malheureusement, au delà de 15 chiffres, le script produit n'importe quoi.
J'ai trouvé pourquoi : trop de chiffres après la virgule et Python les stocke sous la forme exponentielle.
Je pense pouvoir contourner le problème : j'ai pu obtenir, il y a déjà un certain temps, 25000 décimales pour le nombre d'or en 2 à 3 min avec la méthode de Heron d'Alexandrie pour le calcul de $\sqrt 5$... Je vais voir comment faire dans ton cas très particulier.

Pour répondre à ta dernière question la méthode la plus connu est l'algorithme Rho-Pollard (relativement simple)
Après, tu peux jeter un œil là-dessus :
https://www.bibmath.net/crypto/index.ph … ctoentiers
Méthode de Rho-Pollard :
https://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard

@+

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

si ma methode comme tu l'a precisé est efficace pourquoi ne pas lui donner un nom et la difusser pour que les gens en benifice
je vois que ça marche bien comme dans le tableur
pour le probleme de 15 chiffres la société qui fabrique pythons lui fait maintenance après declaration
pour le message 43 j'ai pas eu de reponse
avec un grand chiffre de10 combien de temps pour décomposer?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

RE,

Avec un nombre de 14 chiffres :

Nombre à décomposer : 29493048060521

Le 1er quotient entier a été obtenu par 29493048060521/(3.5+3*397797)
29493048060521/1193394.5 = 24713578.0
24713578/2 = 12356789
29493048060521/12356789 = 2386789

               -- Factorisation --
        29493048060521 = 12356789 x 2386789

Après quand même 397797 additions et autant de multiplications et divisions !!
Temps : 0.248 s

@+

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

je voudrais connaitre la factorisation de ces 2 nombres avec le programme
14 chiffres 13472900573921
15 chiffres 130062255272767
chez moi le tableur fait des erreure au niveau de la virgule il l'arrondie  4,99 à5

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Decouverte Factorisation (nombres premiers

Salut,

Nombre à décomposer : 13472900573921

Le 1er quotient entier a été obtenu par 13472900573921/(3.5+3*611731)
13472900573921/1835196.5 = 7341394.0
7341394/2 = 3670697
13472900573921/3670697 = 3670393

               -- Factorisation --
        13472900573921 = 3670697 x 3670393

Après quand même 611731 additions et autant de multiplications et divisions !!
Temps 0.33 s

A priori, mon script, donc ta méthode échoue échoue à factoriser 130062255272767.
L'algorithme  Rho-Pollard donne : 11404301 * 11404667

@+

FAIZE852

Membre

Inscription : 28-12-2022

Messages : 89

Re : Decouverte Factorisation (nombres premiers

merci
génial

Matou

Invité

Re : Decouverte Factorisation (nombres premiers

Bonjour,

C'est ce que je disais au post#26.
L'algorithme suppose que les diviseurs premiers sont de la forme $6 \cdot i +7$.
Or ce n'est pas le cas de 11404301 ni de 11404667.

Il faut donc utiliser l'autre formulation proposée par FAIZE852 (celle qu'il baptise 1.25 +1.5) puisque les deux diviseurs sont de la forme $6 \cdot i +5$.

Cela amène plusieurs réflexions :
1- A priori, avec ces deux méthodes, on essaye tous les diviseurs premiers (sauf erreur de ma part).
2 - Ce n'est guère pratique de devoir essayer une formulation, puis l'autre si la première ne donne rien. Quand on passe à des chiffres un peu plus grands, on perd beaucoup de temps
3 - Pourquoi aller dans le domaine des nombres à virgule alors qu'on veut travailler sur des entiers ; id est, pourquoi se priver de la fonction modulo qui est très rapide dans tous les langages de programmation ?

Cordialement

Matou