1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Integer Factorization Algorithm

  1. Apr 14, 2008 #1
    I am posting an integer factorization algorithm that I have developed. I am hoping for feedback on any obvious flaws that I might have missed before writing a computer programme to test it out.

    Thanks in advance

    Visu
     

    Attached Files:

  2. jcsd
  3. Jun 16, 2008 #2
  4. Jun 17, 2008 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    On the bottom of the first page, you write:

    1/2(d6)x2 + (d4-(1/2d6))x + d1 = y2

    Is this
    [tex]\frac12d_6x^2+(d_4-\frac12d_6)x+d_1=y^2[/tex]
    or
    [tex]\frac{1}{2d_6}x^2+\left(d_4-\frac{1}{2d_6}\right)x+d_1=y^2[/tex]
    or something else?

    Also, where does this quadratic come from? Does x have some value (it isn't used before the equation) or is this simply a member of R[x]? *Why* do we want the left to be a square?
     
  5. Jun 17, 2008 #4

    The first of the two equations you wrote.Apologies for not being clear.

    x is an unknown and so is y.What I am doing is an extension of Fermat's factoring method.In Fermat's method, we express the number to be factorised as the difference of 2 squares.Let's say the number we want to factorise is N. So we want to find a^2 - N = b^2.
    If "a" doesn't work we try a+1, a+2 and so on until we find (a+n)^2 - N = b^2,so we can factorise N by the difference of squares.

    Now the LHS of the equation is already a quadratic equation, so in the next step, I am applying the calculus of finite difference http://mathworld.wolfram.com/FiniteDifference.html to obtain the another quadratic equation which is the one that you mention.
    Actually this is the same as expanding out (a+n)^2-N=b^2 with n and b as the unknowns and replacing a and N with their known values.

    Hopefully this should also explain you other question of why we want the LHS to be square.
     
    Last edited: Jun 17, 2008
  6. Jun 17, 2008 #5
    Your "integer factorization algorithm" depends on the "generic two integer variable equation solver", which depends on prime factoring of integers,etc...:yuck:

    Six of one, half-dozen of the other...
     
  7. Jun 17, 2008 #6
    Actually it doesn't depend on the "generic two integer variable equation solver".I am actually aware that this is not very clear and am working on an improved draft.

    I was just using the "generic two integer variable equation solver" to illustrate the point that any semiprime has only 2 sets of solutuons for the given quadratic equation.
     
  8. Jun 18, 2008 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Not a problem. I'll note that [itex]1/2\cdot d_6=1[/itex] since d6 is always 2, so the equation
    [tex]\frac12d_6x^2+\left(d_4-\frac12d_6\right)x+d_1=y^2[/tex]
    simplifies to
    [tex]x^2+(d_4-1)x+d_1=y^2[/tex]
    which has roots
    [tex]2y=1-d_4\pm\sqrt{d_4^2-2d_4+1-4d_1}[/tex]
     
    Last edited: Jun 18, 2008
  9. Jun 18, 2008 #8
    [tex]2y=1-d_4\pm\sqrt{d_4^2-2d_4+1-4d_1}[/tex]

    Referring to this equation I think you mean 2x on the LHS which is the quadratic formula. You can't use the quadratic formula in this case because both x and y are unknown whereas in the case where you can use the quadratic formula only x is unknown. The equation I have given is a 2nd order Diophantine equation.In other words what you are doing is correct only if
    [tex]x^2+(d_4-1)x+d_1=0[/tex].
     
  10. Jun 19, 2008 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Must have been confusing it with one of the other problems on the boards, sorry.

    I found it useful when looking over this problem to define [itex]\epsilon=\sqrt n-\lceil\sqrt n\rceil+1\in(0,1].[/itex] Then many of the terms can drop out of the equations, and the magnitude of each term is more clear.

    So
    [tex]a_1=\sqrt n+\epsilon[/tex]
    [tex]k_1=2\epsilon\sqrt n+\epsilon^2[/tex]
    [tex]d_1=2(\epsilon+1)\sqrt n+(\epsilon+1)^2[/tex]
    [tex]d_2=2(\epsilon+2)\sqrt n+(\epsilon+2)^2[/tex]
    [tex]d_3=2(\epsilon+3)\sqrt n+(\epsilon+3)^2[/tex]
    [tex]d_4=\sqrt n+2\epsilon+3[/tex]
    [tex]d_5=\sqrt n+2\epsilon+5[/tex]
    [tex]d_6=2[/tex]
    [tex]y^2=x^2+(d_4-1)x+d_1=x^2+(\sqrt n+2\epsilon+2)x+d_1=x^2+(\sqrt n+2\epsilon+2)x+2(\epsilon+1)\sqrt n+(\epsilon+1)^2[/tex]
     
    Last edited: Jun 19, 2008
  11. Jun 19, 2008 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    You won't be able to find an analytical square in R[x, y], since if you could it would be of the form [tex]x^2+2\alpha x+\alpha^2[/tex] and you could equate coefficients:
    [tex]\sqrt n+2\epsilon+2=2\alpha[/tex]
    [tex]2(\epsilon+1)\sqrt n+(\epsilon+1)^2=\alpha^2[/tex]

    [tex]4\alpha^2=8(\epsilon+1)\sqrt n+4(\epsilon+1)^2=n+(4\epsilon+4)\sqrt n+(2\epsilon+2)^2[/tex]
    [tex]8(\epsilon+1)\sqrt n=n+(4\epsilon+4)\sqrt n[/tex]
    [tex](4\epsilon+4)\sqrt n=n[/tex]
    [tex]n=(4\epsilon+4)^2[/tex]

    Not that this really tells you anything.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Integer Factorization Algorithm
Loading...