Brevet FR2849941A1 — publié le 20040716

{iÄj: PU= j! i ARRIERE-PLAN DE L'INVENTION Il existe différentes méthodes pour obtenir des 10 puissances entières, tels que l'exponentiation standard, l'exponentiation rapide, ou encore l'exponentiation BGCW. Ces méthodes sont mises en oeuvre à l'aide de processeurs spécialisés dans lesquels l'algorithme correspondant est câblé en dur, ou encore à l'aide d'un ou de 15 plusieurs processeurs non spécialisés exécutant l'algorithme programmé. Ces algorithmes ne permettent pas le calcul de séries de puissance entières ou de séries de séries de puissances entières. A cet effet, il faut mettre en oeuvre 20 un programme spécifique qui provoque le calcul des puissances entières successives et somme les puissances entières ainsi obtenues en séries de puissances entières. Dans des applications de cryptologie ou de calcul scientifique, le nombre de calcul et la taille des nom25 bres ainsi calculés peuvent rendre le temps cumulé de calcul relativement important. OBJET DE L'INVENTION L'invention vise à proposer un procédé d'obtention pouvant être mis en oeuvre sur des moyens in30 formatiques très simples et permettant de réduire le temps d'obtention de tels nombres. BREVE DESCRIPTION DE L'INVENTION Selon l'invention, on propose un procédé d'obtention de puissances entières ou de séries de puis35 sances entières au moyen d'un dispositif informatique comprenant un moyen de stockage et une unité de calcul, comportant les étapes de: - stocker au préalable dans le moyen de stockage: * des termes d'une première sous-matrice Pp de 5 Pascal de rang p, extraite d'une matrice de Pascal de terme courant (i2jI: PU= jj); i Ainsi, l'obtention de termes aussi complexes que 20 des puissances ou des séries de puissances entières revient à un simple produit scalaire qui peut être mis en oeuvre sur des moyens informatiques très rudimentaires ne faisant pas appel à des processeurs spécialisés ni à des algorithmes de calcul complexes. Le nombre de multiplications est réduit au nombre minimal de termes de la ligne ou de la colonne concernée, ce qui réduit le nombre de multiplications par rapport à un calcul direct, et par conséquence le temps d'obtention du résultat recherché. Dans tout le texte, on entend par j-ième sousmatrice Mk de rang k d'une matrice M donnée la sousmatrice de rang k extraite de la matrice M dont le premier terme diagonal est le j-ième terme diagonal de la matrice M. Selon un aspect particulier de l'invention, pour obtenir la puissance entière qr o q et r sont inférieurs à n, on provoque le produit des termes non nuls de la q5 ième ligne de la première sous-matrice de rang n extraite de la sous-matrice de Pascal Pp stockée, et les termes non nuls de la r-ième colonne de la première sous-matrice de Bachkat Bn. Le nombre de multiplications est alors égal au 10 minimum de q et r, ce qui réduit considérablement les opérations à effectuer. Selon un autre aspect particulier de l'invention, q pour obtenir la série de puissances entières YWsr, on S=O provoque le produit des termes non nuls de la q-ième li15 gne de la deuxième sous-matrice de rang n extraite de la sous-matrice de Pascal Pp stockée, et des termes non nuls de la rième ligne de la première sous-matrice de Bachkat B,. De la même façon, le nombre de multiplications 20 est alors égal au minimum de q et r, ce qui réduit considérablement les opérations à effectuer. Selon l'invention, on propose également un dispositif pour mettre en oeuvre le procédé précédent, qui comporte: - une première zone mémoire pour le stockage de la première sous-matrice de Pascal PP; - une deuxième zone mémoire pour le stockage de la première sous-matrice de Bachkat Bn; un circuit d'entrée de paramètres d'entrée re30 latifs au calcul à effectuer; - une unité de calcul apte à effectuer le produit de termes en ligne de la première sous-matrice de Pascal Pp et de termes en colonne de la première sous-matrice de Bachkat Bn; - un moyen de sélection pour, en fonction des paramètres d'entrée, sélectionner les termes de la première sous-matrice de Pascal Pp et les termes de la première sous-matrice de Bachkat Bn à fournir à l'unité de cal5 cul; - et un circuit de sortie relié à l'unité centrale et apte à fournir le résultat du produit. Ce dispositif est très simple, et peut par exemple être intégré dans le microprocesseur d'une carte à 10 microprocesseur. Selon un mode particulier de réalisation du dispositif de l'invention, le moyen de sélection est apte à sélectionner un des termes des matrices stockées dans les zones mémoire en fonction des paramètres d'entrée, le 15 circuit de sortie étant apte à fournir le terme ainsi sélectionné. En effet, la première sous-matrice de Pascal est composée de coefficients combinatoires, qui peuvent être fournis directement sans calcul puisqu'ils sont déjà 20 stockés en mémoire. De même, la diagonale de la première sous-matrice de Bachkat est composée de factorielles qui peuvent également être fournies sans calcul. Le dispositif permet donc de fournir tout à la fois des termes aussi complexes que les puissances, sé25 ries de puissances, factorielles, coefficients combinatoires, en faisant appel à des moyens informatiques très simples et en requérant un minimum d'opérations, donc de temps de calcul. Selon un mode avantageux de réalisation du dispo30 sitif de l'invention, celui-ci comporte des zones de mémoire cache associées aux zones mémoires, le moyen de sélection étant apte à scruter préalablement le contenu des zones de mémoire cache avant de scruter le contenu des zones mémoires. La recherche préalable dans la zone mémoire ca- 10 che, d'accès rapide des données qui peuvent s'y trouver (si elles ont été utilisées récemment) permet d'accélérer encore l'obtention des nombres recherchés. BREVE DESCRIPTION DES DESSINS L'invention sera mieux comprise à la lumière de la description qui suit en référence à l'unique figure illustrant schématiquement un dispositif selon l'invention apte à la mise en oeuvre du procédé selon l'invention. DESCRIPTION DETAILLEE DE L'INVENTION L'invention est basée sur l'utilisation de deux matrices qui sont cidessous explicitées. La première est la matrice de Pascal P qui est une matrice triangulaire de dimension infinie dont les coefficients sont égaux à i La seconde matrice est la matrice de Bachkat B qui est une matrice triangulaire de dimension infinie, 5 qui peut être définie de la façon suivante: les premières sous-matrices de rang n de la matrice de Bachkat sont définies par: B, = MnPEn o Mn est la matrice de rang n et de terme courant mi,=i-, et Pe est la première sous-matrice de rang n de la matrice de Pascal P. Seule une partie de dimensions finie de la ma15 trice B est stockée dans la mémoire. On explicite cidessous la première sous-matrice de rang 10 appelée dans la suite B1o: 1 1 1 1 1 1 1 1 1 2 6 14 30 62 126 254 510 6 36 150 540 1806 5796 18150 24 240 1560 8400 40824 186480 120 1800 16800 126000 834120 720 15120 191520 1905120 5040 14112 2328480 40320 1451520 Les éléments non explicités sont identiquement nuls. On observera que la diagonale de la matrice de Bachkat correspond aux factorielles: B1j=i!. On démontre qu'une puissance entière d'un entier peut se déduire de la simple multiplication d'une ligne 25 de la matrice de Pascal par une colonne de la matrice de Bachkat. Ainsi, par exemple, le nombre 49 est obtenu en effectuant le produit de la neuvième ligne de la première sous-matrice de Bachkat Bo10 par la quatrième colonne de 5 la première sous-matrice de rang 10 de la matrice de Pascal P, ici extraite de la sous-matrice de Pascal P13 et illustrée ci-dessous: 2 1 3 3 4 4 5 10 6 15 7 21 8 28 9 36 20 35 56 84 15 35 70 126 21 56 126 7 28 84 8 36 45 120 11 55 165 12 66 220 330 495 462 792 462 924 330 792 165 495 1 55 11 1 220 66 12 Etant donné que les matrices sont triangulaires, ce produit ne nécessite que quatre multiplications (le nombre de multiplications est égal au minimum de 4 et 9), alors que le calcul direct aurait nécessité huit multiplications. On montre également que les séries de puissances entières sont obtenues par le produit d'une ligne de la matrice de Pascal et d'une colonne de la matrice de Bachkat. Par exemple, le calcul du nombre 1+29+39+49 se 20 fait en multipliant la neuvième ligne de la première sous-matrice de Bachkat B10 par la quatrième ligne la deuxième sous-matrice de rang 10 de la matrice de Pascal P. ici tirée de la sous-matrice de Pascal P13 et illustrée ci- dessous: i 1 11 2 1 3 3 1 4 4 6 1 10 10 5 1 6 15 20 15 6 1 7 21 35 35 21 7 1 8 28 56 70 56 28 8 1 9 36 84 126 126 84 36 9 1 10 45 120 210 252 210 120 45 10 1 11 55 165 330 462 462 330 165 55 11 1 12 66 220 495 792 924 792 495 220 66 12 Etant donné que les matrices sont triangulaires, le produit ne nécessite que 4 multiplications (minimum de 4 et 9), alors que le calcul direct aurait nécessité 32 multiplications. On démontre encore que les séries de séries de 10 puissances sont obtenus par le produit d'une ligne de la matrice de Pascal par une colonne de la matrice de Bachkat. Par exemple le nombre (1)+(1+29)+(1+29+39)+(1+29+39+49) se calcule en multipliant la neuvième colonne de la pre15 mière sous-matrice de Bachkat B0lo par la quatrième ligne de la troisième sous-matrice de rang 10 de la matrice de Pascal P, ici tirée de la sous-matrice de Pascal P13 et illustrée ci-dessous: 1 2 1 1 3 3 1 1 4 4 6 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 Ce calcul ne comporte que quatre multiplications 5 (minimum de 4 et de 9), alors que le calcul direct en aurait nécessité 90. On peut continuer ainsi la récurrence, en sélectionnant la sous-matrice de Pascal adéquate. Le rang 10 fixe le maximum des paramètres du cal10 cul des puissances, c'est-à-dire que l'on peut calculer toutes les puissances entières qr o q et r sont inférieurs à 10. Le rang 13 fixe quant à lui le niveau d'imbrications des séries que l'on peut calculer, ici des séries de séries de séries de puissances dont 15 l'intégrande et/ou l'opérande est égal à 9. Le procédé de l'invention peut être mis en oeuvre à l'aide du dispositif illustré à la figure 1. Le dispositif comporte une unité d'entrée 3, par exemple un clavier similaire à celui d'une calculette, 20 apte à recevoir divers paramètres d'entrée, dont un paramètre de type de calcul à effectuer (puissance, série de puissances, factoriel, combinaison...), et des paramètres numériques concernant le calcul lui-même (intégrande et opérande d'une puissance, paramètres d'un coefficient combinatoire, nombre dont on veut obtenir la factorielle...) Le dispositif comporte par ailleurs une première mémoire morte 1 dans laquelle est stockée une première sousmatrice Pp de rang p de la matrice de Pascal P, et une seconde mémoire morte 2 dans laquelle est stockée une première sous-matrice Bn de rang n de la matrice de Bach10 kat B, o n est inférieur ou égal à p. Les mémoires mortes 1,2 sont respectivement associées à des mémoires cache 10, 20 qui contiennent les dernières données qui ont été lues dans les mémoires mortes. Les mémoires caches évitent, comme cela est connu 15 en soi, des opérations répétitives de lecture dans la mémoire morte de données identiques intervenant dans des calculs successifs, et font ainsi économiser du temps d'accès. Les mémoires mortes 1,2 associées à leurs mémoi20 res cache 10,20 forment des zones mémoire 100,200, symbolisées en traits interrompus, aptes à fournir aux autres composants du dispositif les données qui y sont contenues. Le dispositif comprend en outre une unité de cal25 cul 4 apte à calculer le produit de termes en ligne tirés de la matrice de Pascal par des termes en colonne tirés de la matrice de Bachkat, l'unité de calcul 4 étant reliée aux zones mémoire 100, 200 pour en recevoir lesdits termes. Le dispositif comprend également une unité de sortie 5 (par exemple un écran) apte à fournir le résultat du produit effectué l'unité de calcul, ou des termes tirés des zones mémoire 100, 200 par simple lecture. Le fonctionnement du dispositif est le suivant. 35 Lorsque l'on veut obtenir une puissance qr, une série de puissances Sxr, on entre dans le dispositif grâce à s=O l'unité d'entrée 3 le type de calcul à effectuer ainsi que les deux entiers qr. L'unité d'entrée adresse alors les zones mémoires 5 100,200 pour provoquer l'envoi vers l'unité de calcul 4 des termes non nuls de la q- ième ligne de la sous-matrice de rang n adéquate de la première sous- matrice de Pascal Pp et des termes non nuls de la r-ième colonne de la première sous-matrice de Bachkat Bn. L'unité de calcul 4 effectue le produit scalaire des termes en ligne et des termes en colonne, et envoie le résultat vers l'unité de sortie 5. Lorsque l'on veut obtenir des termes factoriels ou combinatoires, on entre dans le dispositif grâce à 15 l'unité d'entrée 3 le type de terme à obtenir ainsi que les paramètres numériques du calcul. L'unité d'entrée 3 adresse alors les mémoires 100,200 pour provoquer l'envoi vers le dispositif de sortie 5 du terme correspondant, pris sur la diagonale de la 20 première sous-matrice de Bachkat B, en ce qui concerne les factorielles ou pris dans l'un des emplacements mémoire contenant les termes de la première sous-matrice de Pascal Pp en ce qui concerne les coefficients binomiaux. On obtient ainsi un dispositif extrêmement sim25 ple, capable de fournir des termes complexes tels que des puissances, séries de puissances, factorielles, coefficients combinatoires, tout en étant réalisé avec des moyens informatiques rudimentaires et requérant un minimum de calcul. L'invention n'est pas limitée aux modes particuliers de réalisation de l'invention qui viennent d'être décrits, mais bien au contraire englobe toute variante entrant dans le cadre de l'invention tel que défini par les revendications. REVENDICATI ONS 1. Procédé d'obtention de puissances entières ou de séries de puissances entières au moyen d'un dispositif 5 informatique comprenant un moyen de stockage (100,200) et une unité de calcul (4), caractérisé en ce qu'il comporte les étapes de: - stocker au préalable dans le moyen de stockage (100,200) : * des termes d'une première sous-matrice Pp de Pascal de rang p, extraite d'une matrice de Pascal de terme courant pÄj: Pij=l(i; i 2. Procédé selon la revendication 1, caractérisé en ce que pour obtenir la puissance entière qr o q et r sont inférieurs à n, on provoque le produit des termes non nuls de la q-ième ligne de la première sous- matrice de rang n extraite de la sous-matrice de Pascal Pp stoc30 kée, et les termes non nuls de la r-ième colonne de la première sous-matrice de Bachkat B,. 3. Procédé selon la revendication 2, caractérisé en ce que pour obtenir la série de puissances entières Es', on provoque le produit des termes non nuls de la qs=O ième ligne de la deuxième sous-matrice de rang n extraite de la sous-matrice de Pascal Pp stockée, et des termes non nuls de la r-ième ligne de la première sous-matrice de Bachkat Bn4. Dispositif pour mettre en oeuvre l'un quelconque des procédés des revendications 1 à 3, caractérisé en ce qu'il comporte - une première zone mémoire pour le stockage de 10 la première sous- matrice de Pascal Pp; - une deuxième zone mémoire pour le stockage de la première sous-matrice de Bachkat Bn; - un circuit d'entrée de paramètres d'entrée relatifs au calcul à effectuer; une unité de calcul apte à effectuer le produit de termes en ligne extraits de la première sous-matrice de Pascal Pp et de termes en colonne extraits de la première sous-matrice de Bachkat Bn; - un moyen de sélection pour, en fonction des pa20 ramètres d'entrée, sélectionner les de la première sousmatrice de Pascal Pp et les termes de la première sousmatrice de Bachkat Bn à fournir à l'unité de calcul; - un circuit de sortie relié à l'unité centrale apte à fournir le résultat du produit. 5. Dispositif de calcul selon la revendication 4, caractérisé en ce que le moyen de sélection est apte à sélectionner un des termes des matrices stockées dans les zones mémoire en fonction des paramètres d'entrée et en ce que le circuit de sortie est apte à fournir le terme 30 ainsi sélectionné. 6. Dispositif de calcul selon la revendication 4 ou la revendication 5, caractérisé en ce qu'il comporte des zones de mémoire cache associées aux zones mémoires, et en ce que le moyen de sélection est apte à scruter préalablement le contenu des zones de mémoire cache avant de scruter le contenu des zones mémoires.