Algorithme de Factorisation des nombres entiers

[invite5f4c1fbb]

bonjour,

j'ai suivi toute votre discussion au sujet de la formule de factorisation.
voila il y a justement quelques temps j'ai trouvé une formule très simple qui décompose un nombre entier naturel en facteurs premiers.
la formule est très simple et donne plus rapidement les facteurs recherchés , elle est basée sur le pgcd de 2 nombres tirés du nombre principal à décomposer.
son algorithme est très simple en c++ ou autre langage.

Je cherche à la diffuser, mais je cherche une protection d'auteur.

sincères salutations

Lakar
-----

[invite0972ca96]

Ha!

Je devais justement trouver les facteurs premiers de 102050453336283356511749312933 957026394713441987997211105331 797172566876636264982102509592 1

je n'y arrive pas§ Peux tu me les trouver grace à ta formule s'il te plait?

merci

[invite5f4c1fbb]

Ha!

Je devais justement trouver les facteurs premiers de 102050453336283356511749312933 957026394713441987997211105331 797172566876636264982102509592 1

je n'y arrive pas§ Peux tu me les trouver grace à ta formule s'il te plait?

merci

Bonjour,

Merci pour votre intérêt, je vous informe que je peux pas satisfaire votre souhait, c'est pas à cause que ma formule ne peut le faire, mais c'est que je ne suis pas équiper pour les grands nombres.
La formule est sûr . mais elle diffère des autres formules à division successive c'est que le nombre qu'on vérifie sa primalité ou non est réduit et il doit être pair.
Désolé

salut

[anthony_unac]

bonjour,

j'ai suivi toute votre discussion au sujet de la formule de factorisation.
voila il y a justement quelques temps j'ai trouvé une formule très simple qui décompose un nombre entier naturel en facteurs premiers.
la formule est très simple et donne plus rapidement les facteurs recherchés , elle est basée sur le pgcd de 2 nombres tirés du nombre principal à décomposer.
son algorithme est très simple en c++ ou autre langage.

Je cherche à la diffuser, mais je cherche une protection d'auteur.

sincères salutations

Lakar

Bonjour,

Vos formules permettent elles de factoriser la somme de deux puissancielles successives ?
Mettons pour fixer les idées.

Cordialement
Anthony

[A voir en vidéo sur Futura]

[invite0972ca96]

d'accord d'accord mais votre formule ne vaut rien mon cher!

[invite5f4c1fbb]

d'accord d'accord mais votre formule ne vaut rien mon cher!

bonsoir

pourquoi ma formule ne vaut rien?
quelle est la meilleure formule de décomposition en facteurs premiers la plus simple actuellement .

avec ma formule, on exploite une variable que personne n'a jamais exploitée sérieusement inédite.

salut

[invite5f4c1fbb]

bonsoir

pourquoi ma formule ne vaut rien?
quelle est la meilleure formule de décomposition en facteurs premiers la plus simple actuellement .

avec ma formule, on exploite une variable que personne n'a jamais exploitée sérieusement inédite.

salut

bonjour,

j'ajoute pour complément d'information:

Avec ma procédure je décompose par exemple :

N=2303 = 47x49 , à la première opération je trouve le 1er facteur 47

N=493 =17x28 , à la 2ème opération je trouve 17

N= 1943 = 29x67 , à la 7ème opération

N= 57439349 = 5819x9817 à 880 opérations je 5819.

Pouvez me dire la différence si on divise N par les nombres impairs inférieurs à la racine carrée?

moi , je trouve une nette différence.
et si je travaille avec le pgcd, quelque fois on trouve le 1er facteur plus rapidement.

Salut

[taladris]

c'est que le nombre qu'on vérifie sa primalité ou non est réduit et il doit être pair.

si on ne peut tester que la primalité d'un nombre pair, l' "algorithme" a peu d'intérêt

[invite5f4c1fbb]

bonjour,

si on peut aussi vérifier avec les nombres impairs

Salut

[WizartS]

