Decomposition Product of Prime Factors

University:
Augusta University
Course:
MATH 4800 | Secondary Mathematics from an Advanced Perspective
Academic year:

2023
Views:

293

Pages:

3
Author:

Aries D.

Decomposition PRODUCT OF PRIME FACTORS The number of ster's for trial division is O~ (3) most of the time. Special algorithms. Their execution time depends the Special Properties of numbern, as, for example, the size of the greatest prime Factor. This category inclules: (a) the rho algorithm. (D) The F-1 algorithm. (C) The algorithm based on elli Ptic curves (d) The Pollard-Strassen algorithm, which was lived to be the Fastest factorization algorithm. For a EN we denote à mod (ain). Let C. 1≤C≤ This algorithm has the following steps: INPUT NEN, 123, 7 is neither Prime, nor Perfect Square, ben. OUTPUT IF the smallest Prime Factor of nis & bictherwise failure. 1. Compute CE [VE]. 2. Detamine the coefficients of Polynomind & EBNEX]: f(x)=(x+k). K=1 3. Compute gr € (0.1,...., n-1) Such that gk = mod (F(FC), n) for OK<< 4.1. If god (gkin) = 1 For HKE (0,1,...., (-1) then return failure 4.2. on the contrary, Let K=min(0=KLC; gcd (9k,n) >1) 5. Return min (d; mod (n,d) = 0,k.c+2=dk.ctc) •Pollard's and Strassen's integer Factoring algorithin works correctly and user (M (VE) M((og(n)) (log(b) + log (log(n)) word operations, Where M is the time for multiplication, and Space For 05.09. (n)) words, This Program uses the Schema of the fastest algorithin to com fule the Value of a Polynomi al, The Infot variables are the vector wich defines the Polynomial amxm 1xm-1 +... ta,x tao and x tam-1x Homer (ax):= me lost (a) Om Fork Em-1.0 J45.x tak return F Computation Program for the coefficients of the Polynomia (x+1)(x+2)...(x+c). Prod (C): = UE (11)T return uif C=1 For KE 2..C U stack LO, U) + stack (k.0.0) return u