Algoritmo del MCD
qp
qppqn
=
<=grandi molto primi ,
;
pnnnfloorMCD
np
pnnfloorMCD
=⇒
<<
=
]);mod()!([
2
];)!([
Implementazione veloce
• I := 1;
• D := floor(sqrt(n));
• A : = D
• While ( MCD(A mod n ; n) ==1):• While ( MCD(A mod n ; n) ==1):A := D(D-I);
I := I+1;
• Print(MCD(A mod n; n) = p);
• Il MCD si calcola con l’algoritmo di Euclide
• Per n piccoli si può invertire ovvero partire da D = 2 D = 2*3, D = 2*3*4…..
In PARI/GP
{fattore(n) =local(A,D);
D = floor(sqrt(n));
A = D;
i = 1;i = 1;
while( (p=gcd(Mod(A,n),n)) == 1, A = D*(D-i); i = i+1 );
print p;
q = n/p;
print q
}
Esempio 1
• 187 = 11*17
• floor(sqrt(187))= 13
• 13 ! = 6227020800• 13 ! = 6227020800
• 13 ! Mod 187 = 88
• MCD (88; 187) = 11
Esempio 2
• 91 = 7*13
• Floor(sqrt(91))= 9
• 9 ! = 362880• 9 ! = 362880
• 9! Mod 91 = 63
• MCD (63, 91)=7
Serie di Fibonacci Generalizzate
bx
ax
pqn
1
0
==
=
qpnVMCDnVMCD
nxV
xxx
ba
bx
kk
kk
kkk
,),(1),(
)mod(
) is.Fibonacc1(
21
1
=⇒≠=
+=⇒==
=
−−
Esempio 1
• 91 = 3*13
• Fibonacci classico 1, 1, 2, 3, 5, 8, 13,21,…
• MCD (91, 1) =1• MCD (91, 1) =1
• MCD(91, 2 ) =1
• MCD (91, 3) = 3 stop
Esempio 2
• 187 = 11*17
• Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34
• MCD(187, 1) = 1
• MCD(187, 2) = 1• MCD(187, 2) = 1
• MCD(187, 3) = 1
• MCD(187, 8) = 1
• MCD(187, 13) =1
• MCD(187, 21) = 1
• MCD(187, 34) = 17 stop