[PDF] Florent CHABAUD RECHERCHE DE PERFORMANCE DANS L

View - Download Florent CHABAUD RECHERCHE DE PERFORMANCE DANS L

Previous PDF

Next PDF

Th?ese pr?esent?ee p our obtenir le grade deDOCTEURDEL? ?ECOLEPOLYTECHNIQUEsp?ecialit?e :

INFORMATIQUEpar

FlorentCHABAUDTitre :

?ALACRYPTOGRAPHIE?Soutenue le 22 o ctobre 1996 devant le jury comp os?e de :

M?JacquesSTERNDirecteurMM?PaulCAMIONRapp orteursJeanVUILLEMINMme?PascaleCHARPINExaminateursMM?AntoineJOUXFran?coisMORAIN

Th?ese pr?esent?ee p our obtenir le grade deDOCTEURDEL? ?ECOLEPOLYTECHNIQUEsp?ecialit?e :

INFORMATIQUEpar

FlorentCHABAUDTitre :

?ALACRYPTOGRAPHIE?Soutenue le 22 o ctobre 1996 devant le jury comp os?e de :

M?JacquesSTERNDirecteurMM?PaulCAMIONRapp orteursJeanVUILLEMINMme?PascaleCHARPINExaminateursMM?AntoineJOUXFran?coisMORAIN

Recherchese?ectu?ees au Lab oratoire d?Informatique de l? ?Ecole Normale Sup?erieureURA 1327 du CNRS45? rue d?Ulm? 75230 Paris Cedex 05 RemerciementsJe tiens tout d?abord ?a remercier tous ceux que j?ai pu omettre dans ce qui suit?

Cependant je ne puis oublier Jean Vuil lemin qui a bien voulu e?ectuer le travail di?cile de rapporteur et

dont les remarques ont fortement contribu?e ?a rendre cette th?ese plus lisible?Je tiens de m?eme ?a remercier Paul Camion dont l?aide a ?et?e pr?ecieuse? en particulier pour la r?edaction

du chapitre I?4? Les am?eliorations en cours de la librairieZendoivent beaucoup aux remarques et r?ef?erencesbibliographiques qu?il m?a communiqu?ees ?a la lecture de la premi?ere version de ce chapitre?Merciaussi?atouteson?equipeduprojet CODESdel?INRIA pourleur accueilchaleureuxlorsdemesvisites? ettout d?abord ?aPascale Charpinqui me fait l?honneurdeparticiper ?a monmonjury deth?ese? etdont les r?eponses ?a mes nombreuses questions ont toujours ?et?e pertinentes?Je ne saurais oublier Anne Canteaut pour le travail fructueux que nous avons r?ealis?e ensemble? ni Nicolas

Sendrier pour ses explications toujours p?edagogiques? Ma gratitude va aussi ?a Daniel Augot? entre autres pourson aide pr?ecieuse avec Axiom dans l?exemple comparatif de l?annexe A?2?Mais les membres de l?INRIA n?ont pas ?et?e les seuls ?a me supporter??? Le LIX m?a lui aussi souvent vu?

et en particulier Reynald Lercier? ?a quiZendoit beaucoup? et dont je loue au passage le travail de relecturedecetteth?ese?Lesdiscussionsparfoisdi?cilesquenousavonspuavoirensemble?ainsiqu?avecFran?coisMorain? ont toujours abouti ?a une am?elioration du r?esultat? Je ne peux donc que les remercier tous deux? Ma

reconnaissancevaaussi?a Jean?MarcSteyaert etMichel Weinfeldquiont aussibeaucoupcontribu?e ?acetteth?ese en me permettant de travail ler quasi?quotidiennement au LIX? Merci aussi ?a Evelyne Rayssac qui g?eremagistralement le secr?etariat du laboratoire? pour son aide dans les divers probl?emes administratifs que j?aipu rencontrer ?a cette occasion?Je remercie aussi la DGA de m?avoir permis d?e?ectuer ces travaux de recherche? Merci en particulier ?a

Alain Quenzer et ?a Alain Lanussepour leur gestion desoptionnaires Recherche? Merci aussi ?a la directiondu CELAR et ?a Fran?cois Debout d?avoir accept?e de ne pas me voir physiquement en poste parmi eux? En?nmerci?atoutel??equipedePhilippeVil loingpourleuraccueildepuisquejelesairejoints?enparticulier ?aFran?cois Daud?e? que j?ai connu lors d?un stage e?ectu?e il y a maintenant quatre ans? Je suis aussi redevable?aJacquelineDemarthonetElisabethDorionpourleurgestione?cacedececasparticulierd?unmembreduCELAR parisien? Je n?oublie pasMichel Minouxquim?a assist?e pendantcestrois ansde th?eseentantqueparrainscienti?que?alaDGAetquiauraitparticip?e ?amonjury sisescontraintesd?emploi dutempsnel?avaientemp?ech?e?Jen?oubliepasnonplusAntoineJoux?quisemblemepr?ec?ederdepuissond?epartduLIENS? puisquenousnousretrouvons ensemble auCELAR? Merci d?avoir ?et?e monparrain DGA et departiciper aujourd?hui ?a mon jury?Je dois aussi beaucoup ?a un autre Ing?enieur de l?Armement pass?e par le LIENS? Jean?Marc Couveignes?

J?esp?erequenoscol laborations?avenirserontencorefructueuses?Ildoitpara??treclaird?esormaisqueleLIENS a beaucoupcontribu?e ?a me faire aimer la recherche? Cela est certainement d ?u ?a l?ambiance amicaleetchaleureusequiyr?egne?L??equipeduGRECCest?acetitre particuli?erement agr?eable? etj?yaipass?edetr?es bons moments? Merci donc par ordre alphab?etique ?a Philippe B?eguin? avec qui j?ai pour la premi?ere foisdiscut?edusyst?emedeChen?merci?aJean?BernardFischerdontl?accueil?aRennesm?a?et?etr?esutile??aLouis Granboulan pour toutes ses astuces de ma??tre?esC?eshtmlqu?il est? ?a Philippe Hoogvorst qui m?a enparticulier conseil l?e l?id?ee dela section I?2?5? ?a DavidPointchevalpour tousles travaux e?ectu?esensemblesurdiverssujets??aSergeVaudenaypourlacryptanalyselin?eairequenousavionse?ectu?eeetquiavaitdonn?e ?5?CV94??De nombreuses personnes ont aussi contribu?e ?a divers titre ?a cette th?ese? Un grand merci ?a toute l??equipe

du SPI et en particulier ?a Jacques Beigbeder qui g?ere de main de ma??tre le r?eseau de l?ENS? m?eme quand je

4REMERCIEMENTSlance des process un peu partout ? Merci ?a Brigitte Van Elsen pour tout ce qu?el le apporte au DMI? merci ?a

Sabine Glasson? Annie Iapte?? Fabienne Meunier et Nicole Mourgues pour toutes les fois o ?u je les ai ennuy?eesavec mes probl?emes administratifs et o ?u el les m?ont r?epondu avec le sourire? Je remercie aussi Claus Schnorr