La formule est sûr . mais elle diffère des autres formules à division successive c'est que le nombre qu'on vérifie sa primalité ou non est réduit et il doit être pair.

Bonjour!...

Ou j'ai rêvé (vu l'heure tardive, ça pourrait paraître normal), ou il l'a vraiment écrit!... (Le nombre dont on vérifie la primalité doit être paire??)

Lakar, s'il te plait, j'aimerais un peu de sérieux sur mon fil de discussion, ou tu peux, et ce serait préférable, ouvrir un nouveau fil de discussion à ce sujet. D'avance, merci!

W's

[invite5f4c1fbb]

Bonjour,

Excusez moi, peut etre j'ai mal exprimé.
Je voulait dire qu'il suffit de faire la factorisation que sur les nombres pairs.
Normalement quand on cherche les facteurs premiers, on le fait avec les nombres impairs inférieurs à la racine carrée.
Dans ma formule, on ne divise que les nombres pairs.
J'espère que c'est clair.

Salut

[invite5f4c1fbb]

Bonjour!...

Ou j'ai rêvé (vu l'heure tardive, ça pourrait paraître normal), ou il l'a vraiment écrit!... (Le nombre dont on vérifie la primalité doit être paire??)

Lakar, s'il te plait, j'aimerais un peu de sérieux sur mon fil de discussion, ou tu peux, et ce serait préférable, ouvrir un nouveau fil de discussion à ce sujet. D'avance, merci!

W's

7/7/2010

Bonjour

Formule pour déterminer les facteurs premiers d’un nombre
Editeur MR. LACHKAR M.


Démonstration
Le principe de l’algorithme
Soit à déterminer la racine carrée d’un nombre N entier naturel. Si le nombre possède une racine carrée sans reste, on dira que N est divisible par sa racine carrée, si au contraire il y a un reste, on dira que le nombre N, soit qu’il est composé dont il faut trouver ses facteurs, soit qu’il n’a pas de diviseurs que 1 ou lui-même et dans ce cas, on dira que le nombre est premier.
Etudions le cas ou le nombre possède, après extraction de la racine, un reste.
Soit N = le nombre
x = la racine carré de N
bo = le reste
Donc N= (x*x) + bo
Si nous modifions la racine carrée X dans la même proportion, en diminuant l’un et en augment l’autre à chaque fois d’une unité, le nombre N sera aussi modifié.
Pour garder le même nombre nous devons modifier aussi le reste

N= (x – i )(x + i) + bi

Nous constatons qu’à chaque modification de X , le reste augmentera d’une quantité égale au carrée de i

N = (x – i )(x + i) + bo + i`2


Donc bi = bo + i`2

L’idée de cet algorithme consiste à établir des nouvelles relations avec des nouveaux xi et les nouveaux restes bi obtenus suite à la multiplication des xi entre eux.
Les xi sont obtenus à partir des x ( la racine), en soustrayant à celui de gauche et en augmentant celui de droite une unité à chaque nouvelle multiplication. La somme de chaque opération avec le nouveau reste donnera toujours le nombre N
N = (x*x) + bo (ici x1=x2 =x)
N = (x1 – 1)(x2 + 2) + bo +p1
N = (x1 – 2)(x2 + 2) + bo +p1 + p2
N = (x1 – 3)(x2 + 3) + bo +p1 + p2 + p3
Nous constatons que le reste bi = bo + somme des pi est une progression arithmétique qui varie du carrée selon sa position dans le rang.


Rang progression de bi

0 le reste = bo
1 le reste = bo + b1 + 1`2
2 le reste = bo + b1 + b2 = bo + 2`2
3 le reste = bo + b1 + b2 + b3 = bo + 3`2
4 le reste = bo + b1 + b2 + b3 + b4 = bo + 4`2

