A new prime factoring algorithm?

[Visu]

Hi would appreciate any feedback on this method I've developed. I've also attached a pdf for those who wish to look at it in their own time.I've been unable to test it out since I am not a programmer but I think the math is sound.

Best Regards

Visu

If the number to be factored is N, express it in the form (a12 + a22 +...+ an2) – (b12 + b22 +...+ bn2 )
This can be done by the following procedure

a12 – N = k1 (where a1 is the next integer > (N)1/2 )
b12 – k1 = k2
and so on until kn = 0

Now [(a12 + a22 +...+ an2) + k ] = A2 and [(b12 + b22 +...+ bn2 ) + k] = B2 - (1)
where N = A2 – B2
one value of A and B is given by A = ((N+1)/2) and B = ((N-1)/2) and for prime numbers this is the only way to express N as a difference of two squares and hence there will only be one value of k which can be easily found . We will refer to this as k1 . For odd composite numbers there will be other values of k satisfying the equation corresponding to the number of factors they have. We now obtain a binary quadratic equation corresponding to N using the above information.
We do this as follows:

(a1 + 1)2 – (a12 + a22 +...+ an2) =d1

(a1 + 2)2 – (a12 + a22 +...+ an2) =d2

(a1 + 3)2 – (a12 + a22 +...+ an2) =d3

and likewise for b to get e1, e2 and e3. Next using calculus of finite difference we obtain

d1 d2 d3
d4 d5 d6

where we subtract the number on the left from its neighbor on the right to obtain the next row.
And proceed to obtain the equation:
1/2(d6)x2 + (d4-(1/2d6))x +d1 = 1/2(e6)y2 + (e4-(1/2e6))y + e1
This is a Diophantine equation of the form A x2 + Bxy + C y2 + Dx + Ey + F = 0. While there are analytical methods to solve this type of equation they involve the use of factorization which we wish to avoid. Hence we will go by the rational point on conics route. Using

A x2 + Bxy + C y2 + Dx + Ey + F = 0

and the equation of the line given by

y = y1 +m(x-x1)

and considering the sum of roots we obtain the parametrization of x given by

