[flint-devel] Multiple Lucas tests at once

[Peter S. <ps...@gm...>]

Hello

I have done some more work on the simultaneous Sieving and Pocklington code
and that now works for numbers that have a prime factor greater then
primes[TF_CUTTOF]. See attached. I think the collision code needs more work
as currently it is not doing an awful lot to deal with it. Although the way
I have done it with both the sieve and the hash table it is still possible
to recover which two numbers collided and often one of them will fail the
Baillie-PSW test so it dosn't need to be factorised.

Also I was thinking about what you were saying with computing 2^k mod
N=n_1*n_2....n_r and I think that it could apply to the Lucas test. I have
written some pseudocode (attached) which might help. The basic idea is to
compute V_M mod N where M has several of the last bits in common with the
m_i's This gives us a starting point to compute the m's from. I am not sure
weather this will actually be quicker and it will require some multi
precision arithmetic but it might be worth while.

Peter