This week I tried implementing the Elliptic Curve Method of Factorization. I spent most of the time trying to understand how the algorithm works, and going through existing implementations (GMP-ECM and pyECM). After spending quite some time, I decided to stick to the Montgomery elliptic curve coordinates for the stage I of the ECM. The reason was that scalar multiplication turns out to be faster when using Montgomery coordinates (no inversions required) and selection of the curve is quite easy (Suyama parameterisation).
Code this week
This week I implemented not so optimised versions of :
- Addition of two points on an EC
- Doubling of two points on an EC
- Scalar Multiplication (Montgomery Ladder)
- Selection of a random curve (Suyama Parameterization)
- Stage I ECM
Currently Scalar Multiplication is carried out by the Montgomery Ladder algorithm. However I would like to try Montgomery's PRAC algorithm. It uses addition subtraction Lucas chains, and turns out to be faster than the Montgomery Ladder. But this would be done once I am done with a stage II implementation.
Although I haven't timed the current stage I implementation properly, I did try to factor the 7th Fermat Number 340282366920938463463374607431768211457. Stage I ECM found the factor 59649589127497217 in 20.713978 seconds (B1 = 10000). Although this is better than the Pollard Rho function, it is still really slow. It is probably due to the fact that the B1 I am using is very large. Stage II would make this factorization faster.
This week, I would understand the ECM stage II algorithm, and implement it. This will be a simple implementation using the fmpz module. If I manage to complete it before the end of the week, I would work on the PRAC algorithm for speeding up scalar multiplication.