Why can basic ECM find a factor with a smaller prime-power multiplier than expected? To improve my understanding of ECM, I am implementing Lenstra's method in Python, following algorithm 7.4.2 in Prime Numbers by Crandall and Pomerance. I'm testing it using composites of known factorisation p1 × p2. According to their discussion on p337, finding a factor p by means of an illegal elliptic operation is expected when the multiplier k is divisible by the order #E(F p). In a test example 11401499 = 3691 × 3089, the curve has a = 2841733, b = 10999747, and on this curve the order for 3691 is 2×7×263 and the order for 3089 is 2×2×2×2×3×5×13. Accordingly, the factor 3089 should be found with B1 = 16, which does happen. But it is found when the multiplier k is calculated for primes up to 11, when k = 55440 = 2×2×2×2×3×3×5×7×11. Why doesn't the calculation of k have to be continued up to prime 13 in this example, before the illegal operation occurs?
 A: The answer relates to the addition-subtraction ladder in C and P's elliptic multiplication algorithm 7.2.4.
It calculates [11]P by P → [2]P → [4]P → [3]P → [6]P → [12]P → [11]P.
It calculates [13]P by P → [2]P → [4]P → [3]P → [6]P → [12]P → [13]P.
In C and P's elliptic addition algorithm 7.2.2, add(Q,P) and sub(Q,P) will both need to invert (x2 - x1), which are the same for add(Q,P) and add(Q,-P). So when the ECM algorithm is expected to get the illegal operation on prime 13 when [12]P → [13]P, this actually happens on prime 11 when [12]P → [11]P. 
A: My previous answer is not the whole story, however, as it doesn't explain another example. For 568861 = 619 × 919, the curve has a = 101512, b = 172778, and on this curve the order for 619 is 23×34 and the order for 919 is 24×59. Accordingly, the factor 919 should be found with B1 = 59. But instead it finds factor 619 when the multiplier k is calculated for primes up to 5, when k = 4320 = 25×33×5. The illegal operation occurs on the addition [25×33×4]P + [25×33]P.
(Added later) This is, in fact, explained by the addition-subtraction ladder. An illegal operation would occur on the subtraction [25×33×4]P - [25×33]P, since this would be [25×33×3]P, with k now a multiple of the order for 619. As mentioned in my previous answer, the same illegal operation can occur whether a term is added or subtracted, so it occurs on the above addition.
