Discussion:
Petit théorème de Fermat
(trop ancien pour répondre)
Julien Arlandis
2017-05-21 19:11:22 UTC
Permalink
Raw Message
En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
m'affichait tous les nombres premiers jusqu'à 340 :

for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);

Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
MAIxxx
2017-05-22 05:27:39 UTC
Permalink
Raw Message
En faisant des tests sur le petit théorème de Fermat j'ai été stupéfait
de constater que le petit bout de code javascript que voici m'affichait
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
Le petit théorème dit que a^p = a + k.p pour p premier mais n'affirme
pas que l'égalité n'a lieu *que* pour p premier, c'est vrai.
Il reste que les nombres composés qui la satisfont pour un a donné sont
*probablement* une infinité. Ça reste à démontrer.
--
Si vous mettez deux Français ensemble, et s'ils sont d'accord sur tout,
c'est qu'un des deux est un étranger.
Ahmed Ouahi, Architect
2017-05-22 07:10:17 UTC
Permalink
Raw Message
Certaines découvertes ayant émergé lors de l'effort considérable tout de
même
D'en prouver le théorème ayant été plus importantes que le théorème lui-même
--
Ahmed Ouahi, Architect
Bonjour!
En faisant des tests sur le petit théorème de Fermat j'ai été stupéfait de
constater que le petit bout de code javascript que voici m'affichait tous
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés apparaissent
en trop, il s'agit des nombres 341, 561 et 645.
Le petit théorème dit que a^p = a + k.p pour p premier mais n'affirme
pas que l'égalité n'a lieu *que* pour p premier, c'est vrai.
Il reste que les nombres composés qui la satisfont pour un a donné sont
*probablement* une infinité. Ça reste à démontrer.
--
Si vous mettez deux Français ensemble, et s'ils sont d'accord sur tout,
c'est qu'un des deux est un étranger.
Samuel DEVULDER
2017-05-22 05:38:59 UTC
Permalink
Raw Message
On Sun, 21 May 17 19:11:22 +0000, Julien Arlandis
Post by Julien Arlandis
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Je ne connais pas bien JS, mais passé une certaine valeur de p le
calcul du modulo devient inexact car il manque des bits dans la
représentation ieee.
Julien Arlandis
2017-05-22 09:12:57 UTC
Permalink
Raw Message
Post by Samuel DEVULDER
On Sun, 21 May 17 19:11:22 +0000, Julien Arlandis
Post by Julien Arlandis
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Je ne connais pas bien JS, mais passé une certaine valeur de p le
calcul du modulo devient inexact car il manque des bits dans la
représentation ieee.
C'est ce qui se passe, autant ça marche bien pour le nombre 2, mais pour
3 ça déraille à partir de 31.
Samuel DEVULDER
2017-05-22 10:17:42 UTC
Permalink
Raw Message
On Mon, 22 May 17 09:12:57 +0000, Julien Arlandis
Post by Julien Arlandis
C'est ce qui se passe, autant ça marche bien pour le nombre 2, mais pour
3 ça déraille à partir de 31.
C'est logique car 2^k est exact pour k signé sur 9 ou 10 bits en ieee
64bits puisque la mantisse est constante à 1.0. En revanche des que
3^k depasse le nombre de bits de la mantisse, il y à arrondi qui
fait perdre tout sens à l'opération modulo qui suit puisque justement
on cherche à récupérer l'info qui vient d'être arrondi. Bref pour
calculer les chiffres de poids fort ieee est bon, mais pour ceux de
poids faibles comme le fait un modulo alors il faut se méfier.
Samuel DEVULDER
2017-05-28 16:58:50 UTC
Permalink
Raw Message
On Mon, 22 May 17 09:12:57 +0000, Julien Arlandis
Post by Julien Arlandis
C'est ce qui se passe, autant ça marche bien pour le nombre 2, mais pour
3 ça déraille à partir de 31.
Ce petit détail est très intéressant. En effet ln2( 3^31) est plus
petit que 53. Ce qui devrait dire qu'un float64 est suffisant pour
représenter tous les bits de ce nombre. Le calcul du modulo 3 devrait
donc être exact. Il y à fort à parier que python fait en interne une
bidouille infâme avec l'expression entrée réduisant la précision
théorique des entiers représentés via des float64. En codant le
calcul avec un langage plus proche de la machine on devrait pouvoir
aller plus loin que 31.
Samuel DEVULDER
2017-05-28 18:16:42 UTC
Permalink
Raw Message
On Sun, 28 May 2017 18:58:50 +0200, Samuel DEVULDER
Post by Samuel DEVULDER
donc être exact. Il y à fort à parier que python fait en interne une
bidouille infâme avec l'expression entrée réduisant la précision
théorique des entiers représentés via des float64. En codant le
calcul avec un langage plus proche de la machine on devrait pouvoir
aller plus loin que 31.
Je viens de tester en LUA ce que donne 3^31%3 et il donne bien 3.
C'est la preuve que python fait un truc crado avec les entiers
représentés par des flottants. En LUA tout est float64 y compris les
entiers ce qui permet à ce langage simple et rikiki (une seule
structure de donnée bien pensée avec laquelle on peut tout faire et
un seul type de nombre) de traiter les entiers exactement jusqu'à
2^54 ce qui n'est que 512 fois plus petit que les int64, mais qui est
suffisamment grand en pratique. En tout cas il ne se met pas à
deconner à partir de 31 pour 3 mais uniquement à partir de 35 ;-)