x = [( x1 Cm2 -(2C y1+ E)m – (By1 + Ax +D)] / ( Cm2 + Bm + A) -(2)

and x1 and y1 are the solutions to the equation at k1
In our case the above Diophantine equation is actually of the form
x2 + Dx + F1 = y2 + Ey + F2 = k ( where F = F1 –F2) and the k is the same k as in (1)
So we just consider x2 + Dx + F1 = k -(3)
and substitute (2) into (3) to get the parametrized version of (3)
Now for a number N with only two prime factors there will only be two integer values of k satisfying (3) one of which k1 can be found. Hence all rational solutions to (3) have to be multiples of either k1 or k2. To find the other value we run through various values of m clear fractions and see if they are 0 (mod k1). If they are we discard these values. If they are not they have to be 0 (mod k2 ) we store them until we get 2 such values and compute their GCD to obtain k2. Having obtained k2 we can work out the two prime factors of N.

[akruppa]

The typesetting in the posting is a little messed up, but ok in the pdf. I suppose b_[I]n[/I] is the smallest integer so that b_[I]n[/I]² ≥ k_2[I]n[/I]-1. Also, I think you're using the variable name k for different things. If so, can you clarify?

I can't say I understand how the finite differences or finding the rational on the conic work, but someone with more experience very well might. Just one question:

To find the other value we run through various values of m clear fractions and see if they are 0 (mod k₁)

Do you mean "run through various values of m, clear the fractions, and see if they are 0 (mod k₁)?" If so, how many m do you need to go through?

Alex

[Visu]

Firstly apologies for the typesetting. I just cut and paste from my original document and didn't realise that it will end up all funny.

For your second question,
I'll provide a numerical example.

we start with 901:
sqrt(901)<31^2 so
31^2 -901 = 60
sqrt(60)<8^2 so
8^2-60 = 4 and
4 = 2^2 so
2^2 - 4 = 0
so (31^2 + 2^2) - (8^2) = 901
then (31^2 + 2^2 + k) - (8^2 + k ) = 901. where the k values will make the expressions in the brackets a perfect square.(I am trying to do something similar to Fermat's factoring algorithm.For a semiprime there will only be two such values. The k's with a subscript are different from the k's in the bracket but we do not need the k's with the subscript subsequently. I think I will change my original to make things clearer.

[Visu]

Also the running through m is the part I've been unable to do, since I am unable to program. But my reasoning is that we have a hyperbola which has. infinitely many rational points. These points are a multiple of k1 or k2 only.(Otherwise our semiprime will have more than 3 factors!) Hence we have a 50/50 chance in infinity of hitting a multiple of either k1 or k2. What I'm hoping is that is if there is a consensus that the math is sound that someone might be able to help me code and test the algorithm. If there are any flaws in the math it will be spotted here and no one will have to waste too much time.

Visu

[Visu]

Made some alterations to the original pdf to avoid using the same symbols for different variables. This should sort out some of the confusion

Cheers

Visu

[R.D. Silverman]

Originally Posted by Visu

then (31^2 + 2^2 + k) - (8^2 + k ) = 901. where the k values will make the expressions in the brackets a perfect square.

The values 31^2, 2^2, and 8^2 are irrelevant. They are a smokescreen.
You are simply trying to factor 901 via Fermat's Method of expressing it
as the difference of two square. We have 35^2 - 18^2 = 901.
You simply choose to represent 35^2 = 1225 as (31^2 + 2^2 + 260)
and 18^2 = 324 as (8^2 + 260) This is a very roundabout and
unnecessarily expensive way of finding a representation as the difference
of two squares. --> It is *useless* (sorry to burst your bubble)


Fermat's method itself is pretty much useless for any composites over 25
digits.

[akruppa]

As far as I understand it, his idea was to contruct a good k more efficiently by looking for rational points on a conic. I don't understand the idea well enough to say anything about its merit. Is the approach inefficient?

Alex

[Fusion_power]

I looked at this thread yesterday and recognized it as a variant of Fermat's squares method. The method is inefficient because the underlying calculations involve finding square roots and performing division. Computers don't do these very efficiently so add the inherent inefficiency of the method plus the inefficiency of coding this into an algorithm and the performance is unacceptable by comparison with other methods.

I put together a crude routine in ubasic and found out just how bad it really was.

Interestingly enough, there are two ways of applying Fermat's squares method, one of which I was unable to find documented. This thread's approach appears to be based on Fermat's original method. The second method is based on finding the largest square greater than the number to be factored. Neither is of much real use except as trivia answers.

Fusion

[Visu]

Originally Posted by R.D. Silverman

The values 31^2, 2^2, and 8^2 are irrelevant. They are a smokescreen.

Well I could have picked random numbers as you seem to be implying but the trouble with that is that if the numbers I selected are wrong ( ie deviate to much from the nearest square) then the coefficients in the conics portion will be too large. This is the best compromise that I could come up with.

You are simply trying to factor 901 via Fermat's Method of expressing it
as the difference of two square. We have 35^2 - 18^2 = 901.
You simply choose to represent 35^2 = 1225 as (31^2 + 2^2 + 260)
and 18^2 = 324 as (8^2 + 260) This is a very roundabout and
unnecessarily expensive way of finding a representation as the difference
of two squares. --> It is *useless* (sorry to burst your bubble)

From your reply it seems you have not looked beyond this first step. Instead of directly computing the difference of the two squares by I am setting up a diophantine equation whose "only" rational solutions are linked to the factors of the integers in question and trying to solve the equation in question.

Fermat's method itself is pretty much useless for any composites over 25
digits.

But Dixon's method and in turn the quadratic sieve are based on this approach.While the actual Fermats method might have been slow don't dismiss the modifications to this out of hand.

[Visu]

Originally Posted by Fusion_power

I looked at this thread yesterday and recognized it as a variant of Fermat's squares method. The method is inefficient because the underlying calculations involve finding square roots and performing division. Computers don't do these very efficiently so add the inherent inefficiency of the method plus the inefficiency of coding this into an algorithm and the performance is unacceptable by comparison with other methods.

I put together a crude routine in ubasic and found out just how bad it really was.

Interestingly enough, there are two ways of applying Fermat's squares method, one of which I was unable to find documented. This thread's approach appears to be based on Fermat's original method. The second method is based on finding the largest square greater than the number to be factored. Neither is of much real use except as trivia answers.

Fusion

Well how bad is it really? Like I said I could use the feedback. Any data that you generated would also be appreciated.

Visu

[Visu]

Correct me if I'm wrong but division and square rooting are still performed in polynomial time. The first step contains no division and maybe at most 8 instances of square rooting and even then the last few numbers become so small that the calculation can be performed on a pocket calculator.

No division or finding of square roots is involved in the second step of finding the conic representation of the numbers.

Until the final step of finding k we do not need to do any division and even in that step we are essentially performing a test of divisibility (by taking mod of k1) which to me seems to be a common feature of all primality testing or factorizing methods.

Visu