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

Description

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

Sujets

• Symbole de Legendre
• Entier relatif
• Algorithme d'Euclide étendu

Informations

• Publié par: pefav
• Nombre de lectures: 78
• Langue: Français

Extrait

NOM : PRENOM :

Date : Groupe :

Mathe´matiquespourlaBiologie:Feuille-r´eponsesduTD7 Equationsdiff´erentielles:m´ethoded’Euleretcomple´ments

. .

Exercice 1.:nOel’´evolmod`elispopataluoituledninledeesndiobaestnqitaale´na’lcorlauepa dynamique suivante : y 0 y= 0,08y(1−). 400000 1.Dequeltypedemod`eles’agit-il?Querepr´esententlesconstantes0,08 et 400000?

2.Al’issued’unelonguepe´riodedesurexploitation,onestimequel’effectifdecettepopulationde baleineesttombe´a`70000.Ensupposantqu’oninterditalorssonexploitation,calculer,aumoyende lam´ethoded’Euler,uneapproximationdesone´volutiony 0 ,y 1 ,y 2 , ....en prenant un pas de temps 0 h’Eederulurpo´el’tauqnoi=1.Onrappleeluqlemae´htdoy=f(yti:e’´sr)c  t n =t n−1 +h (1) y n =y n−1 +hf(y n−1 ). Indiquervotrere´ponsepuispre´sentersuccintementlescalculsquivousyontconduit: y 0 = 70000, y 1 =y.......... , 2 =...............

3. Quepouvez-vous dire de lim n→∞ y n ?

1