1. Limited time only! Sign up for a free 30min personal 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!

I Compositeness test

  1. Sep 11, 2016 #1
    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.
     
  2. jcsd
  3. Sep 11, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
    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.
     
  4. Sep 11, 2016 #3
    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.
     
  5. Sep 11, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  6. Sep 11, 2016 #5
    Why do you say to solve x^2 + 2574x + 32 = m^2 ???
    it has to be via trial and error.
     
  7. Sep 11, 2016 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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 1050 attempts - and that is the range where prime factorization gets interesting.
     
  8. Sep 12, 2016 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Compositeness test
  1. Composite functions (Replies: 3)

  2. Composite function (Replies: 18)

Loading...