Posons
bi = bo + i`2

Pour pouvoir trouver un facteur diviseur de N, il faut faire une comparaison entre les xi et bi et voir la divisibilité de bi par les xi.

Représentons par k le résultat de cette division k= bi/xi

Nous pouvons dire que xi est l’un des facteurs diviseur du nombre N, l’autre diviseur est obtenu en ajoutant k à l’autre xi
K2=k1 + xi

Remarque : Nous constatons qu’il suffit de vérifier la divisibilité par xi que pour les bi pairs

Conclusions
Formules
(x1)i = x – i (x2)i = x + i 2i = (x2)i – (x1)i
(x2)i = x + ¦ x - (x1)i | = 2x - (x1)i = x + ii

Comme bi = bo + i`2
Alors nous dirons que si la condition de la divisibilité de de bi par les xi est réalisée
K = bi/xi = bo + ¦ x - (x1)i ¦`2 / (x1)i
Nous dirons alors que le nombre N est divisible par k (qui peut être l’un des facteurs)
Il suffit de vérifier la divisibilité de bi , par xi

X1 = x – i k1 = bo + i`2 / x – 1

X2 = x + i k2 = bo + i`2 / x + 1


Exemple
Soit N = 38 = 2 x 19 = 6 * 6 + 2

i X1 = x – i X2 = x + i bi = bo + i`2
0 6 6 2 2
1 6-1 = 5 6+1 = 7 2+1`2 3
2 6-2 = 4 6+2 = 8 2+2`2 6
3 6-3 = 3 6+3 = 9 2+3`2 11
4 6-4 = 2 6+4 = 10 2+4`2 18
5 6-5 = 1 6+5 = 11 2+5`2 27
6 6-6 = 0 6+6 = 12 2+6`2 38

A la ligne 4 k = bi/xi 18/2 = 9 donc x2 = 10
Donc le 1er facteur k + x2 = 9 + 10 = 19

avec cette façon de procéder, on peut réduire les calculs. pour factoriser des nombres.
le problème c'est l'extraction de la racine pour des nombres assez grands

salut



salut

[Médiat]

Bonjour lakar,
D'abord je ne peux que vous encouragez à faire des recherches en mathématiques ; mais si vous voulez intéresser des lecteurs il va vous falloir vous plier à quelques exigences :
1) relisez-vous afin déviter des grosses fautes de frappes (N = (x1 – 1)(x2 + 2) + bo +p1 au lieu de N = (x1 – 1)(x2 + 1) + bo +p1 )
2) soyez cohérent dans les notations, parfois x1 et x2 représente des constantes (pour un calcul donné), d'ailleurs égales (puisqu'égales toutes les 2 à x), puis xi représente le i^ième élément du calcul.
3) Essayer d'utiliser , ou a minima les indices comme N = (x₁ – 1)(x₂ + 2) + b_o + p₁
4) Eviter les affirmations non démontrées, quand vous écrivez "Pour pouvoir trouver un facteur diviseur de N, il faut faire une comparaison entre les xi et bi et voir la divisibilité de bi par les xi.", vous n'avez en rien expliqué pourquoi "il faut".
5) donnez un exemple probant ; vous voulez montrer l'efficacité de votre algorithme sur 38 qui nécessite 5 lignes de calculs (on s'arrête quand cela marche) sans compter les divisions que vous devez faire, alors que la technique la plus bête (la division par les nombres premiers plus petit que la racine carrée) nécessite une seule opération.
6) expliquer clairement pourquoi "on peut réduire les calculs", car c'est là le point central.

Enfin une dernière remarque : en aucun cas le calcul de la racine ne pose problème, même pour les nombres extrêmement grands, si c'est votre seul souci, alors considérez que vous n'en avez plus (moi j'en ai d'autres, que vous démontriez que votre méthode est économique en temps par rapport aux techniques connues, par exemple).

Ne désespérez pas, mais je crois qu'il y a encore du travail.

[invite5f4c1fbb]