À+ Sam.
robby
2017-05-29 08:47:35 UTC
Permalink
Raw Message
Je viens de tester en LUA ce que donne 3^31%3 et il donne bien 3. C'est
la preuve que python fait un truc crado avec les entiers représentés par
des flottants.
non, c'est a cause de la façon de faire des modulos, et plus
généralement, des divisions (du moment que c'est fait en float).

dans bien des langages a/b est implémenté par a * 1/b ,
or 1/3 n'est pas représentable exactement en machine.
--
Fabrice
Samuel DEVULDER
2017-05-29 09:05:46 UTC
Permalink
Raw Message
Post by robby
dans bien des langages a/b est implémenté par a * 1/b ,
or 1/3 n'est pas représentable exactement en machine.
C'est dommage car il existe l'opération fmod sur la plupart des fpu
gérant correctement le cas des entiers ieee. En tout cas sous LUA on
obtient bien le modulo de ce que j'ai pu tester (android arm v7).
Julien Arlandis
2017-05-28 21:43:07 UTC
Permalink
Raw Message
Post by Samuel DEVULDER
On Mon, 22 May 17 09:12:57 +0000, Julien Arlandis
Post by Julien Arlandis
C'est ce qui se passe, autant ça marche bien pour le nombre 2, mais
pour
Post by Julien Arlandis
3 ça déraille à partir de 31.
Ce petit détail est très intéressant. En effet ln2( 3^31) est plus
petit que 53. Ce qui devrait dire qu'un float64 est suffisant pour
représenter tous les bits de ce nombre. Le calcul du modulo 3 devrait
donc être exact. Il y à fort à parier que python fait en interne une
bidouille infâme avec l'expression entrée réduisant la précision
théorique des entiers représentés via des float64. En codant le
calcul avec un langage plus proche de la machine on devrait pouvoir
aller plus loin que 31.
Mon test a été fait en javascript et non pas en python...
Samuel DEVULDER
2017-05-29 05:43:36 UTC
Permalink
Raw Message
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.

Mais c'est plus un thème informatique que mathématique en effet.
robby
2017-05-29 08:49:56 UTC
Permalink
Raw Message
Post by Samuel DEVULDER
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.
Mais c'est plus un thème informatique que mathématique en effet.
la question de comment trouver un algorithme qui calcule les modulo
correctement en floats (i.e. exact quand il se trouve que les paramètres
sont entiers) est n'est pas complètement étrangère aux maths, tout de même !
--
Fabrice
MAIxxx
2017-05-30 09:37:49 UTC
Permalink
Raw Message
Post by robby
Post by Samuel DEVULDER
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.
Mais c'est plus un thème informatique que mathématique en effet.
la question de comment trouver un algorithme qui calcule les modulo
correctement en floats (i.e. exact quand il se trouve que les paramètres
sont entiers) est n'est pas complètement étrangère aux maths, tout de même !
Pour le modulo p d'une grande puissance d'un nombre entier a, il me
semble qu'on peut le faire par une suite de divisions entières toutes
bêtes plutôt que "brutalement"
a=a1.p +a'1 a'1 < p
a²= a.a1.p + a'1.a= a2.p + a'2
On ne travaille que sur le reste par p toujours inférieur à p

ex 3^31 ... 3^4 = 81 = 19 + 31*2
3^5 = 26 +31.q5
3^6 = 16 +31.q6 ...
3^7 = 17 + 31.q7
3^12 = 256 + x*31= 8 + 31.q12
3^24 = 64 + y*31 = 2 + 31.q34
3^31 = 3^24.3^7 = (2 + 31.q24)(17+31.q7)= 34 +z.31 = 3 + 31.q31 CQFD

Si p n'est pas trop grand on restera dans le domaine où les "floats"
sont exacts (j'espère). On peut diviser p en puissances de 2 et
travailler sur les carrés successifs)

... 3^31 = 3^24.3^7 = (10+31.q24)(
--
Si vous mettez deux Français ensemble, et s'ils sont d'accord sur tout,
c'est qu'un des deux est un étranger.
Julien Arlandis
2017-05-30 10:05:10 UTC
Permalink
Raw Message
Post by MAIxxx
Post by robby
Post by Samuel DEVULDER
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.
Mais c'est plus un thème informatique que mathématique en effet.
la question de comment trouver un algorithme qui calcule les modulo
correctement en floats (i.e. exact quand il se trouve que les paramètres
sont entiers) est n'est pas complètement étrangère aux maths, tout de même !
Pour le modulo p d'une grande puissance d'un nombre entier a, il me
semble qu'on peut le faire par une suite de divisions entières toutes
bêtes plutôt que "brutalement"
a=a1.p +a'1 a'1 < p
a²= a.a1.p + a'1.a= a2.p + a'2
On ne travaille que sur le reste par p toujours inférieur à p
ex 3^31 ... 3^4 = 81 = 19 + 31*2
3^5 = 26 +31.q5
3^6 = 16 +31.q6 ...
3^7 = 17 + 31.q7
3^12 = 256 + x*31= 8 + 31.q12
3^24 = 64 + y*31 = 2 + 31.q34
3^31 = 3^24.3^7 = (2 + 31.q24)(17+31.q7)= 34 +z.31 = 3 + 31.q31 CQFD
Si p n'est pas trop grand on restera dans le domaine où les "floats"
sont exacts (j'espère). On peut diviser p en puissances de 2 et
travailler sur les carrés successifs)
... 3^31 = 3^24.3^7 = (10+31.q24)(
Le problème c'est que le langage va traiter les opérations de manières
séparées.

x = a^p mod p va devenir
x = mod(exp(a,p),b)
soit
x = exp(a,p)
x = mod(x,b)

Le genre d'optimisations que tu suggères exigerait que le langage traite
les deux opérations de manière globale par une fonction qui effectuerait
le calcul de l'exposant de manière modulaire.
Un truc du genre x = exp_mod(a,p,b) où exp_mod() fait le calcul que tu as
décrit.
Samuel DEVULDER
2017-05-30 11:16:25 UTC
Permalink
Raw Message
On Tue, 30 May 17 10:05:10 +0000, Julien Arlandis
Post by Julien Arlandis
Le genre d'optimisations que tu suggères exigerait que le langage traite
les deux opérations de manière globale par une fonction qui
effectuerait
Post by Julien Arlandis
le calcul de l'exposant de manière modulaire.
Un truc du genre x = exp_mod(a,p,b) où exp_mod() fait le calcul que tu as
décrit.
Si le langage ne le fait pas on peut faire une fonction utilisateur
qui fait ce qu'il faut. C'est un peu le but de l'art de la
programmation que étendre les trucs de base qu'offre un langage par
des méthodes ou fonctions de plus en plus abstraites et proche du
métier de l'utilisateur final.
MAIxxx
2017-05-30 17:43:58 UTC
Permalink
Raw Message
Post by MAIxxx
Post by robby
Post by Samuel DEVULDER
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.
Mais c'est plus un thème informatique que mathématique en effet.
la question de comment trouver un algorithme qui calcule les modulo
correctement en floats (i.e. exact quand il se trouve que les
paramètres sont entiers) est n'est pas complètement étrangère aux
maths, tout de même !
Pour le modulo p d'une grande puissance d'un nombre entier a, il me
semble qu'on peut le faire par une suite de divisions entières toutes
bêtes plutôt que "brutalement"
a=a1.p +a'1 a'1 < p
a²= a.a1.p + a'1.a= a2.p + a'2
On ne travaille que sur le reste par p toujours inférieur à p
ex 3^31 ... 3^4 = 81 = 19 + 31*2
3^5 = 26 +31.q5
3^6 = 16 +31.q6 ...
3^7 = 17 + 31.q7
3^12 = 256 + x*31= 8 + 31.q12
3^24 = 64 + y*31 = 2 + 31.q34
3^31 = 3^24.3^7 = (2 + 31.q24)(17+31.q7)= 34 +z.31 = 3 + 31.q31 CQFD
Si p n'est pas trop grand on restera dans le domaine où les "floats"
sont exacts (j'espère). On peut diviser p en puissances de 2 et
travailler sur les carrés successifs)
... 3^31 = 3^24.3^7 = (10+31.q24)(
Il faut lire 3^31 = (3^24).(3^7) l'éditeur de posts m'a buggé
--
Si vous mettez deux Français ensemble, et s'ils sont d'accord sur tout,
c'est qu'un des deux est un étranger.
azubi
2017-05-29 11:04:40 UTC
Permalink
Raw Message
Post by Samuel DEVULDER
On Sun, 28 May 17 21:43:07 +0000, Julien Arlandis
Post by Julien Arlandis
Mon test a été fait en javascript et non pas en python...
Oups. Mais les conclusions sont les mêmes: js fait perdre de la
précision aux float64 par rapport à ce qu'ils permettent en principe.
Mais c'est plus un thème informatique que mathématique en effet.
Désolé pour mon incompréhension, mais pourquoi vouloir utiliser des
float pour des calculs ne faisant intervenir que des entiers? En python
(j'ai testé avec python 3.5.2 et python 2.7) l'opérateur
d'exponentiation est ** (par exemple 3**4323) et dans ce cas on reste
dans les entiers et donc ensuite le modulo donne la réponse correcte.
Par contre en utilisant la méthode "pow()" alors automatiquement on
passe en floating point. D'après mes connaissances c'est la même chose
en C (bon là il faut un peu bosser pour l'exponentiation en entiers) et
en Java (ou pour le cas de Java utiliser la classe BigNumber). Si vous
devez *absolument* faire des calculs avec des très grands nombres
entiers en Javascript et que la vitesse de calcul devient un problème,
peut-être faut-il se tourner vers un outils annexe comme WebCL ou
Webassembly. Enfin moi ce que j'en dis...
robby
2017-05-29 19:09:18 UTC
Permalink
Raw Message
Si vous devez *absolument* faire des calculs avec des très grands nombres
entiers en Javascript et que la vitesse de calcul devient un problème,
peut-être faut-il se tourner vers un outils annexe comme WebCL ou
Webassembly. Enfin moi ce que j'en dis...
disons qu'en tout cas, on se fait facilement cueillir par un
mod(33,33)=33 inatendu, alors qu'on ne manipulait pas de grands nombres.
C'est dommage car il existe l'opération fmod sur la plupart des fpu
gérant correctement le cas des entiers ieee.
en l'occurence c'est sur GPU en GLSL (pas testé en Cuda), où la place
des transistors est davantage comptée, alors qu'on se sent en
environnement C / IEEE normal.
--
Fabrice
robby
2017-05-23 07:45:52 UTC
Permalink
Raw Message
Post by Samuel DEVULDER
Je ne connais pas bien JS, mais passé une certaine valeur de p le
calcul du modulo devient inexact car il manque des bits dans la
représentation ieee.
oui, et dans tous les langages. (parfois on a meme mod(33,33) = 33 ! )
c'est parceque ça passe par une division, donc precision limitée, alors
qu'une minuscule erreur fait passer du côté 0 ou 1 du fract.

En plus, les compilos souvent implementent les divisions a/b par a *
inverse(b), du coup 1/b peut etre imprécis alors que a/b aurait pu etre
bon.


-> ce genre de calculs doit imperativement etre fait en entiers .

(sauf a la rigueur quand on ne manipule que des puissances de 2, car la
representation IEEE traite exactement certains nombres, et 1/2^p reste
exact en machine ).
--
Fabrice
ast
2017-05-23 08:06:51 UTC
Permalink
Raw Message
Post by robby
Post by Samuel DEVULDER
Je ne connais pas bien JS, mais passé une certaine valeur de p le
calcul du modulo devient inexact car il manque des bits dans la
représentation ieee.
oui, et dans tous les langages. (parfois on a meme mod(33,33) = 33 ! )
c'est parceque ça passe par une division, donc precision limitée, alors qu'une minuscule erreur
fait passer du côté 0 ou 1 du fract.
En plus, les compilos souvent implementent les divisions a/b par a * inverse(b), du coup 1/b peut
etre imprécis alors que a/b aurait pu etre bon.
-> ce genre de calculs doit imperativement etre fait en entiers .
(sauf a la rigueur quand on ne manipule que des puissances de 2, car la representation IEEE traite
exactement certains nombres, et 1/2^p reste exact en machine ).
--
Fabrice
Passez en Python, langage avec lequel il n'y a pas de limite sur la taille
des entiers (à partir de la version 3)
Samuel DEVULDER
2017-05-23 08:22:01 UTC
Permalink
Raw Message
Post by ast
Passez en Python, langage avec lequel il n'y a pas de limite sur la taille
des entiers (à partir de la version 3)
Oh tous les langages ont ce qu'il faut pour traiter les nombres
multi-précision.

La gestion des TAB et SPACE en python pour definir de la sémantique
m'a conduit à plein de bugs vicieux (ce qu'on lit à l'écran n'est pas
ce qui s'execute) et puis la gestion OOP ne m'avait pas semblee
géniale. Non perso si je veux faire dans l'exotique objet avec
entiers de longueur arbitraire je fais du smalltalk! :-P

Sinon tout autre langage avec les bonnes bibliothèques
multi-précision convient.
rosab
2017-05-22 07:21:11 UTC
Permalink
Raw Message
Post by Julien Arlandis
En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
Ce sont les nombres dits "de Poulet" :
https://fr.wikipedia.org/wiki/Nombre_et_supernombre_de_Poulet

--
rosab
Julien Arlandis
2017-05-22 09:11:58 UTC
Permalink
Raw Message
Post by rosab
Post by Julien Arlandis
En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
https://fr.wikipedia.org/wiki/Nombre_et_supernombre_de_Poulet
Merci pour cette référence.
ast
2017-05-23 08:04:27 UTC
Permalink
Raw Message
Post by rosab
Post by Julien Arlandis
En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
https://fr.wikipedia.org/wiki/Nombre_et_supernombre_de_Poulet
--
rosab
Il y a aussi les nombres de Carmichel qui sont composés et qui passent
le test de Fermat en toute base (le "a" dans a^(p-1)-1)

https://fr.wikipedia.org/wiki/Nombre_de_Carmichael

561, 1105, 1529 ...
Ahmed Ouahi, Architect
2017-05-23 08:16:52 UTC
Permalink
Raw Message
Reste à savoir que si deux exp. n moins un est nombre premier
Deux exp. n moins un (deux exp. n moins un) est nombre parfait
--
Ahmed Ouahi, Architect
Bonjour!
Post by rosab
Post by Julien Arlandis
En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);
Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
https://fr.wikipedia.org/wiki/Nombre_et_supernombre_de_Poulet
--
rosab
Il y a aussi les nombres de Carmichel qui sont composés et qui passent
le test de Fermat en toute base (le "a" dans a^(p-1)-1)

https://fr.wikipedia.org/wiki/Nombre_de_Carmichael

561, 1105, 1529 ...
Ahmed Ouahi, Architect
2017-05-22 08:41:16 UTC
Permalink
Raw Message
N'empêche ce qui en reste-t-il strictement insolvable quant aux nombres
En mathématique est que chaque autre nombre plus grand que le nombre
Essentiellement deux est sûrement la somme de deux premiers nombres
--
Ahmed Ouahi, Architect
Bonjour!


"Julien Arlandis" kirjoitti viestissä:***@jntp...

En faisant des tests sur le petit théorème de Fermat j'ai été
stupéfait de constater que le petit bout de code javascript que voici
m'affichait tous les nombres premiers jusqu'à 340 :

for (p=3; p<340; p++) if( Math.pow(2, p) % p == 2) console.log(p);

Si on pousse la boucle jusqu'à 1000, seuls 3 nombres composés
apparaissent en trop, il s'agit des nombres 341, 561 et 645.
Loading...