Results 1 to 6 of 6

Math Help - Odd semi-prime challenge

  1. #1
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Odd semi-prime challenge

    Let n=p*q (p and q are odd prime). Let a mod(p)=(q-p). The numbers a and n are known. Can you find p and q? Thank you.
    Last edited by Mouhaha; March 3rd 2013 at 09:28 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Nehushtan's Avatar
    Joined
    Mar 2013
    From
    Europe
    Posts
    42
    Thanks
    12

    Re: Odd semi-prime challenge

    Umm if n is known, then surely its prime factors are also known?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Odd semi-prime challenge

    Quote Originally Posted by Mouhaha View Post
    Let n=p*q (p and q are odd prime). Let a mod(p)=(q-p). The numbers a and n are known. Can you find p and q? Thank you.
    1 ) For the special case of a < p < q, we have a mod (p) = a = q-p from which one gets q = p + a. We then have the relation n = p x q = p x (p + a) = p^2 + ap........Subtracting n from both sides gives us
    p^2 + ap - n = 0, which is a quadratic equation in terms of "p". Since the discriminant is a^2 + 4n > 0, this will have a solution via the quadratic equation.

    Now this case assumes that a < p. Hence if our given "a" is small enough, we can just check all the prime numbers 2,3,5......that are < a. If we find a prime factor first, then as Nehushtan points out, were already done but if not, we can solve this easily via the quadratic formula above as our initial assumption will have been justified.....


    2) FOR GENERAL CASE (ie "a" is too large to be efficiently solved as described above), we have a - kp = q - p for some "unknown" integer k and we have q = a + (k-1)p..........Following along the same lines as before, we get (k-1)p^2 + ap - n = 0.........Since we do not know what "k-1" is we cannot solve directly via quadratic formula, however because we know that "p" is an integer, it follows that a^2 + 4 x (k-1) x n is a square...........From here I'm not sure of any method other than a "brute force" approach that will efficiently solve for p.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Odd semi-prime challenge

    Quote Originally Posted by Nehushtan View Post
    Umm if n is known, then surely its prime factors are also known?
    On the surface of things, this would be an inefficient method since factorization is slow. With that said, since q-p = a mod (p) < p, we have that q < 2p. However we also have p < q, since "a mod(p)" is by definition positive. Since p < q < 2p, this question could likely be solved very quickly via the "Fermat factoring algorithm" for large n!

    Fermat's factorization method - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Odd semi-prime challenge

    Here is an example :

    n=7313

    a=955

    We have to solve the following equation :

    955 mod(p)=q-p

    It is easy to factorize n in this case.

    n=7313=71*103

    955 mod 71 = 32

    q-p=103-71=32

    But if n is 400 digit-number it will be a headache.

    What is the added information that we need to solve it even if n is a huge number?

    I assume that I have found a mathematical way to find the number a.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Odd semi-prime challenge

    If a^2 < n / 2, then a < p (where p is the smaller prime factor of n) and the problem can be solved via the quadratic formula.

    I don't know how it can be solved more generally, but as the p < q < 2p, the problem does make using the "Fermat factoring method" of n more desirable (keep in mind that for a 400-digit number, this method will still be inefficient).

    I assume that I have found a mathematical way to find the number a.
    That would be quite the discovery! However keep in mind that the condition "a mod(p) = q-p" would rarely hold for most composites that are the product of two primes.
    Last edited by jamix; March 3rd 2013 at 06:48 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: January 9th 2013, 08:35 PM
  2. finding first n semi-prime integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 27th 2012, 07:51 PM
  3. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  4. semi-metric spaces and qausi-semi developable
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 18th 2011, 02:38 AM
  5. Replies: 1
    Last Post: June 19th 2011, 01:56 PM

Search Tags


/mathhelpforum @mathhelpforum