mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Linear algebra in MPQS (https://www.mersenneforum.org/showthread.php?t=7061)

 R1zZ1 2007-02-01 22:56

Linear algebra in MPQS

Hi all, I'm an italian student and I need your support.

I'm implementing MPQS with GMP, the implemented sieving algorithm works fine and I obtain the sparse matrix representing the good relations that I can use to solve the linear algebra and find factors.

My problem is just to solve the linear algebra. I need a C++ implementation or Pari/GP function that find these solutions using gaussian elimination or lanczos (faster, right?).

 R1zZ1 2007-02-01 23:20

I'll also appreciate if you indicate me a C++ library with a function that solves equations system over Z_2.

Lidia has a function named solve() but i am not sure that it works with sparse matrix modulo 2 and gives me a valid solution.

bye

 jasonp 2007-02-02 06:45

[QUOTE=R1zZ1;97477]Hi all, I'm an italian student and I need your support.

I'm implementing MPQS with GMP, the implemented sieving algorithm works fine and I obtain the sparse matrix representing the good relations that I can use to solve the linear algebra and find factors.

My problem is just to solve the linear algebra. I need a C++ implementation or Pari/GP function that find these solutions using gaussian elimination or lanczos (faster, right?).
[/QUOTE]
Lanczos is much faster than Gauss elimination.

There are several MPQS implementations linked to the sticky at the top of the factoring forum; they all have to solve this problem, and there's plenty of code to browse.

jasonp

 All times are UTC. The time now is 18:18.