puisque c?est lui qui a attir?e mon attention sur le syst?eme de Chen lors d?un s?eminaire organis?e par ses soins?a Riezlern? Merci ?a Sami Harari du GECT? et Pascal V?eron pour de nombreuses discussions int?eressantes?Jetiensaussi?aremercier Gil les Brassard? ClaudeCr?epeauetDavidNaccache?Merci ?aOlivier Perretquim?aaid?e?autiliserenpartielesdisponibilit?esdur?eseaudel?ENSTA?Merci?aAntonel laCrestipoursestiramisus ??etaient?ils bonsSerge ??? Ungrandmerci ?aPatrick Grelier poursonp?enibleetmalgr?e toute?cace travail de relecture? ainsi qu??a Thierry Saurin et Fabrice Lefebvre du LIX?Merci ?a mes parents?En?n?lastbutnotleast?jemedoisd?exprimertoutemagratitude?aJacquesStern?quiparsonaideconstante a suscit?e en moi un int?er?et profond pour la recherche? J?esp?ere que ses nouvel les responsabilit?es dedirecteur du LIENS ne l?emp?echeront pas d?avoir avec moi d?autres conversations? car je sais d?avance toutl?int?er?et que l?on peut en tirer?

Intro duction?Lesoccasionsquiproduisentlesgrandschangementssontdi??erentes?maislescauses sont toujours les m?emes??Charles de Secondat de Montesquieu

De la Grandeur des Romains et de leur D?ecadenceD

ansunpremier temps?nous pr?esentons un nouvel outil de programmation? la librairieZen? qui a ?et?ed?evelopp?econjointement par l?auteur et Reynald Lercier? du Lab oratoire d?Informatique de l?

?EcolePolytechnique? Cette librairie p ermet la manipulation en langageCd?ob jets math?ematiques d?e?nis sur lescorps ?nis? voire sur des ensembles moins structur?es?Il estdonc naturelde commencer parrapp elerquelquesnotions d?alg?ebre ?chapitre I?1?? qui nous sontutiles par la suite dans la description de cet outil de programmation et des op?erations qui le constituent? Lalibrairie p ermet la manipulation des p olyn?omes? des matrices? des s?eries et des courb es elliptiques? Nous nepr?esentons pas les op?erations sur les s?eries et les courb es elliptiques puisque nous n?y avons pas contribu?e? Enrevanche? nous essayons d?expliquer la philosophie de la librairie dans le chapitre I?2? Il est toujours di?cile?dans le cadre d?un travail commun de programmation? de distinguer les contributions? Ce chapitre pr?esentedoncla librairie dans sonensemble? Il estclair quetouteslesp ossibilit?es d?ecritesnep euvent?etrele fruitd?un travail individuel? mais s?agissant de la conception profonde? il s?agit bien d?un travail commun?Dans les chapitres qui suivent? nous d?ecrivons quelquesfonctionnalit?es que nous avons implant?ees plusparticuli?erement? ceci a?n d?illustrer quelques uns des asp ectsde la programmation de la librairie? Le cha?pitre I?3 traite des op?erations sur les ?el?ements et en particulier de notre implantation de la multiplication deKaratsuba sur les grands entiers? Le probl?eme rencontr?e ici est d?implanter un algorithme bien connu de lameilleure fa?con p ossible? Le chapitre I?4 pr?esente lui un test d?irr?eductibilit?e de p olyn?ome bas?e en particuliersur l?algorithme de Berlekamp? Il sert d?illustration aux p ossibilit?es de la librairieZen? puisque la fonctionr?ealis?ee fonctionne quel que soit le corps ?ni utilis?e? En?n? le chapitre I?5 ?evo que les structuresde donn?eesutilis?ees dans l?implantation des op?erations matricielles de la librairie? Il s?agit l?a d?un probl?eme de nature unp eu di??erente? puisque les structures de donn?ees utilis?ees dans la description d?une matrice ont une in?uence

imp ortante sur les p erformances des op?erations matricielles?Cettepremi?erepartienesauraitdoncpasconstituerunedo cumentationdelalibrairieZenpuisqu?ysont omises b eaucoup de ses p ossibilit?es? d?evelopp?ees en particulier par Reynald Lercier? Elle se veut surtoutune intro duction aux p ossibilit?es de la librairie? et pr?esentecertainesastuces d?implantation qui rendent ler?esultat e?cace?L

a r

?ealisationd?untel outilne pr?esente d?int?er?et que par ses utilisations p ossibles? Nous pr?esentonsdoncdansun deuxi?emetemps deuxapplications au d?eco dageg?en?eraldeco deslin?eaires? Pourcela?nous rapp elons quelques notions d?alg?ebre dans le chapitre I I?1? Ce chapitre? prolongement du chapitre I?1?est plus sp?ecialement ax?e sur la th?eorie des co des? et intro duit les notions de base n?ecessaires? telles que lesm?etriques deHamming etde Gabidulin? Unenouvelle formulation du d?eco dagedesco desdeGabidulin yest aussi intro duite? Nous pr?esentons ensuite au chapitre I I?2 un algorithme probabiliste de d?eco dage g?en?eraldes co des correcteurs d?erreur en distance de Hamming? Cet algorithme? d?evelopp?e conjointement avec AnneCanteaut? nous p ermet en particulier de d?eterminer les distances minimales r?eelles de six co des BCH sur lesdouze encore inconnues en longueur 511?

6INTRODUCTIONLechapitre I I?3 d?ecritensuiteun algorithme? fruit d?une collab oration avec JacquesStern?qui p ermetled?eco dageg?en?erald?eterministedesco deslin?eairesendistancedeGabidulin?Unecons?equencedecetalgorithme est l?existence d?une b orne sur les dimensions des co des lin?eaires en m?etrique de Gabidulin? qui

am?eliore dans certains cas? la b orne de Singleton?B

ien qu?ayan tpermis d?obtenirquelquesr?esultatsdeth?eoriedesco des?cesalgorithmes ontp ourvo cation premi?erel?attaque dessyst?emes cryptographiquesbas?essurles co descorrecteursd?erreur?Nous pr?esentons donc certains de ces syst?emes et les r?esultats des attaques corresp ondantes ?chapitre I I I?1??avant de conclure ?chapitre I I I?2??Bien entendu? nous ne suivons pas l?ordre chronologique de ces r?esultats? puisque c?est la n?ecessit?e d?une

programmation e?cace de ces cryptanalyses qui a ?nalement conduit ?a l??elab oration de la librairieZen?

8TABLE DES MATI

10TABLE DES MATI

Premi?erepartieAlgorithmiquedescorps?nis

ChapitreI?1Rapp elsd?alg?ebre?H?e Dieu ? si j?eusse estudi?e Au temps de ma jeunesse fol le?Et ?a bonnes m?urs d?edi?e? J?eusse maison et couche mol le?Mais quoi? je fuyois l??ecole??Fran?cois Villon

