Re: Factoring and memory usage by matkermod

[Aurel Page <aurel.page@normalesup.org>]

Hello Doug,

matkermod is designed to be able to handle non-prime modulus, but for prime modulus using matker(Mod(m1,2)) should be more efficient (both in speed and memory consumption). That said, I know that the matxxxmod functions tend to use a lot of memory; I am planning to investigate at some point, maybe this can be improved.

Best,
Aurel

On 01/04/2020 21:58, T.D. Telford wrote:

Hello,

I have written a MPQS factoring program, and GP was very useful.

To find the kernel of my smooth number exponents matrix (modulo 2 entries) m1, I used

matkermod (m1,2)

This works great for smaller dimensions of m1, but once m1 dimensions get to be about 1000, there appear to be memory usage problems.

For a large m1 (1000 x 1000), the stack size is < 100MB before calling matkermod, but matkermod wants to increase the size to 4000MB.

For a slightly larger m1, the stack size goes up to 8000MB.  Since I have 16 GB of memory, this limits how large a number I can factor.

I tried using gaussian elimination and finding the kernel, but the elimination is quite slow  (takes about the same time as all of the sieving).

So my questions are:

1. Is the large stack size increase by matkermod correct?

2. Can you suggest an alternate approach to finding the kernel?

Regards,

Doug