(*Calcul du residu d'un entier Modulo n: Mod[n,m]*)

Mod[134,43]

(*Factorisation d'un entier: FactorInteger[n]*)

FactorInteger[234567891]

(*Quotient d'un entier par un autre:Quotient[m,n] (le reste est donne par Mod[m,n]*)

Quotient[134,43]

(*Plus grand diviseur commun de plusieurs nombres: GCD[n1, ... , nk]*)

GCD[100,250,412]

(*Plus petit commun multiple de plusieurs nombres: LCM[n1, ... nk]*)

LCM[4, 6, 13]

(*Ecriture d'un nombre en base b: IntegerDigits[n,b]*)

IntegerDigits[143,2]

(*Test si un nombre est premier:PrimeQ[n]*)

PrimeQ[2356713]

PrimeQ[81636923]

(*Calcul de a^b (Mod n) de facon plus efficace que par Mod[a^b,n]:PowerMod[a,b,n]. La commande fonctionne avec b<0*)

PowerMod[4,340,81636923]

(*Calcul de la fonction d'Euler: EulerPhi[n]*)

EulerPhi[2356713]

(*Verification que deux entiers sont premiers par factorisation*)

FactorInteger[217546422192682043]

FactorInteger[8369567977777368712343087]

(*La commande Orime ne fonctionne pas si les entiers sont trop gros*)

Prime[8369567977777368712343087]

(*Exemple de code RSA.  Le choix des deux entiers premiers p et q*)

p=217546422192682043

q=8369567977777368712343087

(*En les multipliant on obtient la cle n*)

n=p*q

(*On calcule Phi(n)*)

A=EulerPhi[n]

(*Choix d'une cle d'encryption. On a choisi au hasard.*)

e= 123456789

(*On verifie que e est relativement premier avec A=Phi(n).*)

GCD[e, A]

(*La commande ExtendedGCD donne les x et y tels que (e,A)= xe + yA.*)

ExtendedGCD[e, A]

{1,{-172013368401488150719375167743618039140451,11663320}}

(*Verification.*)

-172013368401488150719375167743618039140451*e+A*11663320

(*La cle de decryption d est congrue modulo A au x qui est negatif.*)

d=Mod[-172013368401488150719375167743618039140451,A]

(*Verification que ed est congru a 1 modulo A= Phi(n).*)

Mod[e*d, A]

(*Le message a envoyer.*)

m=123456789012341219111

(*L'encodage ne fonctionne pas par la commande Mod. Il faut plutot utiliser la commande PowerMod.*)

a=Mod[m^e,n]

(*Le calcul du message encode a.*)

a=PowerMod[m,e,n]

(*Le calcul du message decode b.*)

b=PowerMod[a,d,n]

(*Verification que b=m.*)

b-m

(*Calcul du symbole de Jacobi:JacobiSymbol[n,m]*)

JacobiSymbol[245, 2356713]

R=Table[Random[Integer,{0,9}],{30}]

a=1+Sum[R[[n]]*10^n,{n,1,30}]

PrimeQ[a]

JacobiSymbol[155,a]

PowerMod[155,(a-1)/2,a]

JacobiSymbol[23587,a]

PowerMod[23587,(a-1)/2,a]

JacobiSymbol[4467906,a]

PowerMod[4467906,(a-1)/2,a]

JacobiSymbol[4467906801,a]

PowerMod[4467906801,(a-1)/2,a]

FactorInteger[a]

(*Reste de la division d'un polynome par un autre*)

PolynomialRemainder[x^5+4*x^4-3*x^3+2*x^2+7*x-3, x^3+2*x^2-8*x-9,x]

(*Reste de la division d'un polynome par un autre quand les coefficients sont dans le corps fini F_p, ici p=11*)

PolynomialRemainder[x^5+4*x^4-3*x^3+2*x^2+7*x-3, x^3+2*x^2-8*x-9,x , Modulus->11]

(*V/rification que x est une racine primitive de x^3+x+1 quand les coefficients sont dans F_2*)

PolynomialRemainder[x^4,x^3+x+1,x, Modulus->2]

PolynomialRemainder[x^5,x^3+x+1,x, Modulus->2]

PolynomialRemainder[x^6,x^3+x+1,x, Modulus->2]

PolynomialRemainder[x^7,x^3+x+1,x, Modulus->2]