Le Grand TestamentNousallonspr?esenterleplussuccintementp ossiblelesquelquesoutilsd?alg?ebredontnousavonsb esoin par la suite? Des descriptions plus d?etaill?ees existent dans de nombreux ouvrages? On p ourra parexemple consid?erer?2?RDO85?? ou p our ce quiconcerne plusparticuli?erementles corps ?nis? la?biblerouge? ?2?LN86??Les propri?et?es qui suivent sont tr?es classiques et nous ne donnons donc aucune d?emonstration p ources r?esultats? Nous commen?cons par rapp eler les notions de relation d??equivalence? de morphisme et destructure quotient ?I?1?1?? puis les d?e?nitions des structures classiques de group e? d?anneau? d?id?eal et decorps ?I?1?2?? En?n? nousnous int?eressonsplusparticuli?erementaux corps ?nis ?I?1?3? en rapp elantlanotion d?extension p olynomiale et le r?esultat qui fonde la notion de corps de Galois ?th?eor?eme 57?? Nousterminons par le rapp elde la formulationdu th?eor?eme des restes chinois?th?eor?emes 62 et 63?? dont ilest fait un usage imp ortant par la suite?

Rapp elonsaupassagequec?estene?etaumath?ematicienfran?cais

?EvaristeGaloisquel?ondoitle concept g?en?eral de corps ?ni? Poursuivantles travaux des grands alg?ebristesque furent Legendre etGauss? il formula en e?et le th?eor?eme fondamental de la section I?1?3?c?a? Par la suite? Gauss formula les

fondements de ce qui allait devenir la th?eorie de Galois?I?1?1RelationsetfonctionsI?1?1?aRelationsD?e?nition 1?SoientEetFdeux ensembles? unerelation binaireR

deEversFest la donn?ee d?une partieU?E?F? Un ?el?ementx2Eesten relationavecy2Fselon la relationR ? et on notexR ysi ?x? y?2U?LorsqueF?E?R est unerelation sur l?ensembleE?I?1?1?a?aR?e?exivit?e? transitivit?eD?e?nition 2?Une relationR surEestr?e?exivesi et seulement si p our tout ?el?ementx2E? on ax R x?Une relation R surEesttransitivesi et seulement si p our tout triplet ?x? y ? z?2E?E?E? on a?xR yetyR z???xR z??

14CHAPITRE I?1?RAPPELS D?ALG

?EBREI?1?1?a?bRelation d??equivalenceD?e?nition 3?Une relationR surEestsym?etriquesi et seulement si p our tout couple ?x? y?2E?E? on ax R y?yR

x?Unerelation d??equivalenceest une relation r?e?exive? sym?etrique et transitive?I?1?1?a?cRelation d?ordreD?e?nition 4?Une relationR

surEestanti?sym?etriquesi et seulement si p our tout couple ?x? y?2E?E?on a?xR yetyR

x???x?y??Unerelation d?ordreest une relation r?e?exive? anti?sym?etrique et transitive?I?1?1?bLoisdecomp osition internesD?e?nition 5?On app elleloi de composition internedans un ensembleEtoute application deE?EdansE?Dans ce qui suit nous notons?et?des lois de comp osition internes?I?1?1?b?aAsso ciativit?e? commutativit?e? ?el?ement neutreD?e?nition 6?Une loi de comp osition interne?estassociativesi et seulement si p our tout triplet ?x? y ? z?2E?E?E? on a?x?y??z?x??y?z?Une loi de comp osition interne?estcommutativesi et seulement si p our tout couple ?x? y?2E?E? on ax?y?y?xUn ?el?ement 02Eest un?el?ement neutrep our la loi de comp osition interne?si et seulement si p our tout?el?ementx2E? on ax?0 ? 0?x?x?I?1?1?b?bDistributivit?eD?e?nition 7?Une loi de comp osition interne?estdistributive ?a droitepar rapp ort ?a la loi de comp ositioninterne?si et seulement si p our tout triplet ?x? y ? z?2E?E?E? on a?x?y??z? ?x?z???y?z??On d?e?nitsimilairement ladistributivit?e ?agauche?On parle simplement dedistributivit?e lorsqueles deuxpropri?et?es sont v?eri??ees?I?1?1?b?c

?Elements inversibles? involutifs? idemp otentsNous consid?erons d?esormais que la loi de comp osition interne?p oss?ede un ?el?ement neutre not?e 0?D?e?nition 8?Un ?el?ementx2Eestinversible ?a droitesi et seulement si il existey2Etel quex?y? 0?On d?e?nit de m?eme l?inversibilit?e ?a gauche?

Un?el?ementx2Eestinvolutifp ourla loidecomp osition interne?sietseulementsiilestsonpropreinverse :x?x? 0?Un ?el?ementx2Eestidempotentp our la loi de comp osition interne?si et seulement si :x?x?x?

I?1?2?STRUCTURES15I?1?1?cHomomorphisme? isomorphismeD?e?nition 9?SoientEetFdeuxensemblesmunisresp ectivementdesloisdecomp ositioninternes?et?? Une applicationfestunhomomorphismede ?E ??? dans ?F ??? si et seulement si p our tout couple?x? y?2E?E? on af?x?y? ?f?x??f?y??LorsqueF?E? on parle d?endomorphisme?Th?eor?eme 10?Siunhomomorphismede?E ???dans?F ???estbijectif?sar?eciproqueestunhomomor?phisme de?F ???dans?E ???? On parle alors d?isomorphisme? SiF?E? on parle d?automorphisme?I?1?1?dStructurequotientI?1?1?d?aClasses d??equivalenceD?e?nition 11?SoitEunensemblemunid?unerelationd??equivalenceR

?Pourtout?el?ementx2E?onapp elleclasse d??equivalencedexdansEp our la relationR

l?ensemble des ?el?ementsy2Een relation avecx? On la note?x?Th?eor?eme 12?Les classes d??equivalence d?une relationR

forment une partition deE?D?e?nition 13?Onapp elleensemblequotientdeEparR not?eE ?R l?ensemble desclassesd??equivalencede R surE? L?applicationsdeEdansE ?R

qui asso cie la classe d??equivalence d?un ?el?ement ?a celui?ci estapp el?eesurjection canonique? On la notes:E?E ?Rx7??xI?1?1?d?bStructure quotientD?e?nition 14?SoitEunensemblemuni d?uneloidecomp osition interne?etd?unerelationd??equiva?lence

R ?OnditqueR et?sontcompatiblessietseulementsip ourtoutquadruplet?a? b? c? d?2E

4ona?aR

betcR d???a?c?R ?b?d??Th?eor?eme 15?SiR et?sontcompatibles dansE?il existe uneuniqueloi decompositioninterne?surE ? R tel le que la surjection canonique soit un morphisme de?E ???dans?E ?R ???? La structure?E ?R ???est appel?eestructure quotientde?E ???parR

