Decomposition Product of Prime Factors

Date Decomposition PRODUCT of PRIME FACTORS The number of steps FCT trial division is on(en) most of the time. Special algorithms Their execution time depends I the SPecial Properties OF nimbern as, for example the sheof the greatest Prime Factor . This cate gory includes: (a) The rho algorithm (b) The P-1 algorithm (c) The algorithm based on elli Ptic curves (d) The Pollard - -strassen algorithm, which was Proved to be the Fastest Factorization algorithm. For a ENwe denote a ==mod (a,n). let CISCEUN (X+C)EZ(F) F(x)=F(2)EZN[Z] (2)= C F(FC) K=O KIKY CS Dipindai dengan CamScanner

Date This algorithm has the Following Steps : INPUT NEN, nz3, n is neither Prime, nor Perfect square, bEN. OUTPUT IF the smallest Prime Factor of nis L b,otherwise failure. 1. compute CG-115] 2. Detamine the CoeFFicients of Polynominal f EZNIXI: F(x)= K=1 3. compute gk E (0.1 n-1) such that gk= mod(F(F(C),n) For oL k LC 4.1. If god (gk,n) = 1 For HK E (0.1 (-1) then return failure 4.2. on the Contrary,Let K=min (OEKLC; gcd (9k,n) >1) 5. Return min (d; Pollard's and Strassen's integer Factoring algorithm works correctly anduser O(MCVE)M(109(M)) (log(b)tlog(1096)) word operations, where M is the time For multiplication, and Space For 0 (55.0g (n)) words, This Program uses the Schema of the Faste st alg rithin to com Pute the Value OF a Polynomi al, The (npct variables are the vector wich defines the Polynomial amxm tam -1xm-1 t t a,x tao and x KIKY CS Dinindai dengan CamScanner

Date Horner (a,x):= ME last (a) FL am Fork EM -1.0 Ft F.X + ak te turn F computation program For the CoeFFicients of the Polynomial (x+1) (x+2) (x+c). Prod(c): = UE (11)T return UIF C=1 For KE 2.-C UG stack (O.U) t stack (K.U.O) return U Dinindoi densen