Stage 1 of Elliptic Curve Method (ECM)

107 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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.