?Th?eor?eme 16?Les propri?et?es de commutativit?e? d?associativit?e? dedistributivit?e? d?existenced?un ?el?ementneutreet d?inversibilit?e se transmettent ?a la structure quotient?I?1?2StructuresI?1?2?aGroup esD?e?nition 17?Un ensembleGmuni d?une loi de comp osition interne?est ungroupesi et seulement si?est asso ciative? p oss?ede un ?el?ement neutre et tout ?el?ement deGest inversible p our??D?e?nition 18?Soit ?G??? un group e? on app ellesous?groupedeGune partie stableHdeGp our la loi decomp osition interne?? telle que ?H ??? soit un group e?I?1?2?a?aSous group e engendr?e par une partieTh?eor?eme 19?Soit?G???un groupe etA?G? Il existe un plus petit sous?groupe deGcontenantA? not?eG?A??C?est laplus petite partie stablecontenanttousles ?el?ementsdeAet leurs inverses? Ondit deG?A?que c?est lesous?group e deGengendr?e parA?D?e?nition 20?On app ellegroupe monog?enetout group e engendr?e par un ?el?ement? etgroupe cycliquetoutgroup e monog?ene ?ni?

16CHAPITRE I?1?RAPPELS D?ALG

?EBREI?1?2?a?bGroup e quotientTh?eor?eme 21?Soita2?G???? l?application? a :G?Gg7?a?g?a ?1est un automorphisme?

D?e?nition 22?Un sous?group eHdeGest ditdistingu?edansGsi et seulement si p our tout ?el?ementa2G?on a?

a ?H? ?H ?Th?eor?eme 23?SoitR

unerelationd??equivalencesurGcompatibleaveclaloidecompositioninterne?alors il existe un unique sous?groupeHdeGtel quex

R y?x ?1?y2H?y?x ?1?Ce sous?groupe est distingu?e dansG? Pour la relation d??equivalenceR

? les ?el?ementsyappartenant ?a la classed??equivalence dexsont donc tous les ?el?ements dex?H? On d?eduit du th?eor?eme 12 que lesx?Hformentune partition deG?Th?eor?eme 24?SoitHunsous?groupedistingu?e dansG? etR

larelation d??equivalencecompatible avec?associ?ee ?aH? Il existe uneuniqueloi de compositioninterne?surG?R

tel le quela surjection canoniquesoit un morphisme de?G???dans?G?R ???? La structure?G?R ???est appel?eegroup e quotientde?G???parHet not?eeG?H

?Th?eor?eme 25?SiGest un groupe commutatif? tout sous?groupeHdeGest distingu?e dansG?I?1?2?a?cGroup es ?nisD?e?nition 26?Soit ?G??? un group e? soienta2GetG?a? le sous?group e engendr?e para? alors siG?a? est?ni? son cardinal est app el?eordre deapour la loi?et not?eord ?a? ? card ?G?a???Remarque?On d?eduit du th?eor?eme 23 que dans le cas d?un group e ?ni on aord?a?jcard?G??o ?ujsignale la ?divisibilit?e? de card ?G? par ord?a??Onsupp osed?e?nisdansla suitel?ensembleNdesentiersnaturels?l?ensembleZdesentiersrelatifseton consid?ere d?esormais l?addition? not?ee ?? comme loi de comp osition interne conf?erant ?aZla structure degroup e commutatif? Les relations d?ordre classiques surZsont not?ees comme de coutume?Th?eor?eme 27?Les sous?groupes additifs deZsont d?e?nis par la donn?ee d?un entier natureln2Net not?es :nZ?fy2Z?9x2Z y?

n Xi?1

xgTh?eor?eme 28?D?apr?eslesth?eor?emes25et24?onpeutd?e?nirpourtoutn2NlegroupequotientZ?nZappel?egroup e des entiers mo dulon?

I?1?2?STRUCTURES17I?1?2?bAnneauxD?e?nition 29?Unanneauestla donn?eed?un ensemble etde deuxlois decomp osition internes?A?????tels que?la structure?A??? soitun group ecommutatif ?parconvention? on note0 son ?el?ement neutreet?xl?inverse d?un ?el?ement par la loi?? ;?la loi de comp osition interne?admette un ?el?ement neutre not?e 1 ;?la loi?soit distributive par rapp ort ?a la loi??On parle d?anneaucommutatiflorsque la seconde loi de comp osition interne?est elle m?eme commutative?Th?eor?eme 30?Dans un anneau? 0 est un?el?ement absorbant? donc qui n?admet pas d?inverse :8a2A? a?0 ? 0?a? 0?On noteA

??Anf0g?D?e?nition 31?Un anneau dans lequel l?implicationab? 0?a? 0 oub? 0est v?eri??ee p our tout couple d??el?ements ?a? b?? est ditint?egre?On p eut d?e?nir par r?ecurrencela multiplication classique surN? Soit?la loi d?e?nie par?:N?N?N?x? y?7?

P xi?1

yet ?etendue ?aZde la mani?ere naturelle? alors ?Z????? est un anneau commutatif int?egre?I?1?2?b?aDivision? pgcdD?e?nition 32?On dit quetest undiviseurdezsi et seulement si il existeqtel quez?q?t? On dit depqu?il est premier s?il n?accepte que 1 et lui m?eme comme diviseur?D?e?nition 33?Une partieId?un anneau ?A????? est unid?ealdeAsi et seulement si :?p our tout couple ?x? y?2I

2on ax???y?2I??p our tout couple ?a? x?2A?Ion ax?a2I?Th?eor?eme 34?Pour toute partieP?A? il existe un plus petit id?ealIdeAcontenantP? C?est par d?e?nitionl?id?eal engendr?e parP?Th?eor?eme 35?Pourtouta2A?aA?fy2a?9x2A? y?a?xgest unid?eal deA? Ondit deaAquec?est unid?eal principaldeA?D?e?nition 36?Soienta1

? ? ? ? ? aN N?el?ements non nuls d?un anneauA? on app elleplus grand commun divi?seur ?pgcd?et on notea1 ? ? ? ? ?aN tout ?el?ement g?en?erateur de l?id?eal engendr?e parfa1 ? ? ? ? ? aN g? Si l?id?ealengendr?e parfa1 ? ? ? ? ? aN gest l?anneauAtout entier? alors lesai sont ditspremiers entre eux?Th?eor?eme 37 Bezout?Soienta1 ? ? ? ? ? aN

N?el?ements non nuls d?un anneauA? alors lesai

sont premiersentre eux si et seulement s?il existeu1 ? ? ? ? ? uN tel queN Xi?1 a i ui ? 1?

18CHAPITRE I?1?RAPPELS D?ALG

?EBRECas de l?anneau des entiers naturels

Th?eor?eme 38?Tout id?eal de?Z?????est principal?Th?eor?eme 39 ?division euclidienne??Pour tout?z ? t?2Z?Z

?? il existe un unique couple?q ? r?2Z?Ntel quez?q?t?ravecr ?jtj?La d?e?nition 36 est bien entendu coh?erenteavec la d?e?nition classique du pgcd? Le th?eor?eme 39 signi?e enparticulier que tout nombre admet une d?ecomp osition unique en facteurs premiers? Si on notea4ble pgcdobtenu de fa?con classique par les d?ecomp ositions en facteurspremiers deaetb? alors l?id?eal engendr?epar?a4b? est e?ectivement le plus p etit id?eal contenant les id?eauxaZetbZ? On a donc biena4b?a?bp ourtout ?a? b?2Z

2?I?1?2?b?bAnneau quotientTh?eor?eme 40?Soit?A?????un anneau etIun id?eal deA? La relationR

d?e?nie parxR not?eA?I

