Draft for Information Only
Content
Factorization
FactorizationFactorization is one of the methods to verify whether a number is prime. Prime Factorization Trial DivisionThe direct search factorization is a bruce force factorization method for determining all possible prime factors of a composite number, N, through the repeated examination of divisibility by trial division from a set of nontrivial prime divisors. Let x, y are nontrivial factors of integer N with N=xy. imply It is not necessary to test all numbers from 1 to N1. If x, y are nontrivial factors of integer N with N=xy and x≤y, then x≤√N. Since if x>√N, then y≥x>√N and imply xy>N, which contradicts to the assumption N=xy. Therefore, the trial division can be performed by checking whether x divides N, xN, for x=2 to the floor of √N. if x is found, imply x≡0 (mod N), and y, y=N/x is a factor also. In verifying whether a number N is prime, x can be limited to a nontrivial prime factor. Fermat FactorizationThe Fermat factorization (1600s) from Pierre de Fermat is another way of factoring a composite number by considering the composite number as the difference of squares. This standard binomial can then be factorized into a product. Imply Since all even number can be divided by 2, let x, y are nontrivial odd factors of integer N with N=xy. imply Equate two equations. Imply Both a and b are integers because x and y are odd integers, the sum and difference between any two odd number are even number which is divisible by 2. As x and y are non trivial factors, √N≥x>1 and y≥x, imply a≥1 and b≥0. Instead of testing the non trivial factors x, and y, Fermat factorization examine the integers a and b. Imply Therefore, the Fermat factorization can be performed by checking a from the floor of √N to N. whether the corresponding value of b is an integer and the corresponding terms of the product, (ab) and (a+y) are the non trivial factors of N. Imply In verifying whether a number N is prime, the value of integer a should be choosen from the floor of √N to N. Pollard Rho FactorizationThe Pollard rho factorization or Pollard's Monte Carlo factorization method (1975) from J.M. Pollard is another technique of finding factors of a composite number by making use of probabilistic ideas from transforming a sequencial sequence to a congruential pseudorandom sequence to increase the probability of getting prime factors of the composite number. ©sideway ID: 120400011 Last Updated: 17/4/2012 Revision: 0 Ref: References
Latest Updated Links

Home_{ 5} Business Management HBR_{ 3} Information Recreation Hobbies_{ 7} Culture Chinese_{ 1097} English_{ 337} Reference_{ 67} Computer Hardware_{ 149} Software Application_{ 196} Digitization_{ 25} Numeric_{ 19} Programming Web_{ 621} HTML_{ 65} CSS_{ 58} ASP.NET_{ 62} OS_{ 389} DeskTop_{ 7} Knowledge Mathematics Formulas_{ 8} Algebra_{ 21} Number Theory_{ 206} Trigonometry_{ 18} Geometry_{ 18} Calculus_{ 67} Complex Analysis_{ 21} Engineering Tables_{ 8} Mechanical Mechanics_{ 1} Rigid Bodies Statics_{ 92} Dynamics_{ 37} Fluid_{ 5} Fluid Kinematics_{ 5} Control Process Control_{ 1} Acoustics_{ 19} FiniteElement_{ 2} Physics Electric_{ 23} Biology_{ 1} Geography_{ 1} 
Copyright © 20002020 Sideway . All rights reserved Disclaimers last modified on 06 September 2019