I Composite Number Test: Find Factors w/ Quadratic Equations

[rajeshmarndi]

All composite number comprised of atleast two factor e.g

57 = 3 * 19 and 1 * 57
14927= 11*1357 = 23*649 = 59*253 = 1*14927

We can get to know 57 is a composite number , as the factor 3*19 is achieved, as below, from 11^2. The first factor reduces and the 2nd factor increases, till first factor is 1.

11*11=121
9*13=117
7*15=105
5*17=85
3*19=57
1*21=21

Note all these composite no. that descend from 11^2 are square distance from 11^2 as below.

121-117=4= 2^2
121-105=16 = 4^2
121-85=36 = 6^2
121-57=64 = 8^2
121-21= 100 = 10^2

Note 1*21 factor has always a difference of 1, here, 11-10=1 (i.e of 11^2 & 10^2). So it can always be eliminated.This is true for all composite number. So, each Composite number has a specific square(higher than the test number N) from where it descend, like in the above example.So to find whether a number N is a composite or not. One only need to see if any of the higher squares are square distance to N.
Say a test number N=1656337 . Square next to it is , integer(√N)+ 1

which is,
= integer (√1656337) ) + 1 = integer ( 1286.987...) ) + 1 = 1286 + 1 = 1287.

So, square next to N is 1287^2.
We can formulate distances to next squares which will be quadratic in nature. For the above number N, it will be,

x^2 + 1287*2*x + (1287^2-N)

(this is the distances to all the higher square to N. Starting with x=0)

x^2 + 2574x + 32 = m^2 ?

So, if the above quadratic expression generates an perfect square (integer). Then N is a composite number. Remember 1*N also comes under a specific squares, so every such equation will definitely have one solution for 1*N factor.

So we need to see if the quadratic expression generates atleast two solution. If yes then definitely N is a composite number.
But I am not able to determine, how to say such a quadratic will generate perfect squares or not.For the above test number N. Since I know 1656337 is a composite number and 1217 and 1361 are its factor.

In that case, we can find the squares where its distance comes to be a square.
(1217 + 1361) /2 = 1289

So we get from 1289^2, 1217*1361 has descended.

so, 1289^2 - 1656337 = 72^2

i.e

x^2 + 2574x + 32 = 72^2
so we definitely get at x=2 the quadratic is a perfect square

Similarly for factor 1*1656337, it always descend from

integer(1656337/2) + 1 = integer(828168.5)+1 = 828168+1 = 828169 square

i.e
x^2 + 2574x + 32 = 828169^2
and x for this, will always be

x= [(1287-1)^2 - 32 ] / 2 = 826882

So,
x^2 + 2574x + 32 = m^2
has two solution.

i.e N(1656337) has two square at x= 2 & x = 826882 and therefore is a composite number.
Please comment.
Thank you.

 

[mfb]

This is true for all composite number. So, each Composite number has a specific square(higher than the test number N) from where it descend, like in the above example.

Try to find a square for 6=2*3. It does not work for even numbers (although it is trivial to find a prime factor for them).

One only need to see if any of the higher squares are square distance to N.

This is much more work than the usual tests if a number is prime.

With a good algorithm, your home computer can check if a 50-digit number is prime in seconds, and find the factors in seconds to minutes. Example script.
4564534346464575453645453857398573985358375558353521
= 132985692076982233761143 * 34323499582363159679580258647 - found in 2 seconds.

With the square numbers, it would have to run for years to millenia. Your approach doesn't look wrong, but it does not help.

 

[rajeshmarndi]

With the square numbers, it would have to run for years to millenia. Your approach doesn't look wrong, but it does not help.

x^2 + 2574x + 32 = m^2 ?
Is it really, difficult (or no way), to determine ,if quadratic like above, can generate perfect square or not. I had an impression, it can be solved just like any other equation.

 

[mfb]

Try the example of 4564534346464575453645453857398573985358375558353521.

It is not sufficient to find any larger square, you have to express the number as difference of two squares. And finding that via trial and error is not feasible - it is equivalent to check all possible factors. Squares are rare if the numbers are that large.

 

[rajeshmarndi]

And finding that via trial and error is not feasible -

Why do you say to solve x^2 + 2574x + 32 = m^2 ?
it has to be via trial and error.

 

[mfb]

Despite centuries of searches, no one found a method that does not involve a lot of trial and error (for large numbers), or uses the opposite direction (find the primes first, then reconstruct the difference of squares if you are interested in it).
Such a method would revolutionize cryptography. It would also come with a reasonable prize money (that one expired but I think there are follow-up prizes).

It is easy with 4-digit numbers such as yours, because it involves just a few thousand attempts in the worst case. A computer can do that in a millisecond. A computer cannot do 10⁵⁰ attempts - and that is the range where prime factorization gets interesting.

 

[micromass]

x^2 + 2574x + 32 = m^2 ?
Is it really, difficult (or no way), to determine ,if quadratic like above, can generate perfect square or not. I had an impression, it can be solved just like any other equation.

Come on, I have solved various questions of this type for you already. We won't keep spoonfeeding you the answer. So you should start by showing us some work.