Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Construct for a Base a Factorization Algorithm

  1. Oct 22, 2006 #1
    This is an attempt to right this out very clearly. The other thread on this is sort of the scratchboard for these ideas.


    (1) [tex]N=\beta(N,a,2) =Div(N,a^2)a^2+Div(N-Div(N,a^2),a)a+Mod(N,a)[/tex]

    Suppose N and a are coprime. In general factor pairs (X,Y) of N will multiply base a as follows.

    (2) [tex]XY = (ax+r)(ay+s)[/tex]

    Where r and s are in the reduced residue system modulo a.

    (1) and (2) lead to the general system

    (3) [tex]Div(N,a^2) = xy+u[/tex]
    [tex]Div(N-Div(N,a^2),a) = sx+ry+t-au[/tex]
    [tex]Mod(N,a) = rs-at[/tex]

    Three equations in six unknowns. If I choose a to be small and special then all the possible triples (r,s,t) for a given N are known. This is an advantage. Suppose further that u is "small" so that pursuing solutions by enumerating u is fast.

    Then we are essentially left with a set of systems of two equations in two unknowns

    (4) [tex]Div(N,a^2) = xy+u[/tex]
    [tex]Div(N-Div(N,a^2),a) = sx+ry+t-au[/tex]

    Letting [itex]C_2 = Div(N,a^2)[/itex] and [itex]C_1 = Div(N-Div(N,a^2),a)[/itex] and solving (4) for x obtains

    (5) [tex]x = \frac{(C_1+au-t)\pm\sqrt{(C_1+au-t)^2-4sr(C_1-u)}}{2s}[/itex]

    Again if a is chosen well then we know all possible (r,s,t) triples and we know C[1] and C[2], we are only enumerating u and checking to see if either root is an integer.

    Two generalize this method we need to do a few things.


    (6) [itex]N=\beta(N,a,n) =Div(N,a^n)a^n+Div(N-Div(N,a^n),n)a^{n+1}+...+Mod(N,a)[/itex]

    No the forms XY can take are now more varied and depend on n. So if we use a fourth degree template for N we could have factor pairs where both are quadratic in a, where one is linear and one is cubic, or where one is in the r.r.s modulo a and the other is quartic in a. So we have added categories (non-technical term) to the search but we have effectively reduce the size of the search are by much more. So the search area now is around fourth root of N, but we have the added value of being able to use a smaller a whose residue system is easier to manage. The issue that becomes important is the relative rate of increase in new categories realted to reduction in search relative to N.


    I am going to do a general calculation of this using base 6 because it is easy to work with.

    Notice that [itex] (r,s,t) =\{(1,1,0),(1,5,0),(5,1,0),(5,5,0)\}[/itex]

    Quadratic Template

    [itex]N=\beta(N,a,2) =Div(N,6^2)6^2+Div(N-Div(N,6^2),6)6+Mod(N,6)[/itex]

    Setting in (r,s,t) we end up with four quadratic systems that can be solved for x.

    [tex]Div(N,6^2) = xy+u[/tex]
    [tex]Div(N-Div(N,6^2),6) = sx+ry+t-6u[/tex]

    If u = 0 then [itex] sx+ry+t<6[/itex] meaning


    So let x = y = 3 to get an upper bound on N that are factored easily by these systems and we obtain N < 19^2 = 361.

    Cubic Template

    [itex]N=\beta(N,a,3) =C_36^3+C_26^2+C_16+Mod(N,6)[/itex]

    Now we have to consider two forms for the factor pair (X,Y)

    a) [tex]XY = (6^2x_2+6x_1+r)(6y_1+s)[/tex]

    b) [tex]XY = (6^3x_3+6^2x_2+6x_1+r)s[/tex]

    The second is trivial since it says that five divides N, so we add the condition that N is coprime with 30 to handle this generically for all higher order templates.

    Expansion of (a) leads to the system

    [tex]C_3 = x_2y_1+t_2[/tex]
    [tex]C_2 = x_2s+x_1y_1+t_1-at_2[/tex]
    [tex]C_1 = sx_1+ry_1+t_0-at_1[/tex]
    [tex]C_0 = rs-at_0[/tex]

    Note: Now we recognize that u and t in the quadratic template were just different names for carried values, they should both be thought of as part of one sequence {t}.

    This system is really three equations in five unknowns since we know all the triples (r,s,t[0]). So we have four systems just as in the quadratic template. If t[2] is zero we get still four systems by each has three equations and four unknowns. If also t[1] is zero we now have three equations in three unknowns, name x[1], x[2] and y[1].

    The bounds on easily factorable N for this template are found from the inner equations


    Let x[2]=x[1]y[1]=3 and you get a number N about (36*3+6*1+1)(6*3+1)=109*19

    So for every nth degree template base 6 you can find an upper bound on the numbers N that are easily factored by one of the resulting systems. In the Cubic Template we obtained a larger maximal N without any added number of systems because degree three is either 2+1 or 3+0 (which is redundant in this construct).

    For the Quartic Template we would have added the systems 3+1, 2+2, 4+0 (again redundant, we have already divided by 5), so we have 8 systems of three equations in three unknowns to solve which essentially results in eight cubic polynomials.

    However the assumption that all N less than the bound estimated by taking all carries after t[0] to be zero are easily factored is not true. t[1] may be non-zero and t[2] zero, later I will come back and clarify that and investigate it more.

    Before doing that look at the Template arithmetic that shows how many systems we have for the nth degree template.

    Degree|Forms|Total Systems (Forms times 4)|Max N(?)

    2| 1+1 | 4| <216
    3| 2+1 | 4 | <
    4 | 3+1, 2+2| 8|
    5 | 4+1, 3+2 | 8|
    6 | 5+1, 4+2, 3+3| 12|
    7 | 6+1, 5+2, 3+4 | 12|
    n | (n-1)+1,... | 2(n-1)| < 6^(n+1)

    But of course we have to yet investigate the details of Max N, there is a space that has to be searched related to the set of carries t. So far it appears that the number of new systems to be searched increases linearly 2(n-1) while the upper bound of number easily factored grows exponentially. This is probably not true and the place where the details are hidden is the search space associated with the sequence of carries t. Of course I said that already. I'll be back to post in this thread when I have worked that out more completely.

    The nth degree template systems can be solved using any method. I’ll try to develop this further so that the whole process is perfectly clear from start to finish. If use the convention of solving for the largest x then the quadratic template system is solved by solving this quadratic equation.

    (7) [tex]sx^2+x(t-au-Div(N-Div(N,a^2),a))+rDiv(N,a^2) = 0[/tex]

    In general the rational roots test leads to factorization of Div(N,6^n) as the only hurdle base 6. It would appear that there is not much work to be had after the systems are properly formed.
    Last edited: Oct 23, 2006
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted