Agregext composition de mathematiques generales 2007 maths

Description

6Les quatre premieres parties du probleme sont largement independantes.Partie IDans cette partie I, on etudie une methode de calcul de l’inverse d’un element a d’un groupemultiplicatif G de cardinal ni N ∈N . L’element neutre de G est note 1.«Ecrire un algorithme» signi e le rediger en fran cais, sous une forme rappelant un programmed’un langage tel que Pascal, Maple, Matlab, etc.Le coutˆ d’un algorithme est le nombre de multiplications dans le groupe G que necessite sonexecution. On ne tiendra pas compte des autres operations (en particulier celles dansN).N 11. Justi er le fait que a est inverse de a dans G.2. On ecrit la decomposition en base 2 de N 1 sous la forme :kXiN 1 = x 2 avec k ∈N, x ∈{0,1} pour i∈ [[0,k] et x = 0.i i ki=0On considere les suites nies ( a ) et (b ) de nies par :i 06i6k+1 i 06i6k+1x 2ia = 1, b =a et pour i∈ [[0,k]], a =a b , b =b .0 0 i+1 i i+1i ia) Demontrer que a est l’inverse de a dans G.k+11b) En deduire un algorithme de calcul de a et preciser, en fonction de k, son coutˆdans le pire des cas (c’est- a-dire le nombre maximum de multiplications dans G que1necessite le calcul de a ; on ne tiendra pas compte du coutˆ eventuel du calcul desx , 06i6k). L’algorithme doit prendre comme arguments a et N.i3. Exemple. Dans cette question, G est le groupe des elements inversibles deZ/148Z.On note encore a la classe dansZ/148Z d’un element a deZ.a) Determiner le cardinal N de G.b) Demontrer que 5 ...

Informations

• Publié par: mu
• Nombre de lectures: 186
• Langue: Français

Extrait

Lesquatrepremi`erespartiesduprobl`emesontlargementinde´pendantes. Partie I DanscettepartieI,one´tudieunem´ethodedecalculdel’inversed’un´ele´mentad’un groupe ∗ multiplicatif G de cardinal finiN∈NeGtseredentuemtn’´.L´eelenot´1. ´ «Ecrire un algorithme»mrofparealepnutnn¸raiscaou,snesuprogrammengisnfregedi´eerelifi d’un langage tel que Pascal, Maple, Matlab, etc. Lecouˆtd’unalgorithmeestlenombredemultiplicationsdanslegroupeGitssonesenquce´e exe´cution.Onnetiendrapascomptedesautresope´rations(enparticuliercellesdansN). N−1 1. Justifierle fait queaest inverse deadansG. 2.One´critlade´compositionenbase2deN−1 sous la forme : k X i N−1 =x i 2 aveck∈N,x i ∈ {0,1}pouri∈[0, k]etx k 6= 0. i=0 Onconside`relessuitesfinies(a i ) 06i6k+1 et (b i ) 06i6k+1 ´dr:paesniefi x i 2 ],a= ,b 0 =aet pouri∈[0, k i+1 a i b i b a 0 = 1,b i+1 = i . a)D´emontrerquea k+1 est l’inverse deadansG. −1 b)Ende´duireunalgorithmedecalculdeaeptsire´rcenf,ectonndioekocnotuˆ,s danslepiredescas(c’est-`a-direlenombremaximumdemultiplicationsdansGque −1 n´ecessitelecalculdeandraetie;onndlseucldcualve´euentcudetuˆocsaptpmo x i , 06i6k). L’algorithme doit prendre comme argumentsaetN. 3.Exemple.Dans cette question,Gsinvmentel´edes´edlbsereisrgelepuotseZ/148Z. On note encoreala classe dansZ/148Z’dnue´´lmenetadeZ. a)D´eterminerlecardinalNdeG. b)De´montrerque5estune´le´mentdeGetermtd´esoniinerapesrevnhte´malreedod la question I.2. c)Donneruneautreme´thodepourd´eterminercetinverse. Partie II e 1. a)Soitπitlumepuorgnu’dteneml´´eunatifplicG,eun entier relatif etα=π. 2k k Onconside`rel’applicationfdeZ×GdansGrde´nfieiapf(k, τ) = (τ απ ,). α α 2 Exhiber une fonctionϕdeGdansGe,peneen´duqdeadtnev´erettifian e τ=ϕ◦f(k, τ) pour tout (k, τ)∈Z×G. e α b) Onsuppose le groupeGetneme´le´’ltπconnus de tous les membres d’une association. e L’un d’eux,A, garde secret l’entiereteerlbcidnupl´eml’´eentα=π, ainsi donc que la fonctionfdnucvne’reyoa`heecnr.Ocrehnupeor´cderuepermettant`achaAun α messagecrypte´souslaformed’un(oudeplusieurs)e´l´ement(s)τdeG, telle que la seule connaissance deetial.ssageinirevuemelra`eorteffissu Justifierlefaitque,sil’auteurde´composesonmessageenpartiestellesquechacune puisseˆetrerepre´sent´eeparun´el´ementτdu groupe, choisit pour chacune d’elles un i entierket envoie les couplesf(k ,τ) = (µλ ,a)`A, alors ce dernier peut les i αi ii i d´ecryptergraˆcea`ϕ. e 2