munidesdeux lois quotient a une structure d?anneau? On l?appel leanneau quotientdeAparI?Note 41?L?ensemble quotientZ?nZ

a une structure d?anneau? Celui?ci est int?egre si et seulement si l?entiernest premier?I?1?2?b?cCaract?eristiqueD?e?nition 42?SoitAun anneau? on app ellecaract?eristiqued?un anneau le plus p etit entierntel que8a2A

n Xi?1 a? 0?Si un tel entier n?existe pas? on parle de ?caract?eristique nul le??Note 43?Les anneauxZ?nZ

sont de caract?eristiquen?I?1?2?cCorpsD?e?nition 44?On app ellecorpstout anneau dont tous les ?el?ements non nuls sont inversibles? On app ellecorps premiertout corps n?admettant que lui m?eme comme sous?corps?Th?eor?eme 45?Tout corps est un anneau int?egre? R?eciproquement? tout anneau ?ni int?egre est un corps ?ni?Corollaire 46?Pour tout entier premierp?Z?pZ

est un corps premier?I?1?2?c?aCorps des fractions d?un anneau int?egreTh?eor?eme 47?SoitAunanneauint?egre? soitEl?ensembledescouplesdeA??A

???alors larelationRd?e?nie surEpar?n? d?R ?n 0? d 0??nd 0?n

0d? 0est une relation d??equivalence? Les lois d?e?nies surEparaddition :?n? d? ? ?n

0? d

0???nd

0?n

0d? dd

0??multiplication :?n? d???n

0? d

0???nn

0? dd 0?? sont internes surE? La structure quotient?E ?R

?????est un corps commutatif?D?e?nition 48?Nous app elons corpsQdesfractions rationnel lesl?ensemble obtenu par l?application de laconstruction pr?ec?edente ?a l?anneau int?egreZ?

I?1?3?CORPS FINIS19I?1?3Corps?nisI?1?3?aAnneaudesp olyn?omesNousconsid?eronsdanscequisuitlad?e?nitionclassiquedesp olyn?omes?aunevariabled?e?nissurunanneau commutatifA? D?autre partnous rapp elonsquel?ensemble desp olyn?omes ?a unevariableX? not?eA?X?? muni des lois de comp osition internes a une structure d?anneau? Tout p olyn?omeP2A?X? s?exprimede mani?ere unique dans la base canonique des puissances de la variablesX:P?X? ?

d Xi?0 a i X i?o ?u les co e?cientsai appartiennent ?aA?D?e?nition 49?Le degr?e dePest d?e?ni pardegP? maxfi2N?ai

6? 0g?D?e?nition 50?Un p olyn?ome estmoniquesi et seulement si son co e?cient de plus haut degr?e vaut 1 :P?X? ?

d?1Xi?0 a i X i?X d?I?1?3?a?aIrr?eductibilit?eTh?eor?eme 51 ?division euclidienne??SoientA2A?X?etB2?A?X?? ??ilexisteununiquecoupledepolyn?omes?Q? R?2A?X?

2tels quedegR ?degBetA?B Q?R?D?e?nition 52?Un p olyn?omeP2A?X? estirr?eductiblesurAs?il est de degr?e sup?erieur ?a 1 et que p our toutp olyn?ome de degr?e inf?erieurQ2A?X?? degQ ?degP?PetQsont premiers entre eux?I?1?3?a?bZ?erosD?e?nition 53?On app ellez?eroouracined?un p olyn?omeP?X? tout ?el?ementa2Atel queP?a? ? 0?Th?eor?eme 54?SiP2A?X?admet uneracinea2A? alorsPn?est pas irr?eductible ; il est divisible par lepolyn?ome?X?a??I?1?3?bExtensionp olynomialeNous avons vu par les th?eor?emes 35 et 40 comment ?etendre les anneaux? Nous notonsA?X??P?X?

l?anneauquotient obtenu ?a partir de l?anneau des p olyn?omesA?X? d?e?ni sur l?anneauAet d?un p olyn?omeP?X? priscomme ?el?ement g?en?erateurde l?id?eal principalP?X?A?X?? Dans l?anneauZ?nZ

nous parlions d?op?erationsmo dulon?mutatis mutandisnous parlerons ici d?op?erations mo dulo le p olyn?omeP?X??I?1?3?cCorpsdeGaloisTh?eor?eme 55?Soitpunentierpremier?notonsGF?p?lecorpspremierZ?pZ

?SoitP?X?unpolyn?omeirr?eductible surGF?p?? l?anneauGF?p??X??P?X? a une structure de corps de cardinalit?ep

degP? SoitQ?X?un polyn?ome irr?eductible surGF?p?distinct deP?X?mais de m?eme degr?e? alors le corpsGF?p??X??Q?X?estisomorpheaupr?ec?edent?Pourtoutentiermettoutentierpremierp?ilexisteaumoinsunpolyn?omeirr?eductible deGF?p??X?de degr?em?Th?eor?eme 56?SiKestuncorps?nidecardinaln?alorsilexisteunpremierpetunentiermtelquen?p

m? et il existe un isomorphisme entreKetGF?p m??Tous ces corps ?etant isomorphes? on app ellecorps de Galois de cardinalit?ep m? not?eGF?p m?? un corps ?nide cardinalit?ep mobtenu par la construction pr?ec?edente?

20CHAPITRE I?1?RAPPELS D?ALG

?EBREI?1?3?c?aTh?eor?eme de GaloisTh?eor?eme 57?SiP?X?est un polyn?ome irr?eductible ?a coe?cients dansGF?p?de degr?em? alorsPa uneracine?dansGF?p

m??Corollaire 58?La famil le??? ?

2? ? ? ? ? ?

m?1?est une base que l?on ditasso ci?ee?aP?Corollaire 59?Le polyn?omeP?X?amracines distinctes dansGF?p

m?qui sont??? ? p? ? p

2? ? ? ? ? ?

p m?1??I?1?3?c?bBases normalesCorollaire 60?Danstoutcorps?niKdecardinalp m?ilexisteaumoinsun?el?ement?2K?telquelafamil le?? ? ? p? ? p

2? ? ? ? ? ?

p m?1?soit une base deK:8x2Kx? m?1Xi?0 i p i?avec les?i ?el?ements deZ?pZ

? Une tel le famil le est appel?eebase normaledeK?Th?eor?eme 61?Danstouteextensionpolynomialesuruncorps?niKdecardinalit?eq?ilexisteunebasenormale?? ? ?

q? ? q

2? ? ? ? ? ?

q

m?1??I?1?3?c?cTh?eor?emes des restes chinoisTh?eor?eme 62?Soientmetndeuxentiersnaturelspremiersentreeux?alorsZ??mn?Z

estisomorphe?aZ?mZ ?Z?nZ ? Plus pr?ecis?ement? l?application?:Z?mnZ ?Z?mZ ?Z?nZx7??xmo dm? xmo dn?est un isomorphisme et sa r?eciproque est? ?1?xm ? xn ? ?xm n?n ?1mo dm? ?xn m?m

?1mo dn? mo dmn?Th?eor?eme 63?SoientPetQdeuxpolyn?omes surGF?q?premiers entre eux? alorsGF?q??X??P Q?X?

