2
$\begingroup$

I am trying to use the Pollard $p-1$ method to find the factors of a large integer. Here is the problem:

An RSA-type cipher is based on the integer $n = 140016480344628383$ and exponent $2345671$. Factor n into a product of two primes, $p$ and $q$, using the Pollard $p-1$ method with base 2.

Once you have found $p$ and $q$, find the decryption index $d$ satisfying $de \equiv1\, ({\rm mod}\,(p-1)(q-1))$

None of my code is working. I can't seem to get it setup without having an overflow. Any tips and pointers would be so appreciated!

Here was one of my code attempts:

n = 140016480344628383;
b = 2;
y = 0;
z = 0;
ls = {};
p = 0;
For[k = 0, k <= 1500, k++,
  y = Mod[b^k!, n];
  b^k != Mod[y*(y - 1), n];
  z = y - 1;
  p = GCD[z, n];
  If[GCD[z, n] > 1, ls = Append[ls, p]];
];
$\endgroup$
  • $\begingroup$ Welcome to Mathematica.SE! I suggest that: 1) You take the introductory Tour now! 2) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! 3) As you receive help, try to give it too, by answering questions in your area of expertise. $\endgroup$ – bbgodfrey May 8 '15 at 1:24
  • $\begingroup$ Please add your code to the question, so that readers can help you with it. $\endgroup$ – bbgodfrey May 8 '15 at 1:28
  • 1
    $\begingroup$ Per Wikipedia: In[109]:= n = 140016480344628383; b = 2000; mbig = Product[Prime[j]^Floor[Log[Prime[j], b]], {j, PrimePi[b]}]; g = PowerMod[2, mbig, n]; GCD[g - 1, n] Out[113]= 373607131 $\endgroup$ – Daniel Lichtblau May 8 '15 at 3:08
3
$\begingroup$

Essentially all you need to get your code to terminate is

  • Convert Mod[b^k!, n] to PowerMod[b, k!, n] (b^k! caused the overflow).
  • Break out of your loop once p has been found.

Here's your code with these slight modifications. (I also added Monitor to see the progress.)

n = 140016480344628383;
b = 2;
y = 0;
z = 0;
p = 0;

Monitor[
  For[k = 0, k <= 15000, k++,
    y = PowerMod[b, k!, n];
    z = y - 1;
    p = GCD[z, n];
    If[p > 1, Return[p]];
  ], k
]
 373607131

Finally we can verify to make sure everything went smoothly.

FactorInteger[140016480344628383]
{{373607131, 1}, {374769293, 1}}

Edit: I think there still might be a problem in your code. What is the line

b^k != Mod[y*(y - 1), n];

supposed to do? The way you have it, whether it's True or False, it doesn't effect evaluation.

Edit 2: I have removed that line from the code after getting clarification in the comments section.

$\endgroup$
  • $\begingroup$ Wow, thank you SO much! You have saved me hours of staring at my computer. Thank you. $\endgroup$ – Nora May 8 '15 at 1:53
  • $\begingroup$ @Nora see my edit, what is b^k != Mod[y*(y - 1), n]; supposed to do? $\endgroup$ – Chip Hurst May 8 '15 at 1:54
  • $\begingroup$ Here is my now updated code: e = 2345671; n = 140016480344628383; b = 2; y = 0; z = 0; p = 0; Monitor[ For[k = 0, k <= 15000, k++, y = PowerMod[b, k!, n]; b^k = Mod[y*(y - 1), n]; z = y - 1; p = GCD[z, n]; If[GCD[z, n] > 1, Return[p]];], k] $\endgroup$ – Nora May 8 '15 at 1:59
  • $\begingroup$ @Nora I'm still confused. You can't assign b^k a value. Can you say in words what that line is supposed to do? $\endgroup$ – Chip Hurst May 8 '15 at 2:01
  • $\begingroup$ The b^k != Mod[y*(y - 1), n]; is my attempt at computing b^(k+1)! without overflow. where b is 2 and k is the iterations. That line is now not even needed in the code. It now works correctly and I was able to verify it with the FactorInteger command! $\endgroup$ – Nora May 8 '15 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.