Reading several texts of ECM (e.g. 20 years of ECM) the Stage 1 is described as:

$Q \leftarrow P_0$
for each prime $\pi <= B_1$
$\quad$compute $k$ such that $\pi^k <= B_1 < \pi^{k+1}$
$\quad$for $i$ := to $k$ do
$\quad\quad Q \leftarrow \pi \cdot Q$

For $Q =(x_Q: :z_Q)$ (Montgomery), sometimes that $z_Q$ becomes zero and so all the subsequent multiplications result in $(0: :0)$.

My question is, should I check for GCD after every multiplication because it might reveal a factor? It also could be that I don't understand the description fully and should be detecting the first occurrence of zero but none of the implementations I saw does this? If the zero should be happening, what is the correct way of handling it? Let it simply slip to Stage 2?

up vote 2 down vote accepted

The idea is if a factor $p$ can be found at a particular step, then $p$ would divide $z$ for the rest of the run. So it will always "be there". That means you can still potentially find it at end of stage 1. So you can opt to do just one gcd at that point.

There are advantages and disadvantages of this method.

The advantage of doing this is clearly saving some operations of gcd. The disadvantage is that if multiple factors can be found, not doing intermediate gcd means you lose the chance to split them. In some cases this would mean a failed run, if you found all of the factors at end of stage one. (From there on you cannot split it anymore since $x,z$ would just be $\equiv 0 \pmod N$.) Perhaps an intermediate gcd could have split it.

In some cases perhaps finding a factor as soon as you can may help, in which case more gcds are good. Perhaps once you find one you can terminate. Or you can reduce the modulus from $N$ to $N/d$ to make computations cheaper (maybe less likely if you are using montgomery multiplications).

So: if factors are expected to be uncommon, it suffices to just do one gcd at end of stage 1. If factors are common, it may be useful to do several intermediate gcds to extract them.


Edit 1: If a factor $d<N$ is found, you compute $N' =N/d$ and work in $\pmod {N'}$ from there on.

  • Thank you for the answer! But my problem is slightly different: it can happen that after few multiplications $Q$ becomes $(0::0)$, therefore after using all the primes it ends up also $(0::0)$. Are you saying that this happens because it found all the factors? Because after it finishes all I have is GCD($n$, 0). – minmax Sep 14 at 14:39
  • @minmax Yes, if $z\equiv 0\pmod n$ it means you found all the factors, and for the rest of the run it will remain so. Intermediate gcds might be able to split it, or you can simply try another curve. – Yong Hao Ng Sep 14 at 14:46
  • @minmax In particular, whenever you found all the factors it's the end and there's nothing else to do. $x,z$ will always remain $\equiv 0\pmod n$ from that point onwards so you cannot get factors via $\gcd$. – Yong Hao Ng Sep 14 at 14:52

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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