estisomorphe ?aGF?q??X??P?X? ?GF?q??X??Q?X? ? Plus pr?ecis?ement? l?application?:GF?q??X??P Q?X? ?GF?q??X??P?X? ?GF?q??X??Q?X??7??? mo dP ?? mo dQ?est un isomorphisme et sa r?eciproque est? ?1?? P ??Q ? ? ?P Q?Q ?1mo dP? ? ?Q P?P ?1mo dQ? mo dP Q?

ChapitreI?2LibrairiedeprogrammationZen?Nemeditespasqueceprobl?emeestdif??cile?S?iln??etaitpasdi?cile?ceneseraitpas un probl?eme?Mar?echal Fo ch

Nous pr?esentonsmaintenantlalibrairiede programmationZen? Ils?agit d?untravail?en communavecReynaldLercierduLab oratoired?Informatiquedel?EcolePolytechnique?quiap ourob jectifdefournirunoutilsimple??? de programmationen langageCp ourlecalculdanslescorps?niset plusg?en?eralement dans toute extension ?nie d?e?niesur un anneau d?entiers? Comme souvent en pareilcas?la recherche de la simplicit?ep eut entra??ner des p ertes d?e?cacit?e et obtenir un outil ?a la fois simple ete?cace nous a conduit au niveau de la programmation interne ?a un ?edi?ce relativement complexe? Ainsi?lalibrairieZencompteactuellementplusde 65000lignesde co de ? Ce chapitrene constituepasunedo cumentation de r?ef?erence de la librairi e? mais plutot une tentative d?explication des concepts utilis?es?LalibrairieZenestunoutildeprogrammationetnonunoutildecalculformel?Pourr?esoudreunprobl?emesimple?ilserasouventplusrapidedesecontenterd?unp etitprogrammeenMapleouenAxiom?Parcontre?sileprobl?emes?av?ereengendrerdescalculse?ectifsintensifs?lalibrairieZenp ermettra d?obtenirune am?eliorationtr?es sensiblede la rapidit?edes calculs?Ceci se fera au prix d?untravail de programmation relativement simple? c?est du moins le but recherch?e? de sorte que la transitiondepuis un programme Maple ou Axiom devrait ?etre ais?ee d?es lors que la programmation enCest ?a p eupr?es ma??tris?ee?Nouscommen?conspare?ectuerun ?etatdel?artducalculinformatiquedanslescorps?nisavantderapp elerbri?evementl?historiquedelalibrairie ?I?2?1?? Nouspr?esentonsensuitel?environnementdeprogrammation utilis?e qui p ermet une p ortabilit?e facilit?ee ?I?2?2?? La section I?2?3 pr?esente les princip esdebasedelalibrairie??asavoirlestyp esd?e?nis?larepr?esentationdesanneauxpremiers?leprincip eg?en?eral de la syntaxe des op?erations deZen? la d?e?nition d?une extension p olynomial e? et les di??erentesarithm?etiquesdisp onibles ?Le probl?emede l?optimisationdes calculsest ensuiteab ord?e?avec lesdi??e?rentes options p ossibles pr?evues ?I?2?4? : d?une part les pr?ecalculs? qui ne mo di?ent pas la repr?esentationinternedes?el?ements?p euventdonc?etree?etu?es?atoutmoment?etquiam?eliorentg?en?eralementlesp erformances d?une op?eration arithm?etique particuli?ere ; d?autre part les clones? qui utilisent une repr?e?sentation di??erente de la repr?esentationstandard? en vue d?acc?el?erer les op?erations arithm?etiquesdansleur ensemble? Nous terminons en ?evo quant la gestion des erreurs de la librairiequi s?av?ere imp ortantelors du d?everminage d?un programme ?I?2?5??I?2?1Intro ductionI?2?1?a

?Etatdel?artLa question que l?on est en droit de se p oser est alors celle du bien?fond?e de cet investissement? En e?et?

la r?ealisation d?un tel outil ne s?imp ose que s?il n?existe pas par ailleurs? Or qu?en est?il :1?Ilexistedesoutilsdecalculformel?Maple?3?CGG

?90??Mathematica?3?AB92????? dontlesp erfor?mances sont tr?esmoyennes au niveau del?e?cacit?e decalculs surles grandsentiers?Cesoutils sont

22CHAPITRE I?2?LIBRAIRIE DE PROGRAMMATIONZENene?etoptimis?es p ourlecalculformel? etil nefautpasleurdemanderplus? Typiquement? l?appli?cation ?a la cryptographie exigede p ouvoir manipuler desnombres de 150 chi?resd?ecimaux? De telsnombres sous Maple? par exemple? conduisent?a descalculs lents? Leschosesseg?atent encoresi l?onsouhaite travailler dans des extensions? Maple sait travailler sur des extensionsde niveau 1 ?du typ eZ?pZ

?X??P?X?

??Avecun p eud?habilet?e? au prixd?un v?eritable travail deprogrammation? onp eutarriver ?atravailler surdesextensionsdeniveau 2 ?dutyp e?Z?pZ

?X??P?X? ??Y??Q?Y?

?? M?eme ?aceniveau? les p erformances sont lamentables ; on p ourra en juger sur le p etit exemple de l?annexe A? Or

nous souhaitions p ouvoir travailler facilement sur des extensions de niveau 3 et plus? ce que Maple nesait pas faire?2?Unautreoutilconsid?erable??asavoirlalibrairiedecalculsPari?1?Par??sembleassezcurieusementignorer le monde des corps ?nis? Les extensions p olynomiales en particulier ne sont accessibles que de

fa?con d?etourn?ee?3?A l?interface entre calcul formel et calcul e?ectif? Axiom ?1?NAG? p ermet de travailler dans les exten?sions? mais de mani?ere p eu e?cace?4?Pour la programmation en langageC? la librairieBigMod?1?MorBM?? d?evelopp?ee par Fran?cois Morainp our l?implantation de sescerti?catsde primalit?e par la m?etho de descourb eselliptiques? p ermet detravailler mo dulo un nombre entier ?1?MorEC???

