Prime Factoring Algorithm

[Visu]

Originally Posted by Uncwilly

My understanding is that Mathematica or other program can be used to perform the need calculations.

Mathematica is way out of my budget. I don't qualify for the student or educational version and the standard version (download) is about Singapore $3000. That's almost a months salary spent on something I might only use for this one instance. I've been looking at PARI/GP but again a relevent programming background is necessary.I'm leaning towards learning and using Python. Any other ideas would be appreciated.

Visu

[cheesehead]

Originally Posted by Visu

Looking for comments/criticisms before I proceed further. The idea seems (at least to me) too promising to abandon but as of now is still "half baked".I am hoping other eyes and brains can help me see the things that I have missed.

On the first page of your PDF, you write that "we can find" (a₁+n)² - N = d_n where d_n is a square.

If you've found that, then you have a representation of N as the difference of two squares,

(http://mathworld.wolfram.com/Fermats...ionMethod.html)

(http://en.wikipedia.org/wiki/Fermat'...ization_method)

so N has factors

a₁+n + sqrt(d_n)

and

a₁+n - sqrt(d_n)

(unless I've misread or misinterpreted your PDF).

Do you mean something else by "we can find"? -- that you aren't actually proceeding past a₁+3 and d₃?

[Visu]

Originally Posted by cheesehead

On the first page of your PDF, you write that "we can find" (a₁+n)² - N = d_n where d_n is a square.

If you've found that, then you have a representation of N as the difference of two squares,

(http://mathworld.wolfram.com/Fermats...ionMethod.html)

(http://en.wikipedia.org/wiki/Fermat'...ization_method)

so N has factors

a₁+n + sqrt(d_n)

and

a₁+n - sqrt(d_n)

(unless I've misread or misinterpreted your PDF).

Do you mean something else by "we can find"? -- that you aren't actually proceeding past a₁+3 and d₃?

Yes the idea is to get N as the representation of 2 squares. I am not proceeding past a₁+3 and d[sub]3. I use the first 3 values of d to obtain a quadratic equation that describes all d's in the sequence using this http://mathworld.wolfram.com/FiniteDifference.html
Martin Gardner's Colossal Book of Mathematics also has an excellent description of this method.

Lets say the quadratic equation you get is Ax^2 + Bx + C. For d_n to be a square this equation is also a square so now we can write
Ax^2 + Bx + C = y^2 ( replace d_n by y^2) . I think skipping slightly ahead to page 2 where I provide a numerical example will make things clearer. Also try substituting in x=0,1,2 into the quadratic equation. You should get d₁,d₂,d₃

[Visu]

This is in addition to my previous post. What Fermat's algorithm does is say find
d_n = y^2 . What I'm doing is expressing the d's as Ax^2 + Bx + C and since we know we want a square number stating that we want to solve Ax^2 + Bx + C = y^2.

[grandpascorpion]

Originally Posted by wblipp

To sell to Bill Gates. From his book "The Road Ahead"

"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers."

LOL

[m_f_h]

Originally Posted by Visu

I thought for a minute that some requirement for trial division managed to sneak in. I was fairly certain that I left out trial divisions, iterations that loop indefinitely and sievings the usual road bumps in the way of an amateur mathematicians' road to glory. ( I might have divided something by 0 though.)

Trial division by 0 is unlikely to succeed...

[m_f_h]

Originally Posted by Visu

Yes the idea is to get N as the representation of 2 squares.

somewhat more precision is needed in mathematics.

As remarked, if N is a difference of 2 squares >0, it's trivially composite, N=(a-b)(a+b).

Thus, if N is not composite, you can NOT find a d_k in the list
d_k = (a+k)^2-N

This clearly shows that the 3rd phrase of your document,
"...so that we can find (a1 + n)^2 – (N) = dn where dn is a square number."

is WRONG.
Thus, there is no "Next,..." possible, from that point on, since it is never reached.


You also say
"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."
But then, in the example, you use again alpertron's QUAD.HTM.

All of this does not make sense.

As a final note, you don't need to spend years on learning a programming language or on programming. If you have a clear "method", this means "algorithm", and you just can write it in English:
Given N, let a = floor( sqrt( N )), d_k = (a+k)^2-N for k=1,2,3
Let ... ; If ... then ... ; etc.

Or at least, develop 2 or 3 significant examples "by hand" from the start to the end, without saying "we could... but we want to avoid...": Just use the method and only the method you want to explain.
And, don't say "we can find", but say what exactly *how* is to be done.

[Visu]

Originally Posted by m_f_h

somewhat more precision is needed in mathematics.

Agreed I will make the changes in the next draft.

Originally Posted by m_f_h

As remarked, if N is a difference of 2 squares >0, it's trivially composite, N=(a-b)(a+b).

Nope. A prime can also be expressed as a difference of 2 squares.
4^2 - 3^2 = 7. But a composite number can be expressed as a difference of 2 squares in more ways depending on the number of factors it has. For example the semi-prime 21 can be expressed as 11^2 - 10^2 and 5^2 - 2^2.If the number has 3 factors there are 3 such representations and so on.

Originally Posted by m_f_h

Thus, if N is not composite, you can NOT find a d_k in the list
d_k = (a+k)^2-N

This clearly shows that the 3rd phrase of your document,
"...so that we can find (a1 + n)^2 – (N) = dn where dn is a square number."

is WRONG.
Thus, there is no "Next,..." possible, from that point on, since it is never reached.

Again I disagree. Lets say N = 97 a small prime

Ceiling(sqrt[97]) = 10

10^2 - 97 = 3
11^2 - 97 = 24
12^2 - 97 = 47

Finding d_k is not dependent on N being composite

Originally Posted by m_f_h

You also say
"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."
But then, in the example, you use again alpertron's QUAD.HTM.

All of this does not make sense.

I used Alpertron's algorithm to show that there where 2 sets of solutions for a semiprime one trivial and one requiring factorization to find. If you read carefully you will notice that I do not use the results again in any of my subsequent arguements.

Originally Posted by m_f_h

As a final note, you don't need to spend years on learning a programming language or on programming. If you have a clear "method", this means "algorithm", and you just can write it in English:
Given N, let a = floor( sqrt( N )), d_k = (a+k)^2-N for k=1,2,3
Let ... ; If ... then ... ; etc.

Or at least, develop 2 or 3 significant examples "by hand" from the start to the end, without saying "we could... but we want to avoid...": Just use the method and only the method you want to explain.
And, don't say "we can find", but say what exactly *how* is to be done.

Again agreed.Firstly I included the "dead ends" or the methods we wish to avoid because I reproduced what was in my notes without much editing.I will remove them from my subsequent drafts. I am also working on the pseudocode implementation as you have suggested. Thanks for your input.Its appreciated.

[Visu]

Originally Posted by Visu

Nope. A prime can also be expressed as a difference of 2 squares.
4^2 - 3^2 = 7. But a composite number can be expressed as a difference of 2 squares in more ways depending on the number of factors it has. For example the semi-prime 21 can be expressed as 11^2 - 10^2 and 5^2 - 2^2.If the number has 3 factors there are 3 such representations and so on.

This idea is crucial to the whole method.We can easily find the trivial representation(eg. for N = 21, 11^2 - 10^2 is the trivial representation) but to find the non-trivial representation (5^2 - 2^2) requires factorisation. But we use the trivial representation as our first rational point (it also happens to be an integer point) on the conic section.Once we have one rational point we just need to ensure that the gradient from that point to another point is rational so that the second point is also rational.Selecting the gradients and identifying the integer point amongst the many rational points forms the rest of the argument.

[R.D. Silverman]

Originally Posted by Visu

This idea is crucial to the whole method.We can easily find the trivial representation(eg. for N = 21, 11^2 - 10^2 is the trivial representation) but to find the non-trivial representation (5^2 - 2^2) requires factorisation. But we use the trivial representation as our first rational point (it also happens to be an integer point) on the conic section.Once we have one rational point we just need to ensure that the gradient from that point to another point is rational so that the second point is also rational.Selecting the gradients and identifying the integer point amongst the many rational points forms the rest of the argument.

You are mixing concepts from two separate topologies.
When you talk about "gradient", you are working in R^2. When you
talk about rational points, you are working in Q^2. One can represent the
conic sections for which you are seeking rational points as a scheme.
Factoring now becomes the problem of separating two rings within that scheme.

However, the concept of "gradient" does not apply in that scheme.
A gradient based descent algorithm does not work in the discrete topology.

This is all moot, however, since difference-of-squares methods are
purely exponential; Trying to invent a "new & improved" difference of
squares method is just trying to reinvent a square wheel.

[Visu]

Originally Posted by R.D. Silverman

You are mixing concepts from two separate topologies.
When you talk about "gradient", you are working in R^2. When you
talk about rational points, you are working in Q^2. One can represent the
conic sections for which you are seeking rational points as a scheme.
Factoring now becomes the problem of separating two rings within that scheme.

When I am talking about a gradient between 2 rational points I will still be working in Q^2,right?

Originally Posted by R.D. Silverman

However, the concept of "gradient" does not apply in that scheme.
A gradient based descent algorithm does not work in the discrete topology.

Two points to clarify here. Firstly I am finding points on a conic section which by itself is not discrete. Secondly and I have repeated this many times I am not using a descent algorithm or an iterative procedure. I will follow m f h's advise and write out a few more examples outlining just the steps. Maybe it will be clearer.

Originally Posted by R.D. Silverman

This is all moot, however, since difference-of-squares methods are
purely exponential; Trying to invent a "new & improved" difference of
squares method is just trying to reinvent a square wheel.

I agree and disagree.All difference of square methods up to now have been iterative and thus exponential.Mine as I have said before is not an iterative process. I am trying to round the edges off of the square to make it circular.