Re: time-limited integer factorization

["Max Alekseyev" <maxale@gmail.com>]

Dear Bill,

factor_add_primes in your script does not always work as expected. For example:

? default(factor_add_primes,1)
%1 = 1
? factor(112455406951957393093)
%2 =
[7 1]
[11 1]
[37 1]
[8513 1]
[1245683 1]
[3722183 1]
? factor(112455406951957393093,0)
%3 =
[7 1]
[11 1]
[37 1]
[8513 1]
[4636660085989 1]

It seems that in this example the primes 1245683 and 3722183 were not
recorded with addprimes(), but I have no idea why. The
factor_add_primes documentation does not explain what criterion is
used to decide which primes it adds with addprimes().

As the result, I often see incomplete factorizations produced by your
timefact() routine even when the running time is far below the
specified limit. Is there a way to overcome this problem?

Thanks,
Max

On Nov 17, 2006 3:53 PM, Bill Allombert <allomber@math.u-bordeaux.fr> wrote:

> So I propose a cleaner way. You need the following C file:
> ----%8---alarm.c----------------------------
> #include <pari/pari.h>
> #include <unistd.h>
> /*
> GP; install("startalarm","vL",,"./alarm.so");
> GP; install("stopalarm","v",,"./alarm.so");
> GP; addhelp(startalarm,"(sec): interrupt GP after sec seconds");
> GP; addhelp(stopalarm,"(): stop a pending alarm");
> */
>
> static void pari_sigalarm(int foo) { raise(SIGINT); }
> void
> startalarm(long sec)
> {
>   os_signal(SIGALRM,pari_sigalarm);
>   alarm(sec);
> }
> void stopalarm(void) { alarm(0); }
> ---------------------------------------------
> (You can compile and run it with gp2c-run)
>
> Now the script is a bit simpler:
>
> default(factor_add_primes,1)
> install("startalarm","vL",,"./alarm.so");
> install("stopalarm","v",,"./alarm.so");
> timefact(N,sec)=
> {
>   trap(siginter,0,startalarm(sec);factor(N));
>   stopalarm();
>   factor(N,0);
> }
>
> Cheers,
> Bill
>