Bon, c'est un point que je crois avoir compris, mais j'aimerais juste
une confirmation (ou infirmation... et/ou précision) de votre part.
Considérons le programme suivant. Ai-je raison de croire que les
trois premiers paragraphes (jusqu'au commentaire « maintenant on dépend
du boutisme ») donnent un résultat indépendant du boutisme de la
plateforme ? Entre le deuxième et le troisième paragraphe, l'un vous
paraît-il plus lisible que l'autre ?
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que "all" ne signifie plus "tout" en anglais. Le transtypage automatique dangereux est signalé par l'option -Wconversion.
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
Apres, on ne veut pas "vraiment tout", vu que gcc est capable de se gauffrer et sortir des warnings sans raison, et qu'en meme temps, il y a pas mal de choses qu'il ne verra pas cote portabilite...
In article <alpine.LNX.2.00.1212041115390.3020@coulomb.univ-paris12.fr>,
Lucas Levrel <lucas.levrel@u-pec.fr> wrote:
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à
redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner
un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que
"all" ne signifie plus "tout" en anglais. Le transtypage automatique
dangereux est signalé par l'option -Wconversion.
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un
sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas
d'option pour dire « vraiment tout ».
Apres, on ne veut pas "vraiment tout", vu que gcc est capable de se
gauffrer et sortir des warnings sans raison, et qu'en meme temps, il y a
pas mal de choses qu'il ne verra pas cote portabilite...
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que "all" ne signifie plus "tout" en anglais. Le transtypage automatique dangereux est signalé par l'option -Wconversion.
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
Apres, on ne veut pas "vraiment tout", vu que gcc est capable de se gauffrer et sortir des warnings sans raison, et qu'en meme temps, il y a pas mal de choses qu'il ne verra pas cote portabilite...
Manuel Pégourié-Gonnard
Dominique MICOLLET scripsit :
Manuel Pégourié-Gonnard a écrit :
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que "all" ne signifie plus "tout" en anglais. Le transtypage automatique dangereux est signalé par l'option -Wconversion.
Pour compléter les autres remarques qui ont été faites, dans ma version, -Wconversion n'est pas inclus dans -Wextra non plus.
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32 bits dans le but de réduire rapidement modulo un pseudo-Mersenne. Mais je ne cherche pas particulièrement à utiliser memcpy(), là c'était plutôt pour contraster avec les paragraphes précédents.
Là, dès qu'on cause mathématiques, je suis un peu perdu :-) (et j'ai honte). Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage ne devrait-elle pas être l'octet ? Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à l'architecture du processeur : mais il va y avoir des soucis avec les processeurs 64 bits, sauf si la bibliothèque multiprécision a prévu cette situation.
Là, les 32 bits sont imposés par la structure du nombre quasi-de Mersenne. Imaginons par exemple que je veuille réduire un nombre rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapide passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait de le voir comme une suite de blocs de 32 bits. Et effectivement, c'est moins sympathique sur les archis 64 bits, mais il faut faire avec.
-- Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Dominique MICOLLET scripsit :
Manuel Pégourié-Gonnard a écrit :
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à
redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner
un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que
"all" ne signifie plus "tout" en anglais. Le transtypage automatique
dangereux est signalé par l'option -Wconversion.
Pour compléter les autres remarques qui ont été faites, dans ma version,
-Wconversion n'est pas inclus dans -Wextra non plus.
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32
bits dans le but de réduire rapidement modulo un pseudo-Mersenne. Mais
je ne cherche pas particulièrement à utiliser memcpy(), là c'était
plutôt pour contraster avec les paragraphes précédents.
Là, dès qu'on cause mathématiques, je suis un peu perdu :-) (et j'ai honte).
Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage
ne devrait-elle pas être l'octet ?
Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à
l'architecture du processeur : mais il va y avoir des soucis avec les
processeurs 64 bits, sauf si la bibliothèque multiprécision a prévu cette
situation.
Là, les 32 bits sont imposés par la structure du nombre quasi-de
Mersenne. Imaginons par exemple que je veuille réduire un nombre
rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapide
passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait
de le voir comme une suite de blocs de 32 bits. Et effectivement, c'est
moins sympathique sur les archis 64 bits, mais il faut faire avec.
--
Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Hum, j'ai utilisé gcc -stdÉ9 -Wall -pedantic et il n'a rien trouvé à redire. (J'utilise systématiquement -Wall et je ne laisse jamais traîner un avertissement.)
Votre remarque m'a fait peur. J'ai fait quelques essais, et il semble que "all" ne signifie plus "tout" en anglais. Le transtypage automatique dangereux est signalé par l'option -Wconversion.
Pour compléter les autres remarques qui ont été faites, dans ma version, -Wconversion n'est pas inclus dans -Wextra non plus.
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32 bits dans le but de réduire rapidement modulo un pseudo-Mersenne. Mais je ne cherche pas particulièrement à utiliser memcpy(), là c'était plutôt pour contraster avec les paragraphes précédents.
Là, dès qu'on cause mathématiques, je suis un peu perdu :-) (et j'ai honte). Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage ne devrait-elle pas être l'octet ? Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à l'architecture du processeur : mais il va y avoir des soucis avec les processeurs 64 bits, sauf si la bibliothèque multiprécision a prévu cette situation.
Là, les 32 bits sont imposés par la structure du nombre quasi-de Mersenne. Imaginons par exemple que je veuille réduire un nombre rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapide passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait de le voir comme une suite de blocs de 32 bits. Et effectivement, c'est moins sympathique sur les archis 64 bits, mais il faut faire avec.
-- Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Marc
Lucas Levrel wrote:
Le 4 décembre 2012, Jean-Marc Bourguet a écrit :
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que les utilisateurs risqueraient de mal l'utiliser et de faire perdre des heures à tout le monde avec leurs râleries que tel warning ne leur plaît pas (ils n'avaient qu'à ne pas l'activer !). Certains warnings sont des questions de style, et il est normal d'avoir un warning qui dit de réécrire A en B et si on le fait un autre warning dira de le réécrire en A. -Wall et -Wextra fournissent des sous-ensembles raisonnables pour gens qui n'ont pas envie de se farcir la liste de tous les -W* pour faire leur marché. Si -Wconversion n'est pas inclus dedans pour une release donnée (ça a pu changer plusieurs fois), c'est parce qu'il n'est pas très au point (trop de faux positifs), mais il reviendra dedans quand quelqu'un se sera motivé pour l'améliorer (j'invite d'ailleurs les participants à cette conversation...).
Lucas Levrel wrote:
Le 4 décembre 2012, Jean-Marc Bourguet a écrit :
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un
sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas
d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que
les utilisateurs risqueraient de mal l'utiliser et de faire perdre des
heures à tout le monde avec leurs râleries que tel warning ne leur plaît
pas (ils n'avaient qu'à ne pas l'activer !). Certains warnings sont des
questions de style, et il est normal d'avoir un warning qui dit de
réécrire A en B et si on le fait un autre warning dira de le réécrire en
A. -Wall et -Wextra fournissent des sous-ensembles raisonnables pour
gens qui n'ont pas envie de se farcir la liste de tous les -W* pour
faire leur marché. Si -Wconversion n'est pas inclus dedans pour une
release donnée (ça a pu changer plusieurs fois), c'est parce qu'il n'est
pas très au point (trop de faux positifs), mais il reviendra dedans
quand quelqu'un se sera motivé pour l'améliorer (j'invite d'ailleurs les
participants à cette conversation...).
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que les utilisateurs risqueraient de mal l'utiliser et de faire perdre des heures à tout le monde avec leurs râleries que tel warning ne leur plaît pas (ils n'avaient qu'à ne pas l'activer !). Certains warnings sont des questions de style, et il est normal d'avoir un warning qui dit de réécrire A en B et si on le fait un autre warning dira de le réécrire en A. -Wall et -Wextra fournissent des sous-ensembles raisonnables pour gens qui n'ont pas envie de se farcir la liste de tous les -W* pour faire leur marché. Si -Wconversion n'est pas inclus dedans pour une release donnée (ça a pu changer plusieurs fois), c'est parce qu'il n'est pas très au point (trop de faux positifs), mais il reviendra dedans quand quelqu'un se sera motivé pour l'améliorer (j'invite d'ailleurs les participants à cette conversation...).
espie
In article <k9lo7q$lsq$, Marc wrote:
Lucas Levrel wrote:
Le 4 décembre 2012, Jean-Marc Bourguet a écrit :
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que les utilisateurs risqueraient de mal l'utiliser et de faire perdre des heures à tout le monde avec leurs râleries que tel warning ne leur plaît pas (ils n'avaient qu'à ne pas l'activer !).
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce dont il a envie. Rien de tres surprenant pour gcc donc.
Apres, le fonctionnement des warnings dans gcc est un vrai gros bordel. On ne peut qu'esperer que clang, etant parti de zero plus recemment, ne fera pas les memes conneries.
In article <k9lo7q$lsq$1@news-rocq.inria.fr>,
Marc <marc.glisse@gmail.com> wrote:
Lucas Levrel wrote:
Le 4 décembre 2012, Jean-Marc Bourguet a écrit :
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un
sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas
d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que
les utilisateurs risqueraient de mal l'utiliser et de faire perdre des
heures à tout le monde avec leurs râleries que tel warning ne leur plaît
pas (ils n'avaient qu'à ne pas l'activer !).
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce
dont il a envie. Rien de tres surprenant pour gcc donc.
Apres, le fonctionnement des warnings dans gcc est un vrai gros bordel.
On ne peut qu'esperer que clang, etant parti de zero plus recemment, ne
fera pas les memes conneries.
Le all n'a jamais signifié tout dans -Wall, ca a toujours ete un sous-ensemble des warnings
Et même -Wextra ne suffit pas à tous les activer. Apparemment il n'y a pas d'option pour dire « vraiment tout ».
clang a un -Weverything. gcc a toujours refusé de le créer, parce que les utilisateurs risqueraient de mal l'utiliser et de faire perdre des heures à tout le monde avec leurs râleries que tel warning ne leur plaît pas (ils n'avaient qu'à ne pas l'activer !).
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce dont il a envie. Rien de tres surprenant pour gcc donc.
Apres, le fonctionnement des warnings dans gcc est un vrai gros bordel. On ne peut qu'esperer que clang, etant parti de zero plus recemment, ne fera pas les memes conneries.
Dominique MICOLLET
Bonjour,
Marc Espie a écrit :
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce dont il a envie. Rien de tres surprenant pour gcc donc.
Ben, faut dire aussi que certains utilisateurs de gcc - moi par exemple :-) - n'ont pas lu la totalité de la documentation dudit gcc. Donc les ch oix par défaut sont peut-être un moindre mal, s'ils sont fondés sur l'exp érience.
Promis, un de ces jours, je lirai toute la partie "warning" de la doc d e gcc.
Cordialement
Dominique.
Bonjour,
Marc Espie a écrit :
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce
dont il a envie. Rien de tres surprenant pour gcc donc.
Ben, faut dire aussi que certains utilisateurs de gcc - moi par exemple :-)
- n'ont pas lu la totalité de la documentation dudit gcc. Donc les ch oix par
défaut sont peut-être un moindre mal, s'ils sont fondés sur l'exp érience.
Promis, un de ces jours, je lirai toute la partie "warning" de la doc d e
gcc.
Etat d'esprit un peu arrogant, genre on sait mieux que l'utilisateur ce dont il a envie. Rien de tres surprenant pour gcc donc.
Ben, faut dire aussi que certains utilisateurs de gcc - moi par exemple :-) - n'ont pas lu la totalité de la documentation dudit gcc. Donc les ch oix par défaut sont peut-être un moindre mal, s'ils sont fondés sur l'exp érience.
Promis, un de ces jours, je lirai toute la partie "warning" de la doc d e gcc.
Cordialement
Dominique.
Dominique MICOLLET
Bonjour,
Manuel Pégourié-Gonnard a écrit :
Là, les 32 bits sont imposés par la structure du nombre quasi-de Mersenne. Imaginons par exemple que je veuille réduire un nombre rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapi de passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait de le voir comme une suite de blocs de 32 bits. Et effectivement, c'e st moins sympathique sur les archis 64 bits, mais il faut faire avec.
Je suis complètement largué, et je n'ai pas honte :-). Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer u ne lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce q u'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sa is pas ce que représente l'opération "réduire").
Cordialement
Dominique.
Bonjour,
Manuel Pégourié-Gonnard a écrit :
Là, les 32 bits sont imposés par la structure du nombre quasi-de
Mersenne. Imaginons par exemple que je veuille réduire un nombre
rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapi de
passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait
de le voir comme une suite de blocs de 32 bits. Et effectivement, c'e st
moins sympathique sur les archis 64 bits, mais il faut faire avec.
Je suis complètement largué, et je n'ai pas honte :-).
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer u ne
lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce q u'est
un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sa is
pas ce que représente l'opération "réduire").
Là, les 32 bits sont imposés par la structure du nombre quasi-de Mersenne. Imaginons par exemple que je veuille réduire un nombre rapidement modulo 2^224 - 2^96 + 1 : la façon de faire la plus rapi de passe par l'écriture dudit nombre en base 2^32, c'est-à-dire par le fait de le voir comme une suite de blocs de 32 bits. Et effectivement, c'e st moins sympathique sur les archis 64 bits, mais il faut faire avec.
Je suis complètement largué, et je n'ai pas honte :-). Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer u ne lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce q u'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sa is pas ce que représente l'opération "réduire").
Cordialement
Dominique.
Francois Lafont
Le 05/12/2012 08:57, Dominique MICOLLET a écrit :
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit, c'est trouver le reste r de la division euclidienne de A par n.
Enfin Manuel rectifiera si je dis une bêtise mais je ne crois pas.
-- François Lafont
Le 05/12/2012 08:57, Dominique MICOLLET a écrit :
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une
lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est
un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais
pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r
appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit,
c'est trouver le reste r de la division euclidienne de A par n.
Enfin Manuel rectifiera si je dis une bêtise mais je ne crois pas.
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit, c'est trouver le reste r de la division euclidienne de A par n.
Enfin Manuel rectifiera si je dis une bêtise mais je ne crois pas.
-- François Lafont
Manuel Pégourié-Gonnard
Francois Lafont scripsit :
Le 05/12/2012 08:57, Dominique MICOLLET a écrit :
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Absolument.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit, c'est trouver le reste r de la division euclidienne de A par n.
Précisément. Donc l'opération "réduire a modulo n", si a et n sont des entiers non signés, c'est a = a % n en C (vague tentative de retour en charte).
Bon, prenons l'exemple de n = 2^64 - 1, qu'on peut appeler un nombre (non premier) de Mersenne, et considérons un entier multiprécision qu'on veut réduire modulo n, on suppose qu'il est strictement inférieur à 2^128. On peut donc l'écrire a = a1 * 2^64 + a0 où a1 et a0 sont strictement inférieurs à 2^64 (donc, sur une machine 64 bits, des entiers, sur une machine 32 bits, des tableaux de 2 entiers, etc.).
On peut calculer a mod n rapidement (en tout cas plus rapidement qu'un algo générique) en remarquant que
2^64 = 1 (mod n), donc a = a1 + a0 (mod n)
On calcule donc a1 + a0, et comme ça vaut au plus 2n - 2, il ne reste plus qu'à éventuellement soutraire une fois n pour arriver à a mod n.
Les premiers de Mersenne, c'est des nombres premiers de la forme 2^p - 1. Comme il n'y en a pas tant que ça, on utilise aussi des nombres premiers de pseudo-Mersenne (ou quasi-Mersenne, ou Mersenne généralisé), qui sont des sommes signées d'un petit nombre de puissances de 2, avec exposants en général multiples de 32 (voire de 64) par exemple 2^224 - 2^96 + 1, pour pourvoir réduire rapidement modulo ces premiers, dans des applications cryptographiques. Voir par exemple l'annexe D.2 de http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf pour des nombres de (pseudo-)Mersenne couramment utilisés en crypto elliptique.
(Désolé pour le HS, si vous étes curieux et souhaitez plus de détails, on peut continuer sur fr.sci.math ou en privé.)
-- Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Francois Lafont scripsit :
Le 05/12/2012 08:57, Dominique MICOLLET a écrit :
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Absolument.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une
lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est
un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais
pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r
appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit,
c'est trouver le reste r de la division euclidienne de A par n.
Précisément. Donc l'opération "réduire a modulo n", si a et n sont des
entiers non signés, c'est a = a % n en C (vague tentative de retour en
charte).
Bon, prenons l'exemple de n = 2^64 - 1, qu'on peut appeler un nombre
(non premier) de Mersenne, et considérons un entier multiprécision qu'on
veut réduire modulo n, on suppose qu'il est strictement inférieur à
2^128. On peut donc l'écrire a = a1 * 2^64 + a0 où a1 et a0 sont
strictement inférieurs à 2^64 (donc, sur une machine 64 bits, des
entiers, sur une machine 32 bits, des tableaux de 2 entiers, etc.).
On peut calculer a mod n rapidement (en tout cas plus rapidement qu'un
algo générique) en remarquant que
2^64 = 1 (mod n), donc a = a1 + a0 (mod n)
On calcule donc a1 + a0, et comme ça vaut au plus 2n - 2, il ne reste
plus qu'à éventuellement soutraire une fois n pour arriver à a mod n.
Les premiers de Mersenne, c'est des nombres premiers de la forme
2^p - 1. Comme il n'y en a pas tant que ça, on utilise aussi des nombres
premiers de pseudo-Mersenne (ou quasi-Mersenne, ou Mersenne généralisé),
qui sont des sommes signées d'un petit nombre de puissances de 2, avec
exposants en général multiples de 32 (voire de 64) par exemple
2^224 - 2^96 + 1, pour pourvoir réduire rapidement modulo ces premiers,
dans des applications cryptographiques. Voir par exemple l'annexe D.2 de
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf pour des
nombres de (pseudo-)Mersenne couramment utilisés en crypto elliptique.
(Désolé pour le HS, si vous étes curieux et souhaitez plus de détails,
on peut continuer sur fr.sci.math ou en privé.)
--
Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Je suis complètement largué, et je n'ai pas honte :-).
Faut pas.
Absolument.
Bien que ce soit hors propos dans ce forum, pourriez-vous me proposer une lecture sur ce sujet qui puisse satisfaire ma curiosité (je sais ce qu'est un modulo, je crois savoir ce qu'est un nombre de Mersenne, et je ne sais pas ce que représente l'opération "réduire").
Réduire un entier A modulo n, selon moi, c'est trouver l'unique entier r appartenant à {0; 1; ...; n-1} tel que A = r (mod n). Autrement dit, c'est trouver le reste r de la division euclidienne de A par n.
Précisément. Donc l'opération "réduire a modulo n", si a et n sont des entiers non signés, c'est a = a % n en C (vague tentative de retour en charte).
Bon, prenons l'exemple de n = 2^64 - 1, qu'on peut appeler un nombre (non premier) de Mersenne, et considérons un entier multiprécision qu'on veut réduire modulo n, on suppose qu'il est strictement inférieur à 2^128. On peut donc l'écrire a = a1 * 2^64 + a0 où a1 et a0 sont strictement inférieurs à 2^64 (donc, sur une machine 64 bits, des entiers, sur une machine 32 bits, des tableaux de 2 entiers, etc.).
On peut calculer a mod n rapidement (en tout cas plus rapidement qu'un algo générique) en remarquant que
2^64 = 1 (mod n), donc a = a1 + a0 (mod n)
On calcule donc a1 + a0, et comme ça vaut au plus 2n - 2, il ne reste plus qu'à éventuellement soutraire une fois n pour arriver à a mod n.
Les premiers de Mersenne, c'est des nombres premiers de la forme 2^p - 1. Comme il n'y en a pas tant que ça, on utilise aussi des nombres premiers de pseudo-Mersenne (ou quasi-Mersenne, ou Mersenne généralisé), qui sont des sommes signées d'un petit nombre de puissances de 2, avec exposants en général multiples de 32 (voire de 64) par exemple 2^224 - 2^96 + 1, pour pourvoir réduire rapidement modulo ces premiers, dans des applications cryptographiques. Voir par exemple l'annexe D.2 de http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf pour des nombres de (pseudo-)Mersenne couramment utilisés en crypto elliptique.
(Désolé pour le HS, si vous étes curieux et souhaitez plus de détails, on peut continuer sur fr.sci.math ou en privé.)
-- Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
Antoine Leca
Manuel Pégourié-Gonnard écrivit :
Marc Espie scripsit :
tes printf sont buggues. Ils masquent une promotion,
Tu veux dire que b sera promu en unsigned int ?
Non, c'est le contraire. Sur une machine 16 bits, uint16_t va être passé comme unsigned, ce qu'attend le %X, ce sera OK. Sur n'importe quelle autre machine, il y aura promotion en signed int, et officiellement ce n'est pas ce qu'attend %X.
Antoine
Manuel Pégourié-Gonnard écrivit :
Marc Espie scripsit :
tes printf sont buggues. Ils masquent une promotion,
Tu veux dire que b sera promu en unsigned int ?
Non, c'est le contraire. Sur une machine 16 bits, uint16_t va être passé
comme unsigned, ce qu'attend le %X, ce sera OK. Sur n'importe quelle
autre machine, il y aura promotion en signed int, et officiellement ce
n'est pas ce qu'attend %X.
tes printf sont buggues. Ils masquent une promotion,
Tu veux dire que b sera promu en unsigned int ?
Non, c'est le contraire. Sur une machine 16 bits, uint16_t va être passé comme unsigned, ce qu'attend le %X, ce sera OK. Sur n'importe quelle autre machine, il y aura promotion en signed int, et officiellement ce n'est pas ce qu'attend %X.
Antoine
Antoine Leca
Dominique MICOLLET écrivit :
Manuel Pégourié-Gonnard a écrit :
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32
Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage ne devrait-elle pas être l'octet ? Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à l'architecture du processeur :
Oui, et surtout pour améliorer substantiellement les performances
mais il va y avoir des soucis avec les processeurs 64 bits,
En dehors d'une possible perte de performances par rapport à une version tout en 64 bits (pour exploiter encore plus le processeur, mais qui coûte en temps humain), en supposant que le processeur 64 bits implémente le support suffisant des opérations en 32 bits (ce qui est le cas en pratique), je ne vois pas pourquoi il y aurait des soucis ?
Antoine
Dominique MICOLLET écrivit :
Manuel Pégourié-Gonnard a écrit :
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32
Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage
ne devrait-elle pas être l'octet ?
Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à
l'architecture du processeur :
Oui, et surtout pour améliorer substantiellement les performances
mais il va y avoir des soucis avec les processeurs 64 bits,
En dehors d'une possible perte de performances par rapport à une version
tout en 64 bits (pour exploiter encore plus le processeur, mais qui
coûte en temps humain), en supposant que le processeur 64 bits
implémente le support suffisant des opérations en 32 bits (ce qui est le
cas en pratique), je ne vois pas pourquoi il y aurait des soucis ?
Il s'agit, dans des entiers multi-précision, de déplacer des blocs de 32
Toutefois lorsqu'on parle d'entier multiprécision, la granularité du codage ne devrait-elle pas être l'octet ? Je conçois qu'on puisse vouloir utiliser 32 bits pour se conformer à l'architecture du processeur :
Oui, et surtout pour améliorer substantiellement les performances
mais il va y avoir des soucis avec les processeurs 64 bits,
En dehors d'une possible perte de performances par rapport à une version tout en 64 bits (pour exploiter encore plus le processeur, mais qui coûte en temps humain), en supposant que le processeur 64 bits implémente le support suffisant des opérations en 32 bits (ce qui est le cas en pratique), je ne vois pas pourquoi il y aurait des soucis ?
