Thread: A Factorization Algorithm View Single Post
 P: 92 "Now there are several pairs (s,t) such that st is congruent to one mod five (four pairs to be precise) they are {(4,4),(2,3),(3,2) (1,1)}. Since x and y remain free until later we can consider (2,3) and (3,2) to be the same choice. So picking at random we have only one third chance of getting it right in which case we also need to start with x=0 or we miss the boat all together. These difficulties suggest that we want to use bases that take care of the possible small prime factors right off or else simply divide by the first so many small primes. This is usually recommended even by fellows like Pollard." The sequence of bases that is formed as follows has special properties with regard to size of reduced residue systems locally in the natural numbers. (1a) $$\{\Pi_{i=1}^k p_i | k = 1 ... L\}$$ Here L is determined by the natural number N we wish to factor. This sequence has very special properties. Firstly the bases $$a$$ are products of the first k primes, so by first confirming that N and a are relatively prime we have cleared out those small factors. If it turns out other wise (the Euclidean Algorithm is fast by the way) we simply remove the common factor and start again. Because the reduced residue system is closed under multiplication modulo a we can factor the trailing coefficient of any base a coefficient in a finite number of steps simply by looking at the tables for that base. Consider base 30, where thirty is the product of 2,3 and 5. Suppose N is congruent to 1 mod 30 then any two factor pairs of N must be congruent to one of the following ordered pairs modulo thirty. (2a) {(1,1),(7,13),(11,11),(17,23),(19,19),(29,29)} There would be eight except symmetry reduces this slightly. The size of the reduced residue system for elements of (1a) above is simply to calculate as Euler's totient (3a) $$\phi(p_kp_{k-1}...3*2)=\Pi_{i=1}^k (p_i-1)$$ Furthermore one can look at the set (2a) as the kernel of the map (4a) $$mod 30 :rrs_{30} \otimes rrs_{30} \Rightarrow rrs_{30}$$ Interestingly we only need to store the kernel of this map in it's full form ordered by first entries as (5a) {(1,1),(7,13),(11,11),(13,7),(17,23),(19,19),(23,17),(29,29)} Because from this we can obtain the relevant factorization of any reduced residue modulo thirty by simply multiplying the first element of each ordered pair by the residue. Suppose rather than being congruent to one modulo thirty our natural number was congruent to seven mod thirty. Then we obtain the possible factorizations as mentioned (6a) {(7,1),(19,13),(17,11),(1,7),(29,23),(13,19),(11,17),(23,29)} Reordering and reducing by symmetry we get (7a) {(1,7),(13,19),(11,17),(23,29)} These coorespond to factorization equations for example as (8a) $$N=30z+7=(30x+13)(30y+19)$$ The search area here is calculable so the number of steps in the whole algorithm can be accurately estimated. Now the sequence in (3a) is also special because of the relationship between reduced residue systems of consecutive elements. Consider 6=2*3 and 30=2*3*5. It is clear that every element of the rrs mod thirty is relatively prime to six. So we can generate the rrs mod thirty from the rrs mod 6 as follows. Simply produce the table $$\begin{array}{ 1|c|c|c|c |} x/r&1&2&3&4\\ \hline1&7&13&19&25\\ \hline5&11&17&23&29\\ \end{array}$$ The elements are calculated as 6x+r. Clearly 25 is not in rrs mod thirty but we can quickly remove this in this case because it is not relatively prime to 5 which will be a factor of the new base (30). One must remain so we have quickly obtained the set rrs mod 30 ={1,7,11,13,17,19,23,29}. In general the elements of the array that must be removed can actually be generated from the rrs of the smaller base by simply multiplying the rrs by the new prime factor under standard multiplication. In the above example we want (9a) $$5\{1, 5\} = \{5,25\}$$ So in general using sequence (1a) (10a) $$rrs_{k+1}=\{x \Pi_{i=1}^k p_i+rrs_k |x = 1...p_{k+1}-1\} - \{p_{k+1}rrs_k\}$$ These arguments define a class of sieves that can approach the efficiency one would get if we knew all primes less than the square root of a natural number. The beauty of course is we do not need to know those primes. So we trade some of the work necessary to find those primes for a task we can do in a knowable number of steps. Some theorems that can be proved as excercises. 1) Show that $$\phi(p_kp_{k-1}...3*2)<\phi(n) \forall n > p_kp_{k-1}...3*2$$ 2) Show that if k is a square free natural number $$\phi(k)\leq\phi(n) \forall n > k$$ Notice that there are infinitely many 'ladders' of square free natural numbers that can be used to build sieves just as the sequence (1a) was used and that these sieves are 'locally' minimal as a choice of base for factoring natural numbers by these methods. The final step in this whole process is finding a way to put the approach looked at in the earlier posts of this thread and this last approach into one comprehensive theory.