Bonjour lakar,
D'abord je ne peux que vous encouragez à faire des recherches en mathématiques ; mais si vous voulez intéresser des lecteurs il va vous falloir vous plier à quelques exigences :
1) relisez-vous afin déviter des grosses fautes de frappes (N = (x1 – 1)(x2 + 2) + bo +p1 au lieu de N = (x1 – 1)(x2 + 1) + bo +p1 )
2) soyez cohérent dans les notations, parfois x1 et x2 représente des constantes (pour un calcul donné), d'ailleurs égales (puisqu'égales toutes les 2 à x), puis xi représente le i^ième élément du calcul.
3) Essayer d'utiliser , ou a minima les indices comme N = (x₁ – 1)(x₂ + 2) + b_o + p₁
4) Eviter les affirmations non démontrées, quand vous écrivez "Pour pouvoir trouver un facteur diviseur de N, il faut faire une comparaison entre les xi et bi et voir la divisibilité de bi par les xi.", vous n'avez en rien expliqué pourquoi "il faut".
5) donnez un exemple probant ; vous voulez montrer l'efficacité de votre algorithme sur 38 qui nécessite 5 lignes de calculs (on s'arrête quand cela marche) sans compter les divisions que vous devez faire, alors que la technique la plus bête (la division par les nombres premiers plus petit que la racine carrée) nécessite une seule opération.
6) expliquer clairement pourquoi "on peut réduire les calculs", car c'est là le point central.

Enfin une dernière remarque : en aucun cas le calcul de la racine ne pose problème, même pour les nombres extrêmement grands, si c'est votre seul souci, alors considérez que vous n'en avez plus (moi j'en ai d'autres, que vous démontriez que votre méthode est économique en temps par rapport aux techniques connues, par exemple).

Ne désespérez pas, mais je crois qu'il y a encore du travail.

Bonjour,

Merci pour vos remarques

je dis bien que
N = (x*x) + bo (ici x1=x2=x)
N = (x1 – 1)(x2 + 1) + bo +p1 a
N = (x1 – 2)(x2 + 2) + bo +p1 + p2
N = (x1 – 3)(x2 + 3) + bo +p1 + p2 + p3


un autre exemple

N = 5819 x 9871 = 57439349 = 7578 x 7578 + 13265

i x_i x₂ bo + i² b_i
0 7578 7578 13265+0 13265
1 7577 7579 13265+1 13266
2 7576 7580 13265+4 13269
3 7575 7581 13265+9 13274

12 7565 7590 13265+144 13409
13 7564 7591 13265+169 13434
14 7562 7592 13265+196 13461



42 7536 15029
43 7535 15114
44 7534 15201
45 7533 15290
46 7542 15381

1759 5819 9337 13265+3094081 3107346


A ligne 1759 k = 3107346/5819= 534

Donc X2 = 534 + 9337 = 9871

salut

Le calcul ne se fait que sur les b_i paires

[Médiat]

Si je comprends bien, après plus de 850 divisions (sans compter les autres opérations), vous obtenez deux facteurs, alors que la méthode simpliste donne ce résultat après 8 calculs !

Pour que votre méthode soit intéressante, elle ne doit pas se contenter de donner des résultats, mais les donner plus vite (en moyenne au moins) que les méthodes déjà connues, pour l'instant elle donne des résultat plus mauvais que la méthode de base ...

[invite5f4c1fbb]

Si je comprends bien, après plus de 850 divisions (sans compter les autres opérations), vous obtenez deux facteurs, alors que la méthode simpliste donne ce résultat après 8 calculs !

Pour que votre méthode soit intéressante, elle ne doit pas se contenter de donner des résultats, mais les donner plus vite (en moyenne au moins) que les méthodes déjà connues, pour l'instant elle donne des résultat plus mauvais que la méthode de base ...

Bonjour,

Je vous remercie pour vos commentaires, seulement je vous demande par quelle méthode vous trouverez la réponse en 8 opérations pour ce nombre
N = 5819 x 9871 = 57439349 = 7578 x 7578 + 13265
qui est le résultat de produit de 2 nombres premiers 5819 x 9871

Merci

Salut

[leg]

Bonjour,

