La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Publications similaires

gogus kremi faydalari

de gogusdiklestiri2

zayiflama cayi kullanimi

de bitkiselcayi8

gogus kremi faydalari

de gogusdiklestiri2

Licence STS Mention MATH L3 - ATN Arithm´etique
1 Entiersrationnels L’anneauZdes entiers est connu : sage: ZZ Integer Ring sage: ZZ == IntegerRing() True sage: -5 in ZZ True sage: x = 10^33 sage: b =1479 sage: c = x.digits(b) sage: c [1081, 720, 612, 227, 1085, 1257, 645, 1120, 832, 1430, 19] sage: add(c[k]*b^k for k in range(len(c))) == x True la division euclidienne, les pgcd et ppcm et la formule de Bezout s’obtiennent comme suit : sage: a,b = 62735572, 49362 sage: a,b (62735572, 49362) sage: r = a.mod(b) sage: r 45832 sage: q,r = a.quo_rem(b) sage: q,r (1270, 45832) sage: a == b*q+r True sage: gcd(a,b) 2 sage: lcm(a,b) 1548376652532 sage: d,u,v = xgcd(a,b) sage: d,u,v (2, 5957, -7570921) sage: d == a*u + v*b True Onpeutobteniraussilesdiviseursdunentier,lesentierspremiers`aunentierdonne´setla fonctionϕd’Euler : sage: b.divisors() [1, 2, 3, 6, 19, 38, 57, 114, 433, 866, 1299, 2598, 8227, 16454, 24681, 49362] sage: lc = 250.coprime_integers(250) sage: len(lc) == euler_phi(250)
1
Letestdeprimalite´,etlafactorisationdunentier:lesdiviseurspremiersetlafactorisation d’un entier sont fournis par :
sage: Primes() Set of all prime numbers: 2, 3, 5, 7, ... sage: p = 102639592829741105772054196573991675900716567808038066 803341933521790711307779 sage: p 102639592829741105772054196573991675900716567808038066803341933521790711307779 sage: p.is_prime() True sage: lp = [p for p in range(2,100) if ZZ(p).is_prime()] sage: len(lp) == prime_pi(100) True sage: next_prime(10^5) 100003 sage: fb = factor(b) sage: fb 2 * 3 * 19 * 433 sage: list(fb) [(2, 1), (3, 1), (19, 1), (433, 1)] sage: b == expand(fb) True
Le corpsQrptseslene´d-e´i:dmbreesnoionnsrat
sage: QQ Rational Field sage: QQ == RationalField() True sage: QQ == FractionField(ZZ) True sage: r = 6/4 sage: r,r.numerator(),r.denominator() (3/2, 3, 2) sage: r in QQ True
2Entiersmodulaires Les anneauxZ/Znnsiadsntpr´ed´esonsage: sage: R = IntegerModRing(23) sage: R Ring of integers modulo 23 sage: R.characteristic() 23 sage: R.order() 23 sage: R.is_field() True
2
Onpeutde´terminerdesg´en´erateursdugroupedese´le´mentsinversibles:
sage: R.multiplicative_generator() 5 sage: R.unit_gens() [5] sage: S = IntegerModRing(21) sage: S Ring of integers modulo 21 sage: S.is_integral_domain() False sage: S.multiplicative_generator() Traceback (most recent call last): ... ValueError: multiplicative group of this ring is not cyclic sage: S.unit_gens() [8, 10]
SoitR=Z/Zn; la classekmodulond’un entier rationnelkest obtenue ensagepar la coercitionR(k)ou par la fonctionMod:
sage: R = IntegerModRing(1048) sage: R Ring of integers modulo 1048 sage: a = R(14567) sage: a 943 sage: a in R True sage: Mod(14567,1048) in R True sage: b = R(2) sage: b 2 sage: a*b 838 sage: a^(-1) 519
Onpeutr´esoudredese´quationsmodulaires:
sage: var(’x’) sage: solve_mod([x^2 [(1,), (43,), (34,),
== 1],77) (76,)]
xamodm Onpeutre´soudreunsyst`emedecongruencesdanslequellesmodulesm xbmodn etn; la solutionsont premiers entre euxxomud´neereim´dtetant´elomn.
3
3 Exercices
sage: a = Mod(3,5) sage: b = Mod(2,7) sage: a.crt(b) 23 sage: crt(3,2,5,7) -12 sage: Mod(-12,35) 23
Exercice 1. Poura= 1105,b= 208 calculer le ppcm et le pgcdddeaetbsenterdeiersD.mrnie´etx, yZ tels que la formule de Bezoutd=ax+byosti´vreie´.e
Exercice 2. p Former la listeLdes 15 premiersentiers premiersptels que le nombre de MersenneMp= 21 soit premier. p1 Ve´rierquepourtoutpLle nombrePp= 2Mpestparfait(ie.l`alasom´egaemedess diviseurs propres.
Exercice 3. Pour tout entiern0 on pose : 1 pn= 2 +n[ ] n+1 P 1 +[(n+ 2)/k[(n+ 1)/k]] k=2 o`u[]de´signelatreineite`erpa. 1. Formerla listeLltsee´´lmenestosntlesdonpnpour 0n100. (Indication:lam´ethodefloorerbmonnu)peedacmrterealclluieenpartredti`e 2. Formerla listePde`apartirueenbtoLga´e`auxeml´tsen.2ensupuolssee´rpminatt 3. Soitrsdementel´eed´nelrbmoPqreuirev;e´Pest la liste desrpremiersentiers premiers impairs. (Indication:vouspouvezutiliserunsch´emadecompr´ehensiondutype[p for p ... if ...])
Exercice 4. Leth´eor`emedeDirichlete,quarmnitialletermeieuqitnodhtirte´mssrenaioneuogpraet la raisonqostnrpsr.emieesprombreden´tinnienutneitncouxeetrenrsieem Ecrire enpythonune fonctionDirichletuedse´nnsreitnexquintdo´etaaetqpremiers entre eux et un entierNsedd´eterminelalisteNuedeetiqthm´narimerpsreimretdeesprlareogioss terme initialaet de raisonqqui sont premiers.
Exercice 5. LaiedeFareys´erFnd’ordrenest la liste de tous les nombres rationnels de l’intervalle [0,1] dont lede´nominateurestn. On aF1={0,1}etFnobtis`tnerapadriteFn1en intercalant entre
4
a ca+c deuxnombrescons´ecutifsetdeFn1, le nombre rationnellorsque l’on ab+dn. b db+d Ecrire enpythonune fonctione´rservuicpermettant de contruireFnet calculerF10.
Exercice 6. Re´soudrechacundessyste`messuivantsdecongruences: x6 mod 17 1. x5 mod 11 x3 mod 9 2. 3x10 mod 17
Exercice 7.On prendp= 7 etn= 6. n1. Combienle groupe (Z/pZstne?cno)entiilt-´edeml´ n2. Quelest l’ordre de 1+pdans (Z/pZ(on pourra utiliser une) ?bouclepuis utiliser la fonctionsagemultiplicative order()). n3.V´erierquelegroupe(Z/pZ´engruveeuatern´qilcyctsuortteeu)er.
Proble`me8.ASLame´htdoRe Lebutestdetransmettreunmessagecondentielentoutese´curite´.Lame´thodeRSAesta`el´c publiquesud(notcuoltmenodepeutmalehte´dedodoceeeagcostuenntodeuqerida`tsec fabriqueruncryptogramme).Maisseuller´ecepteurconnaıˆtlecodeded´echirage,etcedernier nepeutpasˆetreretrouve´`alaidedesinformationsrenduespubliques.(celareposesurlefaitque lesalgorithmesconnusdede´compositiondunentierenfacteurspremiersne´cessitentdestemps decalculsimportantspourdesentiersdontlesfacteurspremierssonttr`esgrands,desorteque la connaissance d’un entiernntadeseseeimm´edinaissancnocaltnemeriasseecn´asepqulimpi facteurs premiers.) 1.(a)Onxeunalphabetdontlescaracte`res,num´erote´sde0`alesvr1`tlarinoritu´ecre desmessagesa`transmettre.Cetalphabetestpublicparexemple: 0 0 ABCDEF GHIJ KLM N OP QRST U V W XY Zabcdef ghijklmnopqrstuvwxyz.,; : Ici on als.e`erartc75ac= (b) Onfixe un entiern= 43657458478029293976669622635814729303016339791; cet en-tier est public et est produit de deux grands entiers premiers distinctspetqra´dges secrets. (c) Onfixe un entierc= 3 (qui est lui aussi est public) tel que l’application : C:Z/Zn−→Z/Zn c x−→x soit bijective. 2. Ecrireenpythonune fonctioncryptepermettant de fabriquer un crytogrammectg`a partir d’un messagemsgnnodtebahplaled.´enuqieuemitilastnact`eresntlescarteriunnec´ Pourcelaonproc`ededelafac¸onsuivante: (a) Onremplace chaque lettre du messagemsgsonnum´erodansllahpbateo;ontbeintrap ainsi une listeLd’entiers compris entre 0 etl1. (b)Oninterpre`tecettelisteLntieuneuredcritle´moemcrNen basel
5
(c)On´ecritcenombreNen basen. On obtient ainsi une listeMd’entiers compris entre 0 etn1 : (d)One´l`evechaque´el´ementdecettelistea`lapuissancecmodulon. On obtient ainsi une liste d’entiers compris entre 0 etnc’est le cryptogramme1 ;ctgque l’on envoie au destinataire. 3. Seulle destinataire, qui connaˆıt ladedeoce´egadl´c d= 29104972318686195959201875715334500356126826395 peutd´ecodercemessage.Lapplication 1 C:Z/Zn−→Z/Zn d y−→y estlabijectionr´eciproquedelabijectionC. Ecrire enpythonune fonctiondecrypte permettant de reconstituer le messagemsgritrapa`gotyrcudrammectge`erdelamani suivante : (a)Lemessagecod´ectgest une liste d’entiers compris entre 0 etn1. (b)Chaquee´le´mentdecettelisteeste´lev´ea`lapuissancedmodulon. (c)Oninterpre`tecettelistecommele´crituredunentierNen basen. (d)One´critcenombreNen basel. On obtient ainsi une listeLd’entiers compris entre 0 etl1 : (e)Onremplacechacundescesnume´rosparlalettrecorrespondantedelalphabetetle message d’originemsgsnocerts.e´utite 4. Onan=pqou`petqsont des entiers premiers distincts. (a) Montrerque sicest premier avecϕ(n) = (p1)(q1) l’applicationCest bijective et quedest l’inverse decmoduloϕ(n) (b) Pourquoiconnaissantnetc, le calcul dednt-il`afactoriserrveein? 60 (c)Dansleproble`meonaprisp= 37866809061660057264219253397 etq= 2173 ; l’entiern=pqeaccaevfntsmeitmesieareidtmo´sage. Construire un exemple plus r´ealiste.