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.