Page "Lenstra elliptic curve factorization" Paragraph 5

< li > We will compute certain multiples ( k times ) of the point P using the standard addition rule on our elliptic curve: given two points P, Q on the curve, their sum can be computed using the formulas given in the group law section of the article on elliptic curves.

These formulas contain the " slope " of the line connecting P and Q, hence involve divisions between residue classes modulo n, which can be performed using the extended Euclidean algorithm.

In particular, division by some v ( mod n ) includes the calculation of the greatest common divisor gcd ( v, n ).