Results 1 to 3 of 3

Math Help - RSA, factoring N

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    55

    RSA, factoring N

    I have an assignment to factor a 160 digit number on the form p*q, where p and q are primes. The number is N in RSA. I also got e, which is also about 160 digits, and the fact that d is much much smaller than e. I assume the latter information was given because we need to use it to factor N in reasonable time, but I can't figure out how to do this.

    All I know is that e*d = 1 mod (p-1)(q-1). Can't seem to find a way to calculate neither d nor p or q, since there's too many unknown in the equation.

    Any help would be very appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    Any thoughts anyone?

    Facts:
    - d is much much smaller than e.
    - Can't factorize N with any factorization algorithm.
    - N and e given.

    How do I do?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    216
    Thanks
    29
    I think that there is a conjecture to the effect that any method of beating RSA is equivalent to factoring N? Thus making your assignment impossible. Unless you have the required computer power to factorise N.

    Perhaps this paper might be interesting.
    Breaking RSA may not be equivalent to factoring

    I have not read it.

    If your tutor has given you an answer, then please post it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. need help with factoring
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 7th 2010, 11:47 AM
  2. factoring help
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 4th 2010, 08:44 PM
  3. Is this factoring or something?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 1st 2010, 07:54 PM
  4. Replies: 2
    Last Post: August 22nd 2009, 11:57 AM
  5. Replies: 3
    Last Post: November 6th 2006, 12:02 AM

Search Tags


/mathhelpforum @mathhelpforum