Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmique On note ZN l'anneau quotient Z N ·Z Z N le groupe multiplicatif de cardinal N et len x la

4 pages
TD 7 Algorithmique On note ZN l'anneau quotient Z/N ·Z, Z?N le groupe multiplicatif de cardinal ?(N) et len(x) la longueur en bits d'un entier x. Exercice 1: Exponentiation 1. On suppose que l'on a ?1, . . . , ?k ? ZN , avec des entiers positifs e1, . . . , ek, ou len(ei) ≤ pour i = 1, . . . , k. Montrer comment calculer ? = ?e11 · · ·? ek k en utilisant + O(1) elevations au carre dans ZN et + 2k + O(1) multiplications dans ZN . 2. Montrer comment calculer ?e, ou ? ? ZN pour un exposant e de bits. Montrer que pour tout parametre entier positif k, on peut utiliser un precalcul qui utilise + O(1) elevations au carre dans ZN et 2k?1+O(1) multiplications dans ZN et ensuite on peut calculer ?e pour tout exposant e de bits en utilisant seulement +O(1) elevations au carre et 2k?1+/k+O(1) multiplications. 3. Que peut-on faire si ? est fixe ? Exercice 2: Tests de Primalite Un nombre de Carmichael est un nombre compose tel que pour tout a ? Z?n: a n?1 = 1 mod n.

  • groupe multiplicatif de cardinal ?

  • parametre entier positif

  • meme algorithme

  • demonstration du theoreme d'euler

  • ty mod

  • theoreme des restes

  • cardinal de z

  • symbole de legendre

  • entier

  • algorithme d'euclide etendu


Voir plus Voir moins
NOM : PRENOM :
Date : Groupe :
Mathe´matiquespourlaBiologie:Feuille-r´eponsesduTD7 Equationsdi´erentielles:m´ethodedEuleretcomple´ments
. .
Exercice 1.:nOel´evolmod`elispopataluoituledninledeesndiobaestnqitaale´nalcorlauepa dynamique suivante : y 0 y= 0,08y(1). 400000 1.Dequeltypedemod`elesagit-il?Querepr´esententlesconstantes0,08 et 400000?
2.Alissuedunelonguepe´riodedesurexploitation,onestimequeleectifdecettepopulationde baleineesttombe´a`70000.Ensupposantquoninterditalorssonexploitation,calculer,aumoyende lam´ethodedEuler,uneapproximationdesone´volutiony0,y1,y2, ....en prenant un pas de temps 0 hEederulurpo´eltauqnoi=1.Onrappleeluqlemae´htdoy=f(yti:e´sr)c tn=tn1+h (1) yn=yn1+hf(yn1). Indiquervotrere´ponsepuispre´sentersuccintementlescalculsquivousyontconduit: y0= 70000, y1=y.......... ,2=...............
3. Quepouvez-vous dire de limn→∞yn?
1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin