Results 1 to 6 of 6

Math Help - prime factors

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    98

    prime factors

    Suppose you know n = 1141367 is a product of two primes. A cryptographer is
    able to tell you that = 1136856. Find the two prime factors of n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2008
    Posts
    98
    I think this might be a Euler's theorem problem? Any ideas??
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by bigb View Post
    I think this might be a Euler's theorem problem? Any ideas??
    actually, it is an RSA problem

    let the primes be p and q

    note that \phi = (p - 1)(q - 1)

    and remember you have pq = n \implies p = \frac nq
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    \varphi (n) = \varphi (p_{1} \cdot p_{2}) = \varphi(p_{1}) \cdot \varphi (p_{2}) = (p_{1} - 1)(p_{2} - 1)

    So: (p_{1} - 1)(p_{2} - 1) = 1136856

    But since: n = p_{1}p_{2} \ \Rightarrow \ p_{2} = \frac{n}{p_{1}}

    We have that: (p_{1}-1)\left(\frac{n}{p_{1}} - 1\right) = 1136856

    Should be easy from here.

    AH beaten
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by o_O View Post
    AH beaten
    that's right! Mr. o_O!

    oh! i see, bigb was referring to the Euler-Phi function. ok. never heard it called theorem before
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2008
    Posts
    98
    nvm i got it...sry
    Last edited by bigb; September 30th 2008 at 11:42 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 28th 2010, 07:43 AM
  2. Prime factors
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 20th 2010, 05:57 AM
  3. Replies: 1
    Last Post: December 7th 2009, 11:42 AM
  4. prime factors
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 24th 2008, 03:17 AM
  5. prime factors
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 26th 2007, 01:19 PM

Search Tags


/mathhelpforum @mathhelpforum