Since I've missed out on some blog posts the last couple of weeks, I'll be summing up the stuff I've been up to in this post. The past month hasn't really been as productive as I would have wished, the reason being some wrong assumptions I made. I'll be giving week wise summary below.
13th July - 19th July
This week I started reading the existing SIQS code, which I pulled from Nitin's SIQS branch. I took me some time to understand the existing code, and where exactly I would start working to add the double large prime version.
While reading the code, I also found a small bug in the code. In the qsieve_evaluate_candidate() function, all powers of 2 were being removed before the Knuth Schroeppel multiplier is removed from the relation. This would have slowed down factorisations in which the knuth schroeppel multiplier was even.
An issue was reported this week, concerning one of the functions I had written earlier (#150). I spent some time reading the n_cbrt() code, and noticed that I had made a terrible mistake earlier. I had assigned wrong constants, which would have definitely caused overflows in 32 bit systems. Although this did not solve the issue reported, it was definitely something which would have caused problems. I never noticed it earlier on as I never tested the code on a 32 bit machine.
20th July - 26th July
This week I started coding the double large prime version. I was using Factoring with two large primes, A. K. Lenstra and M. S. Manasse as a reference. I started by reducing the cut off limit in qsieve_evaluate_sieve() to produce more partials and pp relations. Once I got these relations, I used n_factor() and n_isprime() in qsieve_evaluate_candidate() to check whether the remainder after pulling out the factor base primes is a prime / semi prime. If so, I wrote them to a file of the format [type, number of factor base primes that divide it, factor base prime's index, factor base prime's exponent, large prime I, large prime II]. In case of a partial, the large prime II was simply 1.
Here is when I started to face problems. I simply couldn't manage to produce a lot of partials and pp's. I tried to explore the code and check whether I was making any mistake, but couldn't figure out what to do to fix it. At this point I should have switched over to the tested FLINT2 code, and extend it to a a double prime version, however I was under the impression that an SIQS was required before I could add a double large prime version. This was a wrong assumption I made.
27th July - 2nd August
I couldn't really do a lot this week, I had refresher modules and exams throughout the week at my institute (they take place before the beginning of the semester).
I did some minor work towards the FLINT 2.5 release this week. There was an issue #32 reported some time back. It was required to check that in each call of a function *_si(), the si parameter is actually an slong and not a ulong or mp_limb_t. This had to be done for every call across the FLINT code base. I volunteered and checked some.
3rd August - 9th August
At the beginning of this week, I realised that it is too late to implement the double large prime MPQS completely. I decided to go back to the ECM code I had written and complete some of the work I had postponed till after the GSoC period. The main reason was that I knew what was going around in the ECM really well, and thought that I could do considerable work working on it.
The ECM code I had written was doing good, under a factor of 2 compared to GMP-ECM. There were a couple of algorithmic enhancements I had in mind, which could make it even faster and comparable to GMP ECM. These included multi point evaluation in stage II, the Montgomery PRAC algorithm in stage I and maybe Edward coordinates.
I started off by checking the code for any memory leaks and unnecessary memory allocations. I found unnecessary allocations in stage II, and cut them out using better indexing (in stage II). This reduced the memory being used by almost half in the stage II code. There were a couple of places where there were memory leaks. I resolved this as well.
I also fixed the hack I was using in fmpz_factor_ecm_select_curve(). I couldn't figure out how exactly to call mpn_gcdext() earlier on. I realised this week that I was passing an mp_limb_t, whereas I should have been passing an mp_size_t (the latter is signed!). So when the inverse was negative, I was facing problems (the function sets the "size" argument as negative if the mp_ptr is negative). Earlier on, I avoided using mpn_gcdext(). When it was required, I was converting back to fmpz_t's, calling fmpz_gcdinv() and then converting back to mp_ptr's! Now I am making a direct call to mpn_gcdext().
I also started to incorporate multi point evaluation in stage II this week. I had tried this earlier on, however contrary to my expectation, it was almost two times slower. I coded the stage II again (thankfully I had the ECM fmpz code from some time back, coding directly using mpn's would have been very difficult). However yet again, it didn't turn out to be faster than than the existing code. Maybe I'm doing something wrong theoretically? However in such a case, stage II should never be able to factor, whereas it is definitely.
I made some more minor changes to the ECM code and polished it, it seems good to be merged to me.
What next
After a brief conversation with my mentor, I have decided to go back to MPQS. In the coming week, I will be working on a simple sieve, which uses multiple polynomials, without any self initialisation. A lot of code required for this already exists in the FLINT trunk.