Forum de mathématiques - Bibm@th.net

Bonjour,

Allez hop, code amélioré et finalisé en ligne, même URL.

Pour le test de Miller-Rabin, 64 bases sont utilisées, 32 bases fixes (les 32 premiers nombres premiers, de 2 à 131) et 32 bases aléatoires (intervalle 2, n−2). Chaque base de test réduit par au moins 75% la probabilité de faux positifs (c’est la propriété de Miller-Rabin). Ainsi, la probabilité de déclarer "premier" un nombre qui est en réalité composé est maintenant d'environ 5.4 × 10⁻³⁹. Autrement dit, le test satisfait largement les exigences des usages généraux de la cryptographie courante (RSA, Diffie-Hellman, etc.) et même des outils comme OpenSSL, GnuPG ou GMP (qui utilisent en général 25 à 64 tests).

Pollard Rho est également amélioré par la version Brent qui s’y prend autrement et mieux, ce qui en moyenne gagne ici un facteur deux.

Et enfin le calcul parallèle. Javascript permet d’implémenter des Web Workers capables de travailler indépendamment, ce qui tombe bien puisque chaque base fait une recherche autonome. On va donc lire le nombre de threads disponibles, on implémente autant de blocs qui calculeront en parallèle, et en gros pour des factorisations compliquées, sur mon PC je passe d’une quarantaine de secondes avec thread unique et Pollard simple à six secondes avec Pollard Rho Brent amélioré et web workers.

En dehors de la cryptographie qui cherche des décompositions compliquées, la plupart des nombres se décomposent maintenant super vite et super bien, et cela a été un vrai plaisir de bricoler ce genre de truc sans avoir à mettre trop les mains dans le cambouis.

Bonjour,

Pourquoi une calculatrice ? Cela s'appelle le crible d'Érastothène, suffit de faire un tableau de 40 lignes de 50 cases (pratique, j'ai un bloc Rhodia à petits carreau, ça tient sur une feuille), puis de marquer 2 dans la première case, et partant de là de cocher une case sur 2. On met ensuite le nombre correspondant à la case libre suivante, ici 3, et on coche toutes les trois cases. Même pas besoin d'écrire, on se déplace de trois cases, on coche, on se déplace de trois cases, on coche, etc. La case libre suivante est maintenant à deux cases de ce 3, on y met 5, et on coche toutes les cinq cases. Puis 7, puis 11, etc. Un gamin sait faire ça, pas besoin d'attendre d'être au lycée. Les Grecs déjà, m'a-t-on dit...

Bonsoir,

Perso je me suis imaginé sur un anneau avec un réservoir permettant d’en faire le tour complet. Ok. Que se passe-t-il si je répartis le contenu en deux moitiés et que je place le second réservoir pile poil au milieu opposé. Je le rejoins, que ce soit dans un sens ou dans l’autre, en vidant le premier. Bon, comme un anneau c’est symétrique, je ne garde qu’un seul sens, ça marche aussi.

Et maintenant, piège : je déplace le second réservoir pour l’éloigner du premier quand on respecte ce sens de rotation. Panne sèche, forcément. Sauf que. On peut partir de là où on veut, et si je pars de ce second réservoir déplacé vers la fin, quand je vais arriver à cette fin, j’aurais dans le réservoir le carburant qui me manquait pour le rejoindre à partir du premier. Et donc en ajoutant le premier, je rejoins bel et bien le second mon nouveau point de départ.

De là, même chose avec trois, quatre ou n’importe quelle répartition : choisir le point de départ permet de ‘récupérer’ l’excédent qui manquait pour l’atteindre à partir du précédent. En gros, plus on augmente les écarts, plus on concentre le carburant, et donc plus ça revient au même. :-)

Et bien sûr, une fois que j’ai compris ça, je savais que ça marchait de la même façon dans l’autre sens, forcément.

(pas très mathématique ma formulation, désolé)

Bonsoir,

En fait c'est facile à comprendre, le programme teste toutes les divisions par 2, puis 3, puis par les multiples de 6±1. Or parmi ceux-ci, environ la moitié ne sont pas des nombres premiers. Donc effectivement, le nombre de divisions ici n'est pas un minimum théorique.

