This method utilizes discrete binary operations, in particular notice that.(adsbygoogle = window.adsbygoogle || []).push({});

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

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) [tex]Div(xy,a) \leq yDiv(x,a) \leq xDiv(y,a) if y>x[/tex]

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

(1) [tex]N=XY \rightarrow az+t =(ax+s)(ay+r)[/tex]

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

(2) [tex]z = axy+ sy+rx + Div(rs,a)[/tex]

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

Equation 2 can be further dealt with by noting that

(3) [tex]Mod(z,a) = Mod(sy+rx+Div(rs,a),a)[/tex]

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

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

(5) [tex]Div(Div(z,a),a) = Div(xy+Div(sy)+Div(rx)+\{0,1,2\},a)[/tex]

[tex]= Div(xy,a)+Div(Div(sy,a))+Div(Div(rx,a))+Div(\{0,1,2\},a)+\{0,1,2,3\}[/tex]

Or in the sixth step

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

Ah the beauty of the seventh step!

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

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) [tex]xy = Div(xy,a)+Mod(xy,a)[/tex]

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) [tex]Mod(Div(z,a),a) = Mod(xy,a) + Mod(Div(sy+rx+Div(rs,a)),a)[/tex]

[tex]= Mod(xy,a) + Mod(Div(sy),a)+Mod(Div(rx),a)+Mod(\{0,1,2\},a)[/tex]

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 [itex]Mod(Div(sy,a))[/tex].

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Another Base a Factorization Method

**Physics Forums | Science Articles, Homework Help, Discussion**