Results 1 to 7 of 7

Math Help - Rsa-704

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    Rsa-704

    Ok as some of you know, this number:

    74037563479561712828046796097429573142593188889231
    28908493623263897276503402826627689199641962511784
    39958943305021275853701189680982867331732731089309
    00552505116877063299072396380786710086096962537934
    650563796359

    has two prime factors and RSA will give $30,000 to the person/team who can find them.

    Who here knows some basic number theory on this problem and why it is so hard to factor?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,824
    Thanks
    318
    Awards
    1
    Quote Originally Posted by Jameson View Post
    Ok as some of you know, this number:

    74037563479561712828046796097429573142593188889231
    28908493623263897276503402826627689199641962511784
    39958943305021275853701189680982867331732731089309
    00552505116877063299072396380786710086096962537934
    650563796359

    has two prime factors and RSA will give $30,000 to the person/team who can find them.

    Who here knows some basic number theory on this problem and why it is so hard to factor?
    It's not divisible by 2, 3, or 5. Okay, I've done my part.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    It's hard because it doesn't fit in most calculators
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Ummm, thanks guys. I suppose.

    Obviously this number is semi-prime, and it's only factors besides 1 and itself are p_1 and p_2. So I think it's safe to say 2,3, and 5 are out, as well as any other prime less than 100 digits.

    Any ideas?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Jameson View Post
    Ummm, thanks guys. I suppose.

    Obviously this number is semi-prime, and it's only factors besides 1 and itself are p_1 and p_2. So I think it's safe to say 2,3, and 5 are out, as well as any other prime less than 100 digits.

    Any ideas?
    At least you don't have to look farther than the sqrt of the number, which in this case is 8.60450832 10^105
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Well I had hoped to get some serious thoughts on this, but c'est la vie. Thread closed.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Umm, I will first try Fermat's Factorization Method, find the smallest square exceeding this and keep subtracting this number. (But this is only useful when the two factors are adjacent).

    You can also try the Pollard pho primality test. But I am not too familar with it, in fact, I am not familar too well with primality testing.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum