Results 1 to 2 of 2

Math Help - Cryptography -- Pollard p-1 Algorithm in Mathematica

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    9

    Cryptography -- Pollard p-1 Algorithm in Mathematica

    Hi, I've got a weird problem here. I'm trying to implement the Pollard P-1 algorithm in Mathematica, which my textbook states is guaranteed to work for B = \sqrt{n}, but in this particular example, if B gets too large, say, equal to 500, which is about the square root of the number in consideration, the algorithm actually stops working. My instructor and I looked at it for a long time and decided it's correct rendering of Douglas Stinson's pseudo-code from Cryptography: Theory and Practice... so what's going on? I've found it works for B ranging from 14 to 251, but no larger.

    n = 262063;
    B = 251; (* Largest B that works *)
    a = 2;

    For[i = 2, i < B, i++,
    a = PowerMod[a, i, n];
    ]

    d1 = GCD[a - 1, n];

    If[
    1 < d1 && d1 < n,
    Print["d is " <> ToString[d1] <> " and n/d is " <> ToString[n/d1]],
    Print["Fail"]
    ]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2011
    Posts
    3

    Pollard rho-1

    This is because, in the For loop, you extract the two factors, and what is detected as a factor is n.
    This is why, in the Pollard method, one must do the divide GCD check often enough.
    You may extent the multiplys at least until B=sqrt(n), but you must check, for numbers like yours every 50's or 100's. If you do not find after the first 100, then continue for another 100.
    See Hans Riesel book, prime numbers and computer methods for factorization for more details.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Tenenbaum and Pollard, Problem 2.10.6
    Posted in the Differential Equations Forum
    Replies: 10
    Last Post: March 4th 2011, 06:27 PM
  2. Pollard p-1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2009, 08:09 PM
  3. Pollard rho algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: November 26th 2009, 08:37 PM
  4. Pollard Rho Algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: November 10th 2009, 11:17 AM
  5. cryptography help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 21st 2008, 07:25 AM

Search Tags


/mathhelpforum @mathhelpforum