A la base? elle utilise la librairieBigNum?7?SVH89? d?evelopp?ee conjointement par l?INRIA et DigitalPRL qui p ermet de manipuler de grands entiers? Cette derni?ere pr?esentel?avantage de p oss?eder p ourun grand nombre d?architectures un noyau de fonctions ?ecrit en assembleur? ce qui acc?el?ere grandementles calculs ?de 30 ?a 50 ? selon les calculs e?ectu?es et le typ e d?op?erations utilis?ees?? Malheureusement?force est de constater que les fonctions deBigNumsont tr?es p eu simples d?emploi? En outre? certainesd?entreellesp euvententra??nerdeserreursdecalculsiellessontmal employ?ees? Ene?et?parsoucid?e?cacit?e? aucun test n?est e?ectu?e p our d?etecter d??eventuelles erreurs?CecifaitdeBigModunoutile?cacemais pr?esentantlesm?emesd?efautsqueBigNum?Enoutre?BigModnep ermetpasdetravailler surplusieursanneaux?alafoispuisquelemo duleestd?eclar?eglobalement? De plus? la syntaxe des fonctionsBigModest parfois source de confusions?Reconnaissons n?eanmoins queBigModa ?et?e souvent une source d?inspiration p our la programmationdeZen? et ce m?eme si aucune fonction deBigModn?a ?et?e reprise telle quelle?5?En?n? Lidia ?1?LiD95? estuneautrelibrairie decalcul qui p ermetdes op?erationse?caces?mais uni?quement dans les corps ?nis premiers?La r?ealisation d?un outil tel que nous le concevionss?est donc av?er?een?ecessairep our les probl?emes quinous int?eressaient ?voir partie I I? et nous p ensons que cet outil p ourra s?av?erer utile ?a d?autres?I?2?1?bHistoriqueLa librairieZentire en fait ses racines d?un lointain pass?e ? En e?et? la programmation de l?algorithme deLeon ?4?Leo88? p our la cryptanalyse du syst?eme de McEliece ?7?McE78? ?voir chapitre I I?2? avait conduit ?al??elab oration de fonctions matricielles e?caces dansGF?2?? Par la suite? l??etude de l?algorithme de Sidel?ni?kov?Shestakov ?4?SS92? a fourni l?o ccasion ded?evelopp er desoutils similaires dansGF?2

m?? Ces premi?eresimplantations utilisaient le format et certaines fonctions de la librairieBigNum?7?SVH89??Parallelement? Reynald Lerciers?appuyant surBigMod?1?MorBM?? d?eveloppait ses outils dansGF?p?p our factoriser de grands entiers par la m?etho de des courb es elliptiques?Or tous ces algorithmes fonctionnent ?egalement dans tout corps ?ni? Le b esoin s?est donc fait sentir d?un?echanged?outils? Mais? nosprogrammes ?a tousdeuxdevaientdetoutemani?ere ?etrer?e??ecritspuisquenosoutils resp ectifs ?etaient di??erents?Nos implantations utilisant ?a la base la m?eme librairieBigNum? elles pr?esentaient en outre des similitudesde conception? C?est alors qu?a germ?e l?id?ee d?une librairie qui p ermettrait de programmer une fois p our toutesnos algorithmes? Le but ?etait donc d?obtenir un outil qui autorise l?utilisation d?un algorithme dans tout corps?ni? quelle que soit la construction de celui?ci? sans changer une ligne du programme de calcul?

I?2?2?COMPILATION ET ENVIRONNEMENT DE PROGRAMMATION23Nousavionstouslesoutilsdansunformat?ap eupr?escompatible?op?erationssurles?el?ements?lesp olyn?omes et les matrices dansGF?2? etGF?p??? restait ?a assembler les morceaux???I?2?2CompilationetenvironnementdeprogrammationI

d

?ealement?uneprogrammationrigoureuseenCdoit p ermettrela p ortabilit?e surtoute machinep oss?edant un compilateur de ce langage? Malheureusement? l?exp?erience prouve qu?il n?en est rien ? Ouplus exactement? une programmation recherchant l?e?cacit?e risque assez facilement de transgresser ces r?egles?Il est donc absolument indisp ensable de fournir avec la librairie un programme de test qui p ermet? lors dela compilation sur une machine d?un nouveau typ e? de v?eri?er que des e?ets de b ord n?apparaissent pas?Cetterecherched?e?cacit?eimp oseenoutred?utilisersurchaquemachinelecompilateur leplusp er?formant? C?est g?en?eralement le compilateur du constructeurp our une raison que nous verrons dans la sec?tion I?2?3? Or chaque compilateur a desoptions de compilation qui lui sont propres? Il fallait donc trouverun moyen d?obtenir automatiquement les param?etres de compilation ?a utiliser? ou en tout cas que cela soittransparent p our l?utilisateur?D?autre part? la librairieZencompte plus de 200 ?chiers ?a compiler?

?Ecrire p our chacun d?entre eux lap ortionde?chierMake?lecorresp ondanteseseraitav?er?etr?esfastidieuxetsourced?erreursnouvelles?L?aencore un outil automatique ?etait ?a trouver?Comme cegenredeprobl?eme estcommun ?a tout travail de programmation un p eu cons?equent?unteloutil existed?ej?a?Imake?3?DuB93? a ?et?ed?evelopp?eparlesprogrammeurs duserveurXetp ermetpardes?chiers de con?gurer chaque architecture p our autoriser la g?en?eration automatique des ?chiersMake?le? Onutilise ainsi des ?chiersimake?lequi sont b eaucoup plus faciles ?a g?erer? En outre?comme le serveurX estg?en?eralement disp onible sur toute machine Unix? ce programme l?est aussi? Nous avons ainsi pu v?eri?er quenotre librairie se compilait sur des architectures largement di??erentes ?voir ?gure 2?2?? par la m?eme s?equencede commandes ?voir ?gure 2?1?? et que les tests ?etaient correctement e?ectu?es?Dans un tout autre registre? il faut rapp eler qu?une librairie n?est utilisable par d?autres utilisateurs que

ses programmeurs que si elle disp ose d?une do cumentation satisfaisante? Or? conserver une do cumentation ?ajour dans un outil enpleine ?evolution estune t?achedi?cile? Pour tenterdela faciliter? nous avons utilis?euneid?eedeKnuth ?1?KL?a?nquelessourcesdesprogrammes ?enC?etceuxdelado cumentation?enL

ATE

X?3?Lam94?? soient tous dans des ?chiers identiques? Nous n?avons pas repris tel quel le format prop os?eparKnuth?carilconduit?ades?chiersdi?cilementlisibles?Ene?et?auformatCweb?lesdi??erentespartiesdusourceCp euvent?etrep ermut?eesdansle?chiersourceetlacompilationn?ecessitedoncune?etap ede?ltragesuppl?ementaire?C?estp ourquoi?toutengardantcetteid?eedesto ckerlesdeuxtyp esdesourcesdanslesm?emes?chiers?nousavonspr?ef?er?e?ecrirenotrepropreprogramme? Celui?cir?ecup?erelesp ortionssuccessivesdedo cumentationauseindescommentairesdes?chierssourcesCdelalibrairieetg?en?ere automatiquement un index facilitant l?acc?es rapide aux informations r?eparties dans les quelques 500pages de la do cumentation? Il est aussi p ossible d?inclure des p ortions de sourceCdans les ?chiersL

ATE

X?Ce concept p ermet ainsi lors de la mo di?cation de la programmation de mo di?er aussit?ot la do cumentationcorresp ondante?I?2?3Princip esretenusP

ourpermettre de conserver?a la fois la simplicit?e de programmation et l?e?cacit?e? il nous est tr?esvite apparu qu?un conceptde styleorient?e?ob jet ?etait n?ecessaire?Ene?et? unordinateur ne calculepas e?cacement de la m?eme mani?ere dans les corps de caract?eristique 2 et dans ceux de caract?eristiquep?Tout le probl?eme ?etait donc d?arriver ?a cacher cette di??erence p our l?utilisateur?Ce dernier travaille dans un anneau?

?A chaque typ e d?anneau est asso ci?ee une famille d?algorithmes quip ermettent de calculer e?cacement dans cet anneau? Nous avons donc d?ecid?e que p our notre programmation?unanneauseraitunestructurecontenantoutrelesparam?etresdeconstructiondel?anneau?unelistedep ointeursde fonctions? Lors dela constructiond?un anneau? cesp ointeurssont initialis?es selon le typ edel?anneau? Chaque fonction de calcul fait intervenir l?anneau dans lequel on travaille? et c?est donc le p ointeurde fonction qui est utilis?e p our le calcul? Chaque op?eration ne fait donc intervenir qu?une d?er?ef?erenciation

24CHAPITRE I?2?LIBRAIRIE DE PROGRAMMATIONZEN

S ?equencedes op ?erationsCommande

Con?guration des param?etres lo caux

?Edition desp ecif?defimake ?Icon?g

Fabrication du ?chier g?en?eral

make Make?le

Fabrication des sous??chiersmake Make?les

Compilation de la librairie

make

E?acement des ?chiers interm?ediairesmake clean

E?acement de tous les ?chiers compil?esmake tidy

Fig?2?1 ?Compilation deZen?

MachineSyst?eme d?exploitationCompilateurs utilis?es

Sun4SunOScc? gcc

SolarisSUNWspro?cc? gcc

DECUltrixgcc

VAX

AlphaOSFcc? gcc

HPHP?UXcc? gcc

PCnetbsdgcc

linux OS2

Fig?2?2 ?Portabilit?e deZen?

I?2?3?PRINCIPES RETENUS25

Typ eCOb jet math?ematique

ZENRingUn anneau? c?est??a?dire la donn?ee des op?erations ?el?ementaires sur les ?el?ements decetanneau? Tout programme doit commencer par la constructiondesdi??erentsZENRings qui vont ?etre utilis?es?

ZENEltUn ?el?ementd?un anneau?Selonletyp edel?anneau? unZENEltp ourra?etreun?el?ement def0?1gou un p olyn?ome de p olyn?omes surZ?251Z

? mais dans tous lescas il sera de typ eZENEltet manipulable avec la m?eme syntaxe de fonctions?

ZENPolyUn p olyn?ome deZENElts? Comme le typ e ci?dessus?ce typ e estmanipulable dela m?eme mani?ere dans tout anneauZENRing? La seule contrainte est que le degr?emaximal du p olyn?ome est exig?e lors de la cr?eation d?unZENPoly? Les op?erationse?ectu?ees ne doivent donc pas conduire ?a l?obtention d?un degr?e sup?erieur?

ZENMatUnematricedeZENElts?Commeils?agitd?unob jet?adeuxdimensions?lastructurededonn?eesutilis?eeconsisteenunedoubler?ef?erencesuruntableaudeZENElts?Cettedoubler?ef?erencep eutdoncprivil?egier soitleslignes? soitlescolonnes de la matrice? Dans le cas binaire? et selon les op?erations? il p eut ?etre tr?esavantageux d?utiliser une structureplut?ot que l?autre? mais bien entendu? quellequesoitcechoix?ler?esultatobtenuseralem?eme? Cettedoublestructureserapr?ecis?ee au chapitre I?5?

Fig?2?3 ?Types deZensuppl?ementaire ?a chaque app el de fonction? Ceci ?evite le recoursaux testsqui sont tr?es p?enalisant d?es lorsqu?une pro c?edure est app el?ee de l?int?erieur d?une b oucle?En terminologie orient?e?ob jet? on p eut voir cette appro che comme la r?ealisation de classes d?anneaux danslesquelles les op?erations sur les ?el?ements?ob jets sont d?e?nies de mani?ere propre? Mais alors? p ourquoi ne pasavoir utilis?e un langage comme leC?? ? La r?ep onse est simple : parce que nous souhaitions programmer lalibrairie enC? Cep endant? cette a?rmation p?eremptoire n?est pas aussi sectaire qu?elle en a l?air? En e?et lescompilateurs du langageC?? ont fait de tr?es gros progr?es ces derni?eres ann?ees? Mais ils restent n?eanmoinsun p eu en de?ca de leurs concurrents enC? Cela tient au fait que les noyaux Unix sont programm?es en langageC? et chaque constructeurdoit donc optimiser son compilateurCp our que sa machine soit la plus rapide?De ce fait? les compilateursCdes constructeurs utilisent au maximum les resources de la machine? alors queles compilateursC?? ne p euvent qu?appliquer des m?etho des d?optimisation plus g?en?erales? On p eut noterd?ailleurs que les programmeurs de la librairie lidia ?1?LiD95?? ?ecrite enC??? sont actuellement en train dereprogrammer plusieurs de leurs mo dules enCpar souci d?e?cacit?e?Nousallonsmaintenantd?ecrirepluspr?ecis?ementlalibrairie?NousutiliseronsceStyle d?

?Ecriturep ourindiquer toute fonction ou variable d?e?nie dansZen?I?2?3?aTyp esLalibrairieZend?e?nituncertainnombredenouveauxtyp es?Lesprincipauxsont?enum?er?esdansletableau de la ?gure 2?3?I?2?3?bAnneauxpremiersComme nous travaillons dans les anneaux ?nis? il nous faut commencer par fabriquer un anneau mo dulaire

Z?nZ

? Dans un programme enC? on commence donc par d?eclarer une variable d?anneauZENRing R? Il fautensuite initialiser cette variable en utilisant une repr?esentation de l?entiern? Puisque nous avons bas?eZensurBigNumc?est donc ?a l?aide d?une repr?esentationde ce typ e que nous d?e?nissonsn? Rapp elons bri?evementqu?unentiernp euts??ecriredefa?conuniquedansunebase2

s?aire?DansBigNum?unentierestdoncrepr?esent?e par un couple?n?nl?de deux variables de typ e?BigNumDigit ??int?? La valeur denest alors:n?

nl?1Xi?0 n?i??2 s? i?

26CHAPITRE I?2?LIBRAIRIE DE PROGRAMMATIONZEN

S ?equencedes op ?erationsExemplede fonctionutilisable

Initialisation d?un mo dule

BigNum n? int nl?ZBNReadFromString??n??nl?

quotesdbs_dbs22.pdfusesText_28

[PDF] Score ASIA

[PDF] Un algorithme de simulation pour résoudre un problème de probabilité

[PDF] Algorithme PanaMaths

[PDF] Algorithmique en classe de première avec AlgoBox - Xm1 Math

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne

[PDF] Rappels sur les suites - Algorithme - Lycée d Adultes

[PDF] Les tableaux - Luc Brun

[PDF] Les tableaux 1 Exercice 1 - Lipn

[PDF] Terminale S Exercices sur les suites Exercice 1 On consid`ere la

[PDF] Cours d algorithmique BTS SIO première année - Bienvenue sur le

[PDF] Algorithmique et programmation, un levier pour développer des

[PDF] Algorithmique et Structures de Données

[PDF] ORME 212 : Algorithmique en seconde avec Python

[PDF] Ali baba et les quarante voleurs - Gomme Gribouillages

[PDF] Commentaire de l 'article 26 du code de droit international privé