Number Theory
Draft for Information Only Content
Pollard's p1 Method
Pollard's p1 MethodPollard's p1 method is a prime factorization algorithm discovered by John Pollard in 1974. Limited by the algorithm, the Pollard's p1 method is only work for integers with specific factors. Pollard's p1 AlgorithmFor a composite integer, n, with a prime factor p, if p1 can be expressed in terms of a product of primes and k is a multiple of p1. By selecting an integer, a, which is greater than 1 and is coprime to n, then
Imply
Since a is coprime to n, a is coprime to p also. Imply
From Fermat's little theorem, if p does not divide a, then Similarly, If k is a multiple of p1, then Imply p is a nontrivial divisor of ap11 or ak1 . or Since p is also a prime factor of n, p divides the greatest common divisor of ap11 or ak1, and n. or Therefore, if the greatest common divisor of ak1, and n is greater than 1, the greatest common divisor is a factor of n also. Pollard's p1 MethodAlthough the Pollard's p1 algorithm cannot be used to determine the prime factor p directly, the Pollard's p1 method is an efficient prime factor finding method for composite integers with specific types of prime factors by choosing and testing some integers systematically. Smooth Number MethodSmooth NumberOne of the number choosing method for integer k is the making use of the concept of smooth number and the specific type of prime factor, i.e. p1 is the product of primes. Let x and B be integers. x is said to be Bsmooth if all the prime divisors of n are less than or equal to B. Example of Smooth Number
Although B is usually a prime number, B can be a composite number providing that B is greater than or equal to the largest prime factor of x. The key information from a Bsmooth number is the prime factor of a number. However, there is no information on the power or index of the prime factor. The lowest Bsmooth of a number is the greatest prime factor of the number. Pollard's P1 Methed by Smooth NumberSince p1 divides k, by assuming p1 is Bsmooth, if k is also Bsmooth then the choosen integer k should be sufficienly large to ensure p1 divides k. Therefore k is the product of all prime factors with powers less than and equal to B and the index or power ei for each prime factor pi less than and equal to B of k should be just less than and equal to n. Imply Pollard's P1 Methed by Smooth Number Example 1For example: n=203=p*q=7*29; let B=5 imply
Therefore for B=5, k5 or (p51)m5 is equal to 1296000. Fermat's Little Theoremlet a=2, by Fermat's little theorem, let p be one of the prime factors of n, imply Greatest Common DivisorSince ak1 is a very large number, before finding the greatest common divisor of n and ak1, ak1 can be raised to the high power modulo n. Imply Using squarings modulo
Using binary squarings modulo
and using the residue to calculate the greatest common divisor. Imply The greatest common divisor of n and ak1 is Using Euclid's algorithm
Imply Integer 7, the greatest common divisor of n and ak1 is also the prime divisor of n. And p1 is 5smooth.
Since the greatest prime factor of p1 is 3smooth also. And therefore the prime factor 7 can also be found by using B=3
let a=2, by Fermat's little theorem, imply p divides 2103681 ≡ 168 (mod 203) The greatest common divisor of n and ak1 is gcd(168,203)= 7 And 7 is the prime divisor of n as before. ©sideway ID: 120500004 Last Updated: 2012/5/15 Revision: 1 
Home (5) Computer Hardware (149) Software Application (187) Digitization (24) Numeric (19) Programming Web (618) CSS (SC) ASP.NET (SC) HTML Knowledge Base Common Color (SC) Html 401 Special (SC) OS (388) MS Windows Windows10 (SC) .NET Framework (SC) DeskTop (7) Knowledge Mathematics Formulas (8) Number Theory (206) Algebra (20) 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) Biology (1) Geography (1)  
Latest Updated Links

Copyright © 20002019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019