Licence STS Mention MATH L3 ATN Arithmetique
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Elementaire
Licence STS Mention MATH L3 - ATN Arithmetique 1 Entiers rationnels L'anneau Z des 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 On peut obtenir aussi les diviseurs d'un entier, les entiers premiers a un entier donnes et la fonction ? d'Euler : sage: b.
Voir
Licence STS Mention MATH L3 - ATN Arithmetique 1 Entiers rationnels L'anneau Z des 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 On peut obtenir aussi les diviseurs d'un entier, les entiers premiers a un entier donnes et la fonction ? d'Euler : sage: b.
- progression arithmetique
- methode rsa
- multiplicative group
- generateurs du groupe des elements inversibles
- etant determinee modulo
- sage
- elements
- message msg
Publié par
Langue
Français
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 Onpeutobteniraussilesdiviseursd’unentier,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´,etlafactorisationd’unentier: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 corpsQrptseslenfie´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/Znnfisiadsntpr´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,)]
x≡amodm Onpeutre´soudreunsyst`emedecongruencesdanslequellesmodulesm x≡bmodn 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, y∈Z tels que la formule de Bezoutd=ax+byosti´vrefiie´.e
Exercice 2. p Former la listeLdes 15 premiersentiers premiersptels que le nombre de MersenneMp= 2−1 soit premier. p−1 Ve´rifierquepourtoutp∈Lle nombrePp= 2Mpestparfait(ie.l`alasom´egaemedess diviseurs propres.
Exercice 3. Pour tout entiern≥0 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 0≤n≤100. (Indication:lam´ethodefloorerbmonnu)peedacmrterealclluieenpartred’ti`e 2. Formerla listePde`apartirueenbtoLga´e`auxeml´tsen.2ensupuolssee´rpminatt 3. Soitrsdementel´eed’´nelrbmoPqreuirefiv;e´Pest la liste desrpremiersentiers premiers impairs. (Indication:vouspouvezutiliserunsch´emadecompr´ehensiondutype[p for p ... if ...])
Exercice 4. Leth´eor`emedeDirichlete,quaffirmnitialletermeieuqitnodhtirte´mssrenaione’uogpraet la raisonqostnrpsr.emieesprombreden´tinfinienutneitncouxeetrenrsieem 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´nominateurest≤n. On aF1={0,1}etFnobtis’`tnerapadriteFn−1en intercalant entre
4
a ca+c deuxnombrescons´ecutifsetdeFn−1, le nombre rationnellorsque l’on ab+d≤n. b db+d Ecrire enpythonune fonctione´rservuicpermettant de contruireFnet calculerF10.
Exercice 6. Re´soudrechacundessyste`messuivantsdecongruences: x≡6 mod 17 1. x≡5 mod 11 x≡3 mod 9 2. 3x≡10 mod 17
Exercice 7.On prendp= 7 etn= 6. n∗ 1. Combienle groupe (Z/pZstne?cno)entiilt-´ed’eml´ n∗ 2. Quelest l’ordre de 1+pdans (Z/pZ(on pourra utiliser une) ?bouclepuis utiliser la fonctionsagemultiplicative order()). n∗ 3.V´erifierquelegroupe(Z/pZ´engruveeuatern´qilcyctsuortteeu)er.
Proble`me8.ASLame´htdoRe Lebutestdetransmettreunmessageconfidentielentoutese´curite´.Lame´thodeRSAesta`el´c publiquesud(notcuoltmenodepeutmalehte´dedodoceeeagcostuenntodeuqerida`tse’c fabriqueruncryptogramme).Maisseuller´ecepteurconnaıˆtlecodeded´echiffrage,etcedernier nepeutpasˆetreretrouve´`al’aidedesinformationsrenduespubliques.(celareposesurlefaitque lesalgorithmesconnusdede´compositiond’unentierenfacteurspremiersne´cessitentdestemps decalculsimportantspourdesentiersdontlesfacteurspremierssonttr`esgrands,desorteque la connaissance d’un entiernntadeseseeimm´edinaissancnocaltnemeriasseecn´asepqulimp’i facteurs premiers.) 1.(a)Onfixeunalphabetdontlescaracte`res,num´erote´sde0`al−esvr1`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 messagemsgnnodtebahpla’led.´enuqieuemitilastnact`eresntlescarteri’unnec´ Pourcelaonproc`ededelafac¸onsuivante: (a) Onremplace chaque lettre du messagemsgsonnum´erodansl’lahpbateo;ontbeintrap ainsi une listeLd’entiers compris entre 0 etl−1. (b)Oninterpre`tecettelisteLntie’uneuredcrit’le´moemcrNen basel
5
(c)On´ecritcenombreNen basen. On obtient ainsi une listeMd’entiers compris entre 0 etn−1 : (d)One´l`evechaque´el´ementdecettelistea`lapuissancecmodulon. On obtient ainsi une liste d’entiers compris entre 0 etn−c’est le cryptogramme1 ;ctgque l’on envoie au destinataire. 3. Seulle destinataire, qui connaˆıt ladedeoce´egadl´c d= 29104972318686195959201875715334500356126826395 peutd´ecodercemessage.L’application −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 etn−1. (b)Chaquee´le´mentdecettelisteeste´lev´ea`lapuissancedmodulon. (c)Oninterpre`tecettelistecommel’e´critured’unentierNen basen. (d)One´critcenombreNen basel. On obtient ainsi une listeLd’entiers compris entre 0 etl−1 : (e)Onremplacechacundescesnume´rosparlalettrecorrespondantedel’alphabetetle message d’originemsgsnocerts.e´utite 4. Onan=pqou`petqsont des entiers premiers distincts. (a) Montrerque sicest premier avecϕ(n) = (p−1)(q−1) l’applicationCest bijective et quedest l’inverse decmoduloϕ(n) (b) Pourquoiconnaissantnetc, le calcul dednt-il`afactoriserrveein? 60 (c)Dansleproble`meonaprisp= 37866809061660057264219253397 etq= 2−173 ; l’entiern=pqeaccaevfntsmeitmesieareidtmo´sage. Construire un exemple plus r´ealiste.
