assertion failure at 1198528981044337307280190876781

[jay20162016]

836. 1198528981044337307280190876781

quadratic_sieve: fac_quadratic.c:522: iteration_part_6: Assertion `R->mem == R->end' failed.

[michel-leonard]

thank you for identifying this problem.
I use this command line to reproduce the error: ./qs 1198528981044337307280190876781 -r=111, but i'm still looking for the solution.

[moritzbeck13]

@michel-leonard 32115920099212569105106779097640231161112770207070059646211939683635728962265075652991614878272272454539611555745310747733885970866333511478662533604607053662543710242659089271255121936433439154585717 fails aswell for me

[michel-leonard]

Hi @jay20162016,

I've investigated (by asserting at line 404 that i < qs->base.length) the issue you reported, and it seems to be related to the size of the prime number base being too small. Specifically, this was causing an "out of bounds" access to the integer qs->base.data[i].num, where i was exceeding its maximum possible value. This led to selecting numbers that were far too large and unrelated to the prime base in memory.

To address this, I increased the size of the prime number base from 800 to 1000 (using param_base_size at line 110) for integers that are under 130 bits. This adjustment appears to neutralize the error, and the code now runs without the "out of bounds" issue.

Please let me know if this change resolves the problem on your end, or if you encounter any other issues.

Best regards,
Michel

[michel-leonard]

Hi @moritzbeck13,

Thank you for bringing this issue to our attention.

The number you provided, 32115920099212569105106779097640231161112770207070059646211939683635728962265075652991614878272272454539611555745310747733885970866333511478662533604607053662543710242659089271255121936433439154585717, is a 663-bit integer.

Explanation of the Issue

The Quadratic Sieve algorithm, while efficient for factoring numbers up to a certain size, has limitations when it comes to extremely large numbers like this one. The algorithm's efficiency decreases significantly as the number of bits increases, and it becomes impractical for numbers larger than around 300 bits.

In this case, a 663-bit number is far beyond the practical limits of the Quadratic Sieve. The prime number factor base used in the algorithm also becomes insufficient for numbers of this size, which can lead to unexpected behavior, including memory access issues.

Current Implementation and Limitations

To prevent such issues, I have set a default bit limit of 220 bits in the program. While it is possible to factor numbers up to 300+ bits with careful tuning, factoring a 663-bit number is not feasible with this algorithm. This limit is necessary to ensure the program operates within practical bounds and does not encounter errors or excessive resource consumption.

Conclusion

I recommend using more advanced factoring algorithms, such as the General Number Field Sieve (GNFS), for numbers of this size. The GNFS is currently the most efficient classical algorithm for factoring very large integers, though it is also significantly more complex and resource-intensive.

If you have any further questions or need assistance with smaller inputs, feel free to reach out. I appreciate your understanding of the limitations of the Quadratic Sieve algorithm.

Best regards,
Michel Leonard