Si on ne veut tester que les divisions par des nombres premiers, il faut une liste de ceux-ci jusqu'à la racine carrée du nombre dont on cherche les facteurs. Soit on charge cette liste, soit on la constitue par une méthode rapide similaire à celle utilisée dans le programme (il faut par exemple 16 664 nombres premiers pour pouvoir factoriser ton nombre 33762007291).

Allez hop, programme en Python qui constitue d'abord cette liste puis qui ne compte que les divisions par des nombres premiers :

Entrez un nombre à factoriser : 33762007291

► Résultat :
33762007291 = 182981 × 184511

► Performance :
- Nombres premiers générés : 16644
- Divisions effectuées : 16583
- Temps génération : 0.005938s
- Temps factorisation : 0.002296s
- TOTAL : 0.020397s

Bonjour,

On peut toujours écrire un programme Python qui fait le job, en utilisant une recherche un poil plus rapide que tester tous les nombres possibles :
- on teste 2 et 3
- puis tous les multiples de 6 plus ou moin 1 (donc 5, 7, 11, 13, 17, 19, etc.)
- et s'arrêter à la racine carrée

La réponse est pratiquement instantanée.

Facteurs de 74747503 : [8447, 8849]
Nombre de tentatives de division : 2818

Oui, cela devient tellement touffu avec de grands $n$ que j’ai préféré estimer à partir de tirages aléatoires - une forme de sélection darwinienne si on veut - plutôt que me lancer dans le calcul.

Le problème, c’est que chaque branche de l’arborescence a des espérances de gain différentes au fil des cases découvertes. Perso j’établis des seuils pour chaque étape, à telle valeur je continue et à telle autre je conserve, mais c’est assez bourrin vu que ces seuils sont préfixés et ne tiennent pas compte de l’obtention des cases précédentes. Logique de penser qu’un 7, 3 et 2 déjà découverts laissent bien plus de valeurs hautes à la quatrième étape qu’un 13, 15 et 12 par exemple. Faudrait donc le faire en temps réel à la volée.

En fait à force d’y penser, je me rends compte que c’est un peu comme le black jack au casino, la banque applique un algorithme public qui garde un avantage sur n’importe quelle méthode pré-calculée, mais reste inférieur à des mises tenant compte des cartes restant dans le talon. Ici même chose, ma stratégie au doigt mouillé est sans doute satisfaisante comme base, mais peut très certainement être améliorée de façon dynamique.

Hello,

Oui, chaque fois qu’il dévoile une case il sait la valeur de celle-ci. Il peut décider de s’arrêter là et d’empocher, ou au contraire de continuer, sachant qu’à la $n$-ième il n’aura plus le choix et devra se contenter de la valeur de cette dernière.

Pour $n=2$ ce n’est pas très difficile. Au moment où il dévoile la première case, il sait. Si part exemple il tombe sur un $4$, c’est la plus grande valeur du panel (puisqu’il sait que ce sont les valeurs de $1$ à $n^{2}$ qui sont cachées) et donc il s’arrête. S’il tombe sur un $1$ il continue bien sûr, il sait qu’il fera toujours mieux. La stratégie qu’il adopte fait qu’avec un $2$ il continue puisqu’il reste $1$, $3$ et $4$ et donc qu’il a deux chances sur trois de faire mieux (espérance $\dfrac{\left( 1+3+4\right) }{3}=\dfrac{8}{3}>2$), alors qu’avec un $3$ il reste puisque cette fois son espérance est inférieure, à savoir $\dfrac{\left( 1+2+4\right) }{3}=\dfrac{7}{3}<3$.

Avec cette stratégie, l’espérance de gain du jeu $n=2$ est égale à $\dfrac{\left( \dfrac{\left( 2+3+4\right) }{3}+\dfrac{\left( 1+3+4\right) }{3}+3+4\right)}{4}=\dfrac{19}{6}$.

Amis des casse-têtes, bonsoir.

Au départ c’était une curiosité à titre personnel, mais j’ai mis en ligne en me disant que cela pouvait en intéresser d’autres.

C'est vrai. Comme je me suis aussi amusé à faire un programme de > décomposition < pour n’importe quel entier positif (pour les négatifs suffit de changer les signes) on peut s'en servir pour explorer le zéro.

Bref, ton casse-tête hors de ma portée sur le plan théorique m’a quand même bien cassé la tête sur le plan pratique, c'est cool.

Surprenant !

Ce qu’il y a de bien quand on me demande de démontrer, c’est que cela me dit que c’est possible, par conséquent je le tiens pour acquis. Donc là, c’est une propriété tout à fait étonnante, je garde. :-)

Ceci dit, comment a-t-on pu déterminer qu’une sommation des premiers carrés pouvait donner n’importe quel entier, mystère…

Un mot sur l’assistance numérique.

Pour ceux qui ont vu se développer les tableurs et les langages de programmation après leurs études (il en reste encore m’a-t-on dit) l’avenir est au passé. Ils regrettent massivement le bon vieux temps, celui des classes prépa où on apprenait les maths comme on apprenait les lettres classiques (langues mortes faut-il le rappeler) et où l’essentiel de l’effort était finalement de démontrer encore et encore des choses parfaitement connues, la belle affaire...

Aujourd’hui c’est comme si nous avions à notre service des assistants inépuisables, ni plus ni moins. Par exemple pour Lagrange, que je n’ai pas eu l’honneur de connaître, cela a été très simple. Je lui ai demandé une formule qui, quand on fournit $a$ donne $b$, quand on fournit $c$ donne $d$ et quand on fournit $e$ donne $f$. Il me l’a donné, extrait :

Suffit alors de remplacer $f$ par n’importe quelle valeur parmi les cinq proposées pour que le résultat soit parfait.

Soit dit en passant, ce genre d’assistance va à l’encontre de tous les principes qui régissent ce forum, à savoir que c’est au demandeur de faire un effort, qu’on lui donne uniquement des pistes, et que c’est à lui de se débrouiller en montrant de la bonne volonté. C’est très appréciable certes, et je ne remets pas cette approche en cause, je dis juste qu’aujourd’hui on dispose d’outils qui permettent d’aller bien plus vite et bien plus loin, et qu’apprendre les identités remarquables me paraît maintenant aussi utile que d’apprendre les chefs-lieux et les sous-préfectures.

Bonjour,

S’il y a une aptitude qui me semble fondamentale, c’est bien la recherche d’une structure, tout le temps, avec tout. Chercher à comprendre comment ça marche, c’est in fine toujours chercher une logique, que ce soit avec le langage, la médecine, la physique, l’agriculture ou ce que l’on voudra d’autre.

Ici même chose. On voit bien que les valeurs ne suivent pas une progression évidente, qu’il n’y a pas une question de primalité, de parité, d’alternance, les premières structures habituelles que l’on recherche dans ces cas-là. Il est facile d’inventer une structure fonctionnelle grâce aux polynômes de Lagrange mais ce n’est pas ce qu’on nous demande.

J’ai donc essayé un peu tout et n’importe quoi. Par exemple ordonner les nombres en suivant une étoile dans le pentagone (1,3,5,2,4), par exemple changer de base pour trouver une évidence masquée, par exemple décomposer en facteurs premiers pour faire émerger une similitude, etc. Et bien sûr je n’ai rien trouvé.

Je me suis dit qu’il existait peut-être une sommation avec un facteur pour chaque nombre qui donnerait le centre. En gros il s’agit d’essayer dans une plage donnée tous les facteurs possibles à appliquer indépendamment aux sommets a, b, c, d et e pour obtenir la valeur du centre. Alors hop, un petit programme et bingo, 2, -2, 2, 2 et -2 donnait la valeur centrale dans les deux premiers. Si, avec le troisième, j’obtenais une valeur parmi celles proposées, j’étais bon, sinon fallait encore chercher.

J’étais bon.

Bonjour,

J'ai demandé à Perplexity, voici sa réponse.

Je crois que même pour un autodidacte, passer par un site particulier n'a aujourd'hui plus aucun sens tant les ressources de qualité sont disponibles et faciles à trouver.

(eh oui, les temps ont bien changé, mais au moins pour cela ce n'était pas mieux avant ;-)