Why can basic ECM find a factor with a smaller prime-power multiplier than expected?

Question

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?

Answer 1

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.

Answer 2

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 2³×3⁴ and the order for 919 is 2⁴×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 = 2⁵×3³×5. The illegal operation occurs on the addition [2⁵×3³×4]P + [2⁵×3³]P.

(Added later) This is, in fact, explained by the addition-subtraction ladder. An illegal operation would occur on the subtraction [2⁵×3³×4]P - [2⁵×3³]P, since this would be [2⁵×3³×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.