Je vous remercie pour vos commentaires, seulement je vous demande par quelle méthode vous trouverez la réponse en 8 opérations pour ce nombre
N = 5819 x 9871 = 57439349 = 7578 x 7578 + 13265
qui est le résultat de produit de 2 nombres premiers 5819 x 9871

Merci

Salut

tu en es sur ??? que c'est le résultat de 2 premiers....

[Médiat]

Bonjour,

Je vous remercie pour vos commentaires, seulement je vous demande par quelle méthode vous trouverez la réponse en 8 opérations pour ce nombre
N = 5819 x 9871 = 57439349 = 7578 x 7578 + 13265
qui est le résultat de produit de 2 nombres premiers 5819 x 9871

57439349 = 23 x 2497363
Et 23 est le 8 ième nombre premier (non pair).

[leg]

tu peux essayer avec ces deux nombres: 840 337831 et 840337801 et contrôler le nombre d'opérations qu'il te faut, pour trouver le premier facteur P par exemple ...et Médiat te diras combien il lui a fallut d'opérations...

[Elie520]

[invite5f4c1fbb]

tu en es sur ??? que c'est le résultat de 2 premiers....

Bonjour,

Merci pour vos remarques,
La formule sert à décomposer un nombre en 2 facteurs.
On peut aussi s'en servir des PGCD et on aura à la première ligne le premier facteur.

1.....7577 ....7579......13265+1=13266

Donc pgcd 7579(11,13,53) et pgcd 13266(2,3,3.11.67)

Donc N est divisible par 11.

Merci

Salut

[invite5f4c1fbb]

tu peux essayer avec ces deux nombres: 840 337831 et 840337801 et contrôler le nombre d'opérations qu'il te faut, pour trouver le premier facteur P par exemple ...et Médiat te diras combien il lui a fallut d'opérations...

bonjour,
pour le nombre
N=840337801 =28988 x 28988 + 33657

X x B0 bi
0 28988 28988 33657 33657
1 28987 28989 33657+1 33658
2 28986 28990 33657+4
3 28985=5.11.17.31 28991 33657+9 33666=2.3.31.181

Donc si on utilise les pgcd on a le premier facteur à la 3ème ligne qui le facteur 31.

salut

[Médiat]

Bonsoir,

Si j'ai bien compris votre méthode consiste à faire des tests de divisibilté pour une variable comprise entre racine entière(N) et 1, même en ne faisant qu'un test sur deux, pour un nombre de l'ordre de 10¹⁰, cela va vous demander 50 000 opérations au maximum, alors que la division par les premiers inférieurs à 100 000 nécessite moins de 10 000 opérations (et c'est la méthode la plus bête, il en existe de beaucoup plus efficaces)

[invitef37fc893]

11 x 927731393966212331924993753945 063876315576745345429191866652 70156878978760240892820463265

[Paraboloide_Hyperbolique]

Merci pour votre intérêt, je vous informe que je peux pas satisfaire votre souhait, c'est pas à cause que ma formule ne peut le faire, mais c'est que je ne suis pas équiper pour les grands nombres.
salut

Bonjour lakar: comme vous travaillez en C++, téléchargez la bibliothèque gratuite "gmp" (en C): https://gmplib.org/

Celle-ci permet de traiter les grand nombres et propose même un algorithme de factorisation en nombres premiers. Vous aurez ainsi une base de comparaison pour vérifier si votre algorithme est au moins aussi rapide que celui-ci proposé par gmp*.

*A noter que l'algorithme de factorisation de gmp n'est probablement pas le plus rapide sur le marché.

[pm42]

Bonjour lakar: comme vous travaillez en C++, téléchargez la bibliothèque gratuite "gmp" (en C): https://gmplib.org/

D'un autre coté, il n'est pas revenu sur le site depuis 2010.

[Paraboloide_Hyperbolique]

Mince, je n'avais pas fait attentions aux dates et simplement suivi le message de pimkiwimki...

[pm42]

Mince, je n'avais pas fait attentions aux dates et simplement suivi le message de pimkiwimki...

Ca arrive à tout le monde