Results 1 to 9 of 9

Math Help - Sum and product of factors of a semiprime

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Post Sum and product of factors of a semiprime

    Hi all, I'm new on this forum (it is great )

    I have a maybe-hard maybe-easy question, which is the following (I have worked quite a lot on it but can't find a way around it) :

    Say n = pq, with p and q [non-trivial] primes (so n is semiprime)
    Now say m = p + q (same values of p and q obviously)

    I know "n", but I need "m" (I don't know p or q). Is there a way around this, or is it just impossible ? Isn't there some kind of relation between the product and the sum of the factors of any semiprime ?

    Regards.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bacterius View Post
    Hi all, I'm new on this forum (it is great )

    I have a maybe-hard maybe-easy question, which is the following (I have worked quite a lot on it but can't find a way around it) :

    Say n = pq, with p and q [non-trivial] primes (so n is semiprime)
    Now say m = p + q (same values of p and q obviously)

    I know "n", but I need "m" (I don't know p or q). Is there a way around this, or is it just impossible ? Isn't there some kind of relation between the product and the sum of the factors of any semiprime ?

    Regards.

    I wouldn't say "impossible" but as close to it as you can imagine, in particular if the number n is big, and it must be big if you can't find more or less easily its two prime divisors, EVEN after being said it only has two!
    This is the reason why we can have some security when paying, working and having fun with a computer: some codes are based precisely in that (for example, the Public one): you can know the number n, but only the receiver of a message knows its prime divisors.
    Just for fun, find the prime divisors of 251646847 (i - this is a product of two primes, ii -don't even dream in trying to find a prime that divides this number by hand, lest you'll get a severe hand-and-brain tiredness)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    If you knew m, then you could just solve the quadratic equation x^2-mx+n=0 to get p and q. Solving a quadratic is very easy, so finding m is definitely as difficult as finding the two factors p and q from just n.
    Last edited by Bruno J.; November 4th 2009 at 10:17 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Oh I see. Well ... that's too bad because I was actually trying to avoid factorization

    PS : Tonio, 251646847 = 9697 x 25951 on a basic quadratic sieve (no matrix, just the sieving) that I did for fun. But thanks for the info.

    But anyway, isn't there a way mathematically to express that a number is square ? Example, if I know that (x - 84) for example gives a square for 2 values only ? I can find the first one easily (x = 84/4 + 1), but the second one is x = 10 but I can't make an equation to find both solutions cleanly.
    Last edited by Bacterius; November 4th 2009 at 11:02 AM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    I can find another integer solution, namely 22^2-84=20^2, and infinitely many rational solutions, for example (19/2)^2-84=(5/2)^2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Reply

    Well I knew the 22, since 84/4 + 1 = 22. And I'm only considering perfect squares. There is x = 10 too, since 100 - 84 = 16. But how can I mathematically find the 10 ? (since the 22 is a trivial solution)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    I wrote x^2-84=y^2, and factored it as (x-y)(x+y)=84. Now if you factor 84 as 84=AB, and set x-y=A, x+y=B, you'll find that x,y are integers if and only if both A,B are even or both are odd. Clearly both cannot be odd, and the only way for both to be even is to have A=2, B=42, or A=14, B=6. If you then solve for x=(A+B)/2,y=(A-B)/2 you will find the two solutions (10,4),(22,20).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Reply

    But you still get to factorize 84, so the whole point is lost.
    So does this show that factorization is necessary to solve this type of problem ? But factorizing the sum of the two prime factors wouldn't it be easier than factorizing the semiprime itself (since the sum is obviously a lot smaller and even) ? There might be a way around this ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Reply

    Ok I'll try to explain this as well as I can :
    I have a function :

    f(x) = x^2 - 4n

    Where n is a known constant.

    Is there a "quick" way to find the two distinct values of x when f(x) is a perfect square ?

    I can find one easily : if you let x = (n + 1), then you get :

    f(n + 1) = (n + 1)^2 - 4n
    f(n + 1) = n^2 + 2n + 1 - 4n
    f(n + 1) = n^2 - 2n + 1
    f(n + 1) = (n - 1)^2

    Which obviously is a square. The problem is, this solution is somewhat trivial, and there is only one other solution which is non-trivial and that I need, but I can't find an algebraic way to solve it ...
    Last edited by Bacterius; November 6th 2009 at 03:53 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Lemma of Semiprime Ring
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2011, 05:29 PM
  2. A semiprime proof
    Posted in the Math Challenge Problems Forum
    Replies: 6
    Last Post: November 30th 2009, 03:51 AM
  3. Express as the product of four factors
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 23rd 2009, 01:49 PM
  4. solving as a product of two factors
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 21st 2009, 04:25 PM
  5. product of linear factors
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 4th 2008, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum