Help about document for Msieve 1.38

[Greenk12]

Hello everybody!

I am Binh. I am a student. Now, i am studying about factoring and Msieve. So I hope i will be received your help.

I want to know about Block Lanczos implementation in Msieve program.
I've already read about Block Lanczos theory ( document that i read : A New Parallel Approach to the Block Lanczos Algorithm for Finding Nullspaces over GF(2) - by I Flesch, A Block Lanczos Algorithm for Finding Dependencies over GF(2) - by Peter L.Montgomery)

I understanded Block Lanczos theory, but i don't understand Block Lanczos of implementation in Msieve program, especially :

uint64 * block_lanczos(msieve_obj *obj, uint32 nrows,
uint32 num_dense_rows, uint32 ncols,
la_col_t *B, uint32 *num_deps_found)
{...}

i don't understand what form matrix B that i need to pass in block_lanczos function.

Could you explaint it to me? Or Could you show me an example a matrix B that i need to pass in block_lanczos function ?

Could you show me any document about your block_lanczos of implementation ?

Thank you for reading!
Hope being received your help.

[jasonp]

Msieve represents matrices by column, because they're built one column at a time; B is an array of ncols matrix columns, and each column is given an la_col_t structure. The la_col_t has two fields:

- the count of sparse nonzero elements in that column
- an array of 32-bit words to hold the row numbers containing a 1 for
that column

Rows are numbered from 0 to (nrows - 1), and the first num_dense_rows rows are considered dense. The array has one 32-bit word for each of the sparse rows (sorted by increasing row index), and then (num_dense_rows+31)/32 words where the nonzero dense rows are stored in packed (bitwise) form. Dense row i gets bit i in this latter array. QS matrices always have num_dense_rows = 0, and the same block Lanczos code is used by both QS and NFS.

There is very little linear algebra documentation outside comments in the code, but the algorithm is exactly as described in Montgomery's initial paper.

[Greenk12]

Yes, I see.

Thank you very much.

Continue working.