Another Base a Factorization Method

[Playdo]

This method utilizes discrete binary operations, in particular notice that.

(I1) Div(x+y+z,a)=Div(x,a)+Div(y,a)+Div(z,a)+\{0,1,2\}

This means that for one of the elements of the included set {0,1,2} the equation is true. This notation is quite useful for carrying out long calculations using integer division as will be apparent in a moment.

Also note that

(I2) Div(xy,a) \leq yDiv(x,a) \leq xDiv(y,a) if y>x

Now we first start with a type of quadratic template for a natural number N, that is

(1) N=XY \rightarrow az+t =(ax+s)(ay+r)

Notice we do not require N and a coprime. This leads immediately to

(2) z = axy+ sy+rx + Div(rs,a)

This is because t=Mod(rs,a) was removed after expanding the product XY.

Equation 2 can be further dealt with by noting that

(3) Mod(z,a) = Mod(sy+rx+Div(rs,a),a)

(4) Div(z,a) = xy + Div(sy+rx+Div(rs,a)) = xy + Div(sy)+Div(rx)+Div(Div(rs,a),a) + \{0,1,2\}

Equation four can be categorized depeending on the relationships of s to y and r to x. Notice that Div(Div(rs,a))<Div(a-2,a) = 0 therefore this term is obliterated. If we restrict x and y to be less than a then Div(sy,a)<a-2. So by dividing (4) by a again we obtain

(5) Div(Div(z,a),a) = Div(xy+Div(sy)+Div(rx)+\{0,1,2\},a)
= Div(xy,a)+Div(Div(sy,a))+Div(Div(rx,a))+Div(\{0,1,2\},a)+\{0,1,2,3\}

Or in the sixth step

(6) Div(Div(z,a),a) = Div(xy,a) + \{0,1,2,3\}

Ah the beauty of the seventh step!

(7) Div(xy,a) = Div(Div(z,a),a)-\{0,1,2,3\}

After this we recognize that in short order we know a key ingredient if you will of xy since the division algorithm shows us that

(8) xy = Div(xy,a)+Mod(xy,a)

But of course we know that Mod(xy,a) is greater than zero and less than a, this is not as impressive as we wish it to be. if N and a are coprime we reduce the residues to be searched to the reduced residue system modulo a. But perhaps by taking the modulus of Equation four we can obtain a better estimate.

(9) Mod(Div(z,a),a) = Mod(xy,a) + Mod(Div(sy+rx+Div(rs,a)),a)
= Mod(xy,a) + Mod(Div(sy),a)+Mod(Div(rx),a)+Mod(\{0,1,2\},a)

The modulus of the set {0,1,2} is clearly equal to itself. The modulos of the terms containg sy and rx will be harder to come by. In fact right now I do not see a way past the terms of the form Mod(Div(sy,a))[/tex].

 

[Playdo]

In fact right now I do not see a way past the terms of the form Mod(Div(sy,a))[/tex]<br /> <br /> But what if we study the relationship<br /> <br /> (12) Mod(Div(sy,a)+Div(rx,a),a)=Div(Mod(sy,a),a)+(Div(Mod(rx,a),a)<br /> <br /> How are these two expressions different? Suppose we have<br /> <br /> (13) Div(sy,a) \leq sDiv(y,a)<br /> <br /> Where we have restricted y to be less than a. Then<br /> <br /> (14) Mod(Div(sy,a),a) \leq Mod(sDiv(y,a),a) <br /> = Mod(s,a)Mod(Div(y,a),a)=Mod(s,a)*0<br /> <br /> There are a lot of equations in this derivation so we will have to work some simple examples just to get a better feel for the whole thing but if this is right we can pick up from (9) above and right <br /> <br /> (15) Mod(Div(z,a),a) -\{0,1,2\} = Mod(xy,a)<br /> <br /> We have extraceted xy from the equation (2) above and arrived at a set of five systems of two independent equations in four unknowns. Namely the systems<br /> <br /> (S1) <br /> <br /> (S1:1)xy = Div(Div,z),a) +Mod(Div(z,a),a)-\{0,1,2,3,4,5\}<br /> (S1:2)z = axy+sy+rx+Div(rs,a)<br /> <br /> This would appear daunting still because r and s are unknown residues of a. However if we pick a so that the reduced residue system has special properties some of the apparent difficulty vanishes. Suppose a is prime, then every element less than a is in the reduced residue system which is an abelian group under multiplication modulo a. Is this useful?<br /> <br /> If we can find x and y from the five equations (S1:1) we can rewrite (S1:2) as (S1:2:E1) the E means evolved from,<br /> <br /> (S1:2:E1) N = az+t = a^2xy+asy+arx + rs<br /> <br /> And then<br /> <br /> (S1:2:E1:E1) or more simply (S1:2:1:1) is<br /> <br /> (S1:2:1:1) r = \frac{az-a^2xy - asy}{ax+s}<br /> <br /> If as I have discussed in other threads the (r,s,Div(rs,a)) triples are esay to find and the r.r.s. modulo a is relatively small in size N falls open like a roasted pistachio.<br /> <br /> Much of the arithmetic here is predicated on the notion that x and y are small. I want to take some time to look at this using base 6 which has a very nice r.r.s. and the using the larger polynomials discussed in other threads. Because what appears to be happening here is the interplay of two processes that have ot be iterated. There is a top-side iteration represented by xy and a bottom-side iteration represented by rs and the residue system modulo a. Finding the best combination of techniques to minimize the interval of iteration from top and bottom may be worth looking into. <br /> <br /> I see little benefit to considering cases where N and a are not coprime, although the calculation above was carried out under that premise. The reason is that if N and a are not coprime, then some zero divisor of a divides N, we can factor a to find one divisor of N. This is useless for RSA type numbers composed of only two very larger prime factors.