-
Notifications
You must be signed in to change notification settings - Fork 4
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
assertion failure at 1198528981044337307280190876781 #3
Comments
thank you for identifying this problem. |
@michel-leonard |
Hi @jay20162016, I've investigated (by asserting at line 404 that To address this, I increased the size of the prime number base from Please let me know if this change resolves the problem on your end, or if you encounter any other issues. Best regards, |
Hi @moritzbeck13, Thank you for bringing this issue to our attention. The number you provided, Explanation of the IssueThe 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 LimitationsTo 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. ConclusionI 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, |
quadratic_sieve: fac_quadratic.c:522: iteration_part_6: Assertion `R->mem == R->end' failed.
The text was updated successfully, but these errors were encountered: