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


    Attached Files:

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


    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
    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


    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
    simplifies to
    which has roots
    Last edited: Jun 18, 2008
  9. Jun 18, 2008 #8

    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
  10. Jun 19, 2008 #9


    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.

    [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]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


    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]

    Not that this really tells you anything.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook