Exercice 1: la méthode de Pollard pour factoriser un entier de grande taille

> Pollard:=proc(B,a,n)
local d,Q,l,q;

d:=gcd(a,n);

if d>= 2 then return d; fi;

Q:=3;

for q from 2 to B do

if isprime(q) then

l:=floor(ln(n)/ln(q));

Q:=power(Q,q**l) mod n;

fi;

od;

d:=gcd(Q-1,n);

return d;

end;

Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...Pollard := proc (B, a, n) local d, Q, l, q; d := gcd(a, n); if 2 <= d then return d end if; Q := 3; for q from 2 to B do if isprime(q) then l := floor(ln(n)/ln(q)); Q := `mod`(power(Q, q^l), n) end if...

> isprime(2);

true

> debug(Pollard);Pollard(19,3,19048567);

Pollard

{--> enter , Pollard, , args = , 19, , , 3, , , 19048567

d := 1

Q := 3

l := 24

Q := 2293244

l := 15

Q := 13555889

l := 10

Q := 16937223

l := 8

Q := 15214586

l := 6

Q := 9685355

l := 6

Q := 13271154

l := 5

Q := 11406961

l := 5

Q := 554506

d := 5281

<-- exit , Pollard,  (now at top level, ) = , 5281, }

5281

> 19048567/5281;

3607

> Pollard(31,3,19048564);

{--> enter , Pollard, , args = , 31, , , 3, , , 19048564

d := 1

Q := 3

l := 24

Q := 11264945

l := 15

Q := 18931449

l := 10

Q := 1546373

l := 8

Q := 4769761

l := 6

Q := 7530385

l := 6

Q := 18756877

l := 5

Q := 6663377

l := 5

Q := 11081485

l := 5

Q := 2390125

l := 4

Q := 16730869

l := 4

Q := 18831281

d := 72428

<-- exit , Pollard,  (now at top level, ) = , 72428, }

72428

Exercice 2 : Interpolation pour le calcul de zéros d'une fonction

> f:=x->2*cos(x)-3*x;diff(f(x),x);X:=[0.1,0.3,0.5,0.7,0.9];Y:=map(f,X);

f := proc (x) options operator, arrow; 2*cos(x)-3*x end proc

-2*sin(x)-3

X := [.1, .3, .5, .7, .9]

Y := [1.690008331, 1.010672978, .255165124, -.570315625, -1.456780063]

> P:=simplify(collect(interp(Y,X,t),t));

P := -0.3389262941e-3*t^4-0.2064426101e-2*t^3+.5635493679-0.1243627259e-1*t^2-.2457385882*t

> simplify(eval(P, t=0));

.5635493679

> map(f,%);

0.80702e-4

> plot(f);

[Plot]

Exercice 3 : calcul de puissance de matrice

> with(linalg);A:=matrix(5,5,1):
for i to 5 do A[i,i]:=3 od:

evalm(A);

Warning, the protected names norm and trace have been redefined and unprotected

[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...[BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian, addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix, charmat, charpoly, cholesky, col, cold...

matrix([[3, 1, 1, 1, 1], [1, 3, 1, 1, 1], [1, 1, 3, 1, 1], [1, 1, 1, 3, 1], [1, 1, 1, 1, 3]])

> latex(matrix([[2, 1, 1, 1, 1], [1, 2, 1, 1, 1], [1, 1, 2, 1, 1], [1, 1, 1, 2, 1], [1, 1, 1, 1, 2]]));

\left[ \begin {array}{ccccc} 2&1&1&1&1\\\noalign{\medskip}1&2&1&1&1
\\\noalign{\medskip}1&1&2&1&1\\\noalign{\medskip}1&1&1&2&1

\\\noalign{\medskip}1&1&1&1&2\end {array} \right]

> for i from 2 to 4 do evalm(A^i) od;

matrix([[13, 9, 9, 9, 9], [9, 13, 9, 9, 9], [9, 9, 13, 9, 9], [9, 9, 9, 13, 9], [9, 9, 9, 9, 13]])

matrix([[75, 67, 67, 67, 67], [67, 75, 67, 67, 67], [67, 67, 75, 67, 67], [67, 67, 67, 75, 67], [67, 67, 67, 67, 75]])

matrix([[493, 477, 477, 477, 477], [477, 493, 477, 477, 477], [477, 477, 493, 477, 477], [477, 477, 477, 493, 477], [477, 477, 477, 477, 493]])

> I5:=diag(1,1,1,1,1);

I5 := matrix([[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]])

> An:=evalm(matrix(5,5,(i,j)->an-2**n)+2**n*I5);

An := matrix([[an, an-2^n, an-2^n, an-2^n, an-2^n], [an-2^n, an, an-2^n, an-2^n, an-2^n], [an-2^n, an-2^n, an, an-2^n, an-2^n], [an-2^n, an-2^n, an-2^n, an, an-2^n], [an-2^n, an-2^n, an-2^n, an-2^n, a...

> evalm(An&*A);

matrix([[7*an-4*2^n, 7*an-6*2^n, 7*an-6*2^n, 7*an-6*2^n, 7*an-6*2^n], [7*an-6*2^n, 7*an-4*2^n, 7*an-6*2^n, 7*an-6*2^n, 7*an-6*2^n], [7*an-6*2^n, 7*an-6*2^n, 7*an-4*2^n, 7*an-6*2^n, 7*an-6*2^n], [7*an-...

> calculA:=proc(n)
local t;

if n=1 then return 3 else

return  7*calculA(n-1)-2**(n+1);

fi;

end;

>

calculA := proc (n) local t; if n = 1 then return 3 else return 7*calculA(n-1)-2^(n+1) end if end proc

> calculA(3);calculA(4);calculA(5);

75

493

3387

> MonExo:=proc(A,n)
local I5,An,an;

I5:=diag(1,1,1,1,1);

if n=1 then return eval(A); fi;

an:=calculA(n);

An:=evalm(matrix(5,5,(i,j)->an-2**n)+2**n*I5);

return eval(An);

end;

MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...MonExo := proc (A, n) local I5, An, an; I5 := diag(1, 1, 1, 1, 1); if n = 1 then return eval(A) end if; an := calculA(n); An := evalm(matrix(5, 5, proc (i, j) options operator, arrow; an-2^n end proc)...

> MonExo(A,3);MonExo(A,5);

matrix([[75, 67, 67, 67, 67], [67, 75, 67, 67, 67], [67, 67, 75, 67, 67], [67, 67, 67, 75, 67], [67, 67, 67, 67, 75]])

matrix([[3387, 3355, 3355, 3355, 3355], [3355, 3387, 3355, 3355, 3355], [3355, 3355, 3387, 3355, 3355], [3355, 3355, 3355, 3387, 3355], [3355, 3355, 3355, 3355, 3387]])

>