Factorization_and_Sieve_Algorithms.pdf

Factorization and Sieve Algorithms Factorization Brute Force Just try every possible solutions, maybe not every number If divided by 2 and found not divisible, pointless to divide by 4,6,8… So try all prime numbers Provides an upper bound on the amount of work Complexity is O (( 2n/...

Factorization and Sieve Algorithms Factorization Brute Force Just try every possible solutions, maybe not every number If divided by 2 and found not divisible, pointless to divide by 4,6,8… So try all prime numbers Provides an upper bound on the amount of work Complexity is O (( 2n/2 ) / (n/2)) where n= no. of bits Advantage: Always works No randomness in its operation It has a fixed upper bound Fermat’s differences of squares Works from the fact (x+y)(x-y)=x2- y2 Take an integer N to factor Goal is to calculate (x+y)(x-y)=x2- y2 =N d = x2 - N ( should eventually = y2 )  Algorithm 1. Set x=ceil(sqrt(N)) 2. Set t= 2x + 1 3. Set d= x2 - N ( d is +ve if N is not a perfect square or 0 if N is a perfect square Make t as the diff. b/n x2 and the next square (x+1)2 t= [(x+1)2 - x2 ]=2x+1 |||ly (x+2) 2 - (x+1)2 = 2x+3 which is 2 more than 2x+1) 4. a. If d is a square then stop and go to Step 5 b. Set d to d+t c. Set t to t+2 d. Go to Step 4.a 5. Set x to sqrt(d+N) 6. Set y to be sqrt(d) 7. Return two factors x+y and x-y  Example N=88 1. x=10 2. t=2x10+1=21 3. d= 102 - 88 = 12 4. a. d= 12 +21 = 33 b. t = 21 + 2 =23 ; d is not a square. Repeat step 4 a. d = 33 + 23 = 56 b. t= 23 + 2=25 ; d is not a square. Repeat step 4 a. d= 56 +25 = 81 b. t= 25 + 2 =27 ; d is a square. Go to step 5 5. x = sqrt(81+88) = 13 6. y= sqrt(81)= 9 7. x+y=22 , x-y=4  Example N=3675 1. x=sqrt(3675)=61 2. t=2x61+1=123 3. d= 612 - 3675 = 46 4. a. d= 46 +123=169 b. t = 123 + 2 =125 ; d is a square. Repeat step 4 5. x = sqrt(169+3675) = sqrt(3844) =62 6. y= sqrt(169)= 13 7. x+y=75 , x-y=49 Factorize N=176 Pollard Rho Factorization Algorithm The algorithm is used to factorize a composite number n = pq, where p is a non-trivial factor. A polynomial modulo n, called g(x)=(x^{2}+1) is used to generate a pseudorandom sequence: A starting value, say 2, is chosen, and the sequence continues as x1=g(2) x2=g(g(2)) x3=g(g(g(2))) The sequence is related to another sequence xkmod(p). Since p is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet, in it lies the core idea of the algorithm. Because the number of possible values for these sequences are finite, both the sequence {xk}, which is mod n and the sequence xkmod(p) will eventually repeat, even though these values are unknown  Pollard Rho Factorization Algorithm Contd… Once a sequence has a repeated value, the sequence will cycle, because each value depends only on the one before it. This structure of eventual cycling gives rise to the name "Rho algorithm", owing to similarity to the shape of the Greek character ρ when the values x1mod(p), x2mod(p), x3mod(p) etc. are represented as nodes in a directed graph. Pollard Rho Factorization Algorithm Contd… The algorithm takes as its inputs n, the integer to be factored and g(x), a polynomial in x computed modulo n. It is more common to use g(x)=(x2+1)mod n. The output is either a non-trivial factor of n, or failure. It performs the following steps: Pollard Rho-Factors an integer n 1. Set a=2 2. Set b=2 3. Define g(x)= (x2 + 1) mod n 4. Let d=1 5. If d≠1 then go to Step 6 a. Set a=g(a) b. Set b= g(g(b)) c. Set d=gcd(|a-b|, n) d. Repeat (go to step 5) 6. If d is less than N, return. Otherwise, the algorithm failed to find a factor 7. In that case, the method can be tried again, using a starting value other than 2 or a different g(x). Example: Let n= 8051 and g(x)= 2 (x + 1) i a b d=gcd(|a-b|, n) 1 5 26 1 2 26 7474 1 3 677 871 97 4 7474 1481 1 97 and 8051/97=83 are the factors HW: Factorize n=7171 and n=455459 i a b d=gcd(|a-b|, n) 1 5 26 1 2 26 6557 1 3 677 6347 1 4 6557 2218 1 5 4105 4936 1 6 6347 4560 1 7 4903 375 1 8 2218 4389 1 9 219 5471 101 HW: Factorize n=245 i a b d=gcd(|a-b|, n) 1 5 26 1 2 26 180 Gcd(154,245)=1 3 187 47 Gcd(140,245)=5 4 HW: Factorize n=2781 i a b d=gcd(|a-b|, n) 1 5 26 3 2 3 4 927 and 3 are factors  Pollard’s p-1 It is very likely that at least one factor of a number is B-powersmooth for small B. B-powersmooth means, that every power dk of a prime d that divides p−1 is at most B. e.g. the prime factorization of 4817191 is 1303⋅3697 And the factors are 31-powersmooth and 16-powersmooth respectively, because 1303−1=2⋅3⋅7⋅31 and 3697−1=16⋅3⋅7⋅11. In 1974 John Pollard invented a method to extracts B-powersmooth factors from a composite number. https://cp-algorithms.com/algebra/factorization.html  Some composite numbers don't have B-powersmooth factors for small B. e.g. the factors of the composite number 100 000 000 000 000 493 =763 013⋅131 059 365 961 are 190 753-powersmooth and 1092161 383- powersmooth. We would have to choose B>=190753 to factorize the number. Notice, this is a probabilistic algorithm. It can happen that the algorithm doesn't find a factor. The complexity is O(BlogBlog2n) per iteration. Pollard’s p-1 Step 1:Choose a prime number relatively prime to N and evaluate ak! for some limit Step 2: find the GCD of ak! -1 mod N and N Step 3: if it is non trivial then it is one of the factor  Pollard’s p-1 Requires a list of primes upto some bound B Works on Fermat’s Little theorem Given a prime p and integer b bp-1 Ξ 1(mod p) Find p such that p is a prime factor of N If L is some multiple of (p-1) then p| gcd(bL – 1,N) To get L to be a multiple of (p-1) is to have L be a multiple of several prime factors Algorithm works by computing L=p1e1……pkek Where ei= floor((log B)/(log pi)) and trying to see if (bL – 1) and N have common factors Example: N=899 Choose a=5 51=5 ➔ gcd(4,899)=1 52=25 ➔gcd(24,899)=1 53=125 ➔gcd(124,899)=31 899/31=29 Therefore 29 and 31 are the factors of 899 Sieve Algorithms-Eratosthenes’s sieve Improvements to Eratosthenes's sieve remove all even numbers from the table in memory allows to run Eratosthenes's sieve twice as fast for the same cost in terms of both time and memory consider the three primes 2, 3 and 5. Between, 1 and 30, only eight numbers, namely 1, 7, 11, 13, 17, 19, 23 and 29, are not multiples of either 2, 3 or 5 adding 30 or a multiple of 30 to any number preserves the properties of being multiple of 2, 3 or 5 In any interval of 30 consecutive integers, we know that Eratosthenes's sieve already removes 22 numbers, simply by sieving over the small primes 2, 3 and 5. to consider only numbers of the form (30k + δ), for all integers k and for δ chosen among 1, 7, 11, 13, 17, 19, 23 and 29 Allows us to represent more than three times more numbers than the initial sieve into the same amount of memory Schematic picture of wheel factorization to visualize the algorithmic principle, it is useful to represent the numbers on a modular wheel of perimeter 30  going up to the small prime 11, 480 numbers out of 2310, thus gaining a factor of almost five Using wheel factorization also speeds up the computation drawback of complicating the matter of sieving over larger primes, since the locations of multiples of these primes are no longer evenly distributed in memory  consider the distribution of the multiples of 7 in a wheel of perimeter 30. We already know that our memory only holds numbers which are multiples of neither 2, 3 nor 5. We now need to locate multiples of 7 among these numbers. They are obtained by multiplying together 7 with a number in the wheel, since multiplication by 7 does not change the divisibility by 2, 3 or 5. Thus, mark all numbers of the form: 7 (30k + δ ) for all k and for δ in 1, 7, 11, 13, 17, 19, 23 and 29. These numbers form eight series, one for each value of δ and each series consists in evenly distributed numbers in memory, separated by a distance of 7X 8 as shown in Figure, with one series in each column figure also shows that the starting points of the different series are not evenly spaced. the starting points correspond to the numbers 7, 49, 77, 91, 119, 133, 161 and 203 and their respective locations in memory are 1, 13, 20, 24, 31, 35, 42, 54; assuming that 1 is at location 0. This uneven distribution makes the sieving code more complicated. We need either to sieve with irregular steps or to repeat the sieve eight times, once for each of the different series. With a wheel of fixed size, this can be achieved by embedding all the different cases into the program. Finding primes faster: Atkin and Bernstein's sieve Atkin and Bernstein proposed a new algorithm, not based on Eratosthenes's sieve constructed from 3 subroutines each addressing a subset of the prime numbers, using a characterization of primes which does not make use of divisibility. First -Used to find primes congruent to 1 modulo 4 second finds primes congruent to 1 modulo 6 third finds primes congruent to 11 modulo 12. Since all primes, but 2 and 3, are of these forms these three subroutines suffice. For primes congruent 1 modulo 12, we need to choose either the first or second subroutine. The algorithm is based on the following theorem: A square free integer is one which is not divisible by any perfect square other than 1 The algorithm: 1. Create a results list, filled with 2, 3 and 5. 2. Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked non prime. 3. For each entry number n in the sieve list, with modulo-sixty remainder r: 1. If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n 2. If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n. 3. If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 – y2 = n when x > y. 4. If r is something else, ignore it completely. 4. Start with the lowest number in the sieve list. 5. Take the next number in the sieve list still marked prime. 6. Include the number in the results list. 7. Square the number and mark all multiples of that square as non prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes. 8. Repeat steps four through seven https://www.geeksforgeeks.org/sieve-of-atkin/ Example: Given the limit 20 print all prime numbers smaller than or equal to the limit Step0: Set status for all numbers as False. Special numbers are 2,3 Step1: Generate values for the condition 4x2 + y2