Forum de mathématiques - Bibm@th.net

lakar

Invité

Re : Nombres premiers

Salut,

Une limite en programmation, oui : la RAM de la machine et le temps qu'on est disposé à attendre. Sinon, mathématiquement, non !
Il y a 20 ans, j'ai écrit un programme de calcul de la racine carrée de 5 avec 120 chiffres après la virgule : il fallait deux heures avec une machine cadencée à 4,7 Hz et dont je ne savais exploiter que 64 Ko de RAM (sur 128 ko) : ma machine actuelle est plusieurs millions de fois plus rapide et plus de 200 millions de fois plus de RAM.
Quelle racine carrée veux-tu calculer et avec combien de chiffres après la virgule ?

@+

Bonjour

Pourquoi, j'ai posé cette question.

Je suis arrivé à une formule pour factoriser un nombre en facteurs premiers.
avec ma formule ,j'exploite le reste cad les chiffres après la virgule et la racine carré du nombre.

réduction dans les calculs et vérification de la division seulent les nombres pairs
Salut

shearer

Invité

Re : Nombres premiers

C’est encore moi et ma méthode. Je crois qu’il est inutile de décortiquer ce qu’il y a à l’intersection de mes 2 règles ainsi, je me perds. Cela parait politiquement incorrect de voir autant de transparence. Il faut que je retourne dans l’autre sens. Je ne garde plus que les règles et je glisse la série complète des chiffres de la formule y = x!/x2. Je ne sais pas si ce que je fais est juste, je m’aventure par-là car c’est ça qu’on cherche. L’addition de log & ln me fait bien penser qu’il existe une autre formule.

Lakar

Invité

Re : Nombres premiers

Salut,

Une limite en programmation, oui : la RAM de la machine et le temps qu'on est disposé à attendre. Sinon, mathématiquement, non !
Il y a 20 ans, j'ai écrit un programme de calcul de la racine carrée de 5 avec 120 chiffres après la virgule : il fallait deux heures avec une machine cadencée à 4,7 Hz et dont je ne savais exploiter que 64 Ko de RAM (sur 128 ko) : ma machine actuelle est plusieurs millions de fois plus rapide et plus de 200 millions de fois plus de RAM.
Quelle racine carrée veux-tu calculer et avec combien de chiffres après la virgule ?

@+

17/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

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Bonjour,

Effectivement, pour autant que je puisse en juger (j'ai fait des essais), ton algorithme semble fonctionner...

1. Si je reprends ta liste de bi pour l'exemple N =38 :
    2, 3, 6, 11, 18 27, 38
    Tu peux constater que ce n'est pas une suite (ou progression) arithmétique.
    Une suite arithmétique [tex]U_n, n \in\;\mathbb{N}[/tex] est définie ainsi [tex]U_n=U_{n-1}+r,\;r \in\;\mathbb{N}[/tex], r est la raison de cette suite.
   Et tu peux constater que b2 - b1 = 3-2 =1 mais que b4-b3 = 6 - 3 = 3
   Ce n'est pas non plus une suite (ou progression) géométrique qui se définit avec une multiplication (et non plus une somme) par la raison.
2. Si par ' tu entends puissance, alors il faut utiliser ^ ce sera plus clair
3. N = 23548758125933 = 4852706*4852706 + 2603497 (23548758125933 = 69847 * 337147739 tous deux premiers)...
   Plus de 1.000.000 de tests à faire avant de trouver 69487...
   Le problème n'est pas tant les racines carrées (quasi instantané) que les 2.000.000 d'additions/soustractions et les 2.000.000 de tests de divisibilité : là ça devient vite rédhibitoire...
4. Ta méthode n'est pas trop éloignée de la méthode dite du "crible quadratique".
    Va voir http://www.bibmath.net/dico/index.php3? … tique.html

@+

PS
Je t'avais dit que les racines carrées des grands nombres (entiers) ne me poseraient pas de problème en langage Python:
[tex]\sqrt{33714773921547893214516124578032501254687802100012401}\approx 183615832437042022126693289[/tex]
Résultat obtenu en moins d' 1 s.

Dernière modification par yoshi (18-07-2010 17:20:18)

lakar

Invité

Re : Nombres premiers

Bonsoir,

Merci pour vos remarques,
Il faut noter une erreur de frappe

au lieu de  N  = (x1 – 1)(x2 + 2) + bo +p1   il faut lire   N  = (x1 – 1)(x2 + 1) + bo +p1   

Une autre remarque, il faut prendre pour les calculs que les bi paires   bi = bo + i^2   

donc on peut faire le calcul directement 

Il suffit de vérifier la divisibilité de  bi  pairs,    par xi   

X1 = x – i       k1 = bo + i^2  / x – i

X2 = x + i       k2 = bo + i^2  / x + i

salue

lakar

Invité

Re : Nombres premiers

Bonsoir

j'ajoute un autre exemple

un autre exemple

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

i  …. ...xi ….. ....x2 ……...bo + i2 ……….....bi
0 …   7578 ……7578 …….13265+0……. ..13265
1…… 7577…… 7579 ……13265+1 …………13266
2…… 7576…… 7580 ……13265+4 …………13269
3 ……7575 ……7581… …13265+9 …………13274

1759… 5819 …..9337… 13265+3094081 ….3107346

A ligne 1759   ……. k = 3107346/5819= 534

Donc X2 = 534 + 9337 = 9871

Le calcul ne se fait que sur les bi paires

Salut

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Re,

Oui, les bi pairs...
J'en ai tenu compte dans les calculs de mon exemple.
Entre le 1er bi et le 1er xi, il y a un écart d'environ 2500000, j'ai arrondi à 2 000 000
Il faut que je teste d'abord
- 2000000 fois bi pour savoir s'il est pair ou impair,
- s'il est pair je dois tester 1000000 fois la divisibilité de bi par x1 et 100000 fois la divisibilité de bi par x2.

Informatiquement, ma machine mettra certainement plus de 15 min (j'ai stoppé après 1.000.000 lignes et 12 min) pour trouver 69847 (et 337147739) avec ta méthode.
Je vais voir si je peux améliorer la vitesse de mon programme, mais j'aurai beaucoup de mal à améliorer le temps d'un programme que j'ai écrit il y a quelques temps déjà et mettant en œuvre l'algorithme de Rho-Pollard :
2/100e de s !!!

@+

PS
Pourquoi un 2e exemple, celui que je t'ai proposé ne te convient pas ?
En ce qui concerne mon exemple, je viens de voir que si le reste après calcul de la racine est impair le suivant sera pair, donc je teste les lignes 1,3,5,7....
Si ce même reste est pair, je testerai les lignes 2,4,6,8...
Je teste donc la parité de bi une seule fois au début du programme.
Ensuite j'ai donc :
1.000.000 d'addition x2+2,
1.000.000 de soustraction x1-2,
1.000.000 de calculs de puissances i^2,
1.000.000 d'addition de bi et de i^2
1.000.000 de test de divisibilité de bi par les x1 et x2...

Ça fait beaucoup quand même, n'est-ce pas ?

PS2
Je viens de découvrir une erreur de programmation. Je vais corriger et retester.

Dernière modification par yoshi (19-07-2010 07:03:24)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Re,

Programme corrigé...
Pour 38, il trouve bien 19 en  4/100e s
Pour 57439349, il trouve bien 9871 en 2s 2/100e
Pour 23548758125933, après 20 min et ligne autour de 3.800.000, j'ai fait une fausse manœuvre et mon programme s'est arrêté : il n'y avait toujours pas de résultat...

Nouveaux essais avec

958143517  = 91873 * 10429 = 30953^2+55308
Ligne 20254 --> 10429     51477   421289884
421289884/10429 = 40396 ; 51477+40396 = 91873 en 23,4 s

95821095701 = 918733 * 104297 = 309549^2+512300
Ligne 918733 --> 104297     514801     42128895804
42128895804/104927 = 401506 ; 514801+401506 = 916307  en 233,6 s soit 5 min 33 s

Conclusion : ta méthode est séduisante, originale mais hélas bien trop lente...
Cela dit, tu pourrais essayer de trouver, un chercheur en mathématiques pour la lui soumettre : qui sait ? il en tirerait peut-être quelque chose...
Je me demande d'ailleurs si au lieu de commencer à la ligne 1 (ou 2), on ne pourrait pas commencer plus haut.
En effet, je remarque que :
38      :  racine   6    reste      2        ligne 4             |2 - 6 |   =   4
589    :  racine  24   reste     13        ligne 5           |13 - 24|  =  11 
5899  :  racine  76   reste    123       ligne 59         |123 - 76| =  47

57439349    :  racine  7578   reste  13265   ligne 9871       |13265 - 7578| = 5687

@+

lakar

Invité

Re : Nombres premiers

Bonsoir Yoshi,

Merci pour vos remarques et pour vos suggestions, je vais réfléchir à toutes vos remarques.

Pour compléments d'information le but de cette  formule c'est pour décomposer un nombre en 2 facteurs.
Mais on peut aussi s'en servir des PGCD.

par exemple pour le nombre

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

i...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 est le facteur 31.

salut

shearer

Invité

Re : Nombres premiers

Même si je ne fais pas mes 37 ans, je viens de louper la médaille Field.
Il faudrait aussi que ces imbéciles de psy me lachent un peu, ils veulent le prix Nobel de médecine.
(les tyrans sur le bûcher).

Donc si j'intègre y=x!/x2 de 37 à 98 et que aàékla àéslhàl  esruo jphsrthhhhhhhaaaaaaaaaaaaa

Lol

Invité

Re : Nombres premiers

Je voudrais savoir s'il existe une formule capable de calculer les nombres premiers?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Salut marrant,

Non, il n'existe pas de formule universelle permettant de calculer à coup sûr les nombres premiers.
Il existe des formules avec chacune des limitations...

@+

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Nombres premiers

Salut à tous,

Ici l' idiot du village.

Je n'ai pas été attiré par cette discussion parce qu'elle était à ma portée : j'ai suffisamment conscience de mes limites pour voir tout de suite qu'elle ne l'est pas.

Ce qui m'a attiré, c'est :

a) la taille de la discussion : sept pages, ça doit être un record,
b) près de 60.000 visites, ça doit être un autre record,
c) j'ai toujours été attiré et agacé par les nombres premiers,
d) j'ai toujours éprouvé le désir de voir quelqu'un obliger cette bande d'énergumènes de nombres premiers à rentrer dans le cadre de ce qui caractérise les mathématiques : la soumission à des règles précises,
e) l'espoir que, dans ces sept pages auxquelles je ne comprenais à peu près rien, il y avait peut-être quelque chose, un progrès dans la maîtrise des nombres premiers.

Pour le savoir, je voudrais seulement demander si quelqu'un peut-répondre, dans un délai raisonnable (cinq à dix minutes) à la question suivante :

le nombre suivant :  21.002.752.143.226.656.522.199.369.247 est-il premier, et, s'il ne l'est pas, quels sont les facteurs premiers dont il est le produit ?

Si je n'ai pas de réponse satisfaisante, je ne vous cache pas que je serai amené à me demander si cette longue, longue, longue discussion a beaucoup fait avancer le schmilblick.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Re,

Pas de bol, tu as fourni un multiple de 3 (Somme des "chiffres" = 114)...
121002752143226656522199369247 = 3 * 43783 * 58049 * 240139 * 66086239065673

@+

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Nombres premiers

Salut, Yoshi,

je te suggère de relire le nombre que tu as donné et de mieux le comparer avec le mien !!!

Manque d'attention ! Je peux t'affirmer que mon nombre n'est pas multiple de trois.

"Sur le métier remettez votre ouvrage" disait, je crois, Boileau.

J'ai vérifié trois fois ce nombre. Un exemple à suivre !

Mon nombre comporte vingt neuf chiffres, le tien trente.

Dernière modification par nerosson (24-01-2011 17:54:17)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Re,

Bin, monbonmonsieurlexempleasuivre, pas de faute d'inattention, ce sont tes foutus points de séparation qui ont mis le bazar.
Toi, tu ne fais jamais d'erreur, par contre :

Nerosson il y a une petite erreur dans un des 2 messages (lettre fausse tout près du début).

-----------------------------------------------------------------------------------------
Je ne sais pas ce qui s'est passé : j'ai fait un copier/coller dans un programme que j'ai déjà et je lui ai demandé d'enlever les points.
Bon cela dit, j'ai repris le nombre modifié.
Verdict du programme :

Le nombre 21002752143226656522199369247 se factorise ainsi :
5000201 * 6000191 * 7000429 * 99999773

Ça te va quand même ?

Citation exacte :
<< Vingt fois sur le métier remettez votre ouvrage. >>
Boileau, oui...

@+

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Nombres premiers

Salut, Yoshi,

J'ai eu droit à la réponse du berger à la bergère. Voici maintenant la réponse de la bergère au berger :

a) une lettre fausse dans deux cryptos qui en totalisent 150.... Que celui qui n'a jamais péché me jette la première pierre,

b) mes "foutus points" sont conformes à l'usage courant. Je dirais même qu'ils sont bien commodes pour éviter les erreurs....

c) la décomposition d'un nombre de 29 chiffres en facteurs premiers ne m'a pas surpris. Je n'ignore pas qu'il existe des procédures qui le permettent, mais elles dépassent mon modeste savoir. Je pense donc que ta compétence à ce sujet est antérieure à la présente discussion. Mon intention, qui semble avoir suscité chez toi, disons : une certaine émotion, avait seulement pour  objet de savoir s'il en était sorti des éléments nouveaux touchant cet irritant problème des nombres premiers.

d) si je t'avais fourni un nombre qui soit le produit de deux facteurs premiers ayant chacun une centaine de chiffres, il en aurait sans doute été tout autrement, puisque le système RSA, qui fait, A JUSTE TITRE, l'admiration des foules, est précisément basé sur la quasi-impossibilité de factoriser les très grands nombres.

e) c'est justement parce que je ne me rappelais plus COMBIEN DE FOIS il fallait remettre son ouvrage sur le métier que j'ai si malencontreusement tronqué la citation de Boileau. Mea culpa ! Ca confirme qu'il faut toujours vérifier !

Avec mon inaltérable amitié.

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Nombres premiers

Bonjour

Oui tout l'encre versé pour cette conversation n'est vraiment pas justifié! De même que "l'idée" originale de la discussion (formule des nb 1er) était absurde et moi ignorant. Heureusement, on change en 934 jours!

Allez fermons cette discussion!

++

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombres premiers

Re,

Discussion fermée à la demande de son initiateur...

@+