[flint-devel] Multiple Lucas tests

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

Hello

I think I have implemented the psudocode that I wrote yesterday and
amazingly I think it might actually be working! However I am not sure if it
is even supposed to. I realized whilst I was writing the code that the
parameter passed to the Lucas chain actually depends on n (A=a^2*b^(-1) - 2
mod n (where b^(-1) is the inverse mod n)) However for a=1,b=-1 which is the
case I am interested in (its worth $620) I realized that this simplified to
-3 mod n or n-3. At this point I had already written most of the code so I
thought I may as well just try passing N-3 as the parameter (where
N=n_1*n_2....n_r as in the psudocode). This seamed to work and simply
reducing V_M mod n_i and continuing from there got me the same answers as
computing the V's from scratch. Unfortunately the computer seg-faults if we
try to do more then 5 17-digit numbers (I think N is getting too large. Not
sure though). Also in order for it to be worth the extra effort the numbers
need to have as many of there highest bits in common as possible. I am not
sure this will actually be the case after we have sieved etc.

It might be worthwile writing some profiling code of the various methods we
have developed for (psudo)prime tests for several numbers. If that shows
that there are significant benefits between them and testing numbers one at
a time then perhaps it would be worth writing up?

Peter