Find the value of N for which the relation-building step in the quadratic sieve results in roughly
Question:
Find the value of N for which the relation-building step in the quadratic sieve results in roughly a 200 by 200 matrix - and then implement the quadrac sieve for factoring numbers of roughly that size, using the other code we have written thus far.See Proposition 3.47 in the text for guidance on how to find suchN.The steps are:
(a) Find the appropriate value ofB(again, see the text, chapter 3.7.2) You’ll need to use the square-root-finding code, and it’ll look a lot like your sieve of Eratosthenes code from the last assignment.
(b) Use the sieve method described in the text to find a list of B-smooth numbers a2−N, for various a larger than√(N).
(c) Once you’ve found enough of those: factor them, make a mod 2matrix A of their exponent vectors, and find a nontrivial solution ofAx= 0.
Discovering Advanced Algebra An Investigative Approach
ISBN: 978-1559539845
1st edition
Authors: Jerald Murdock, Ellen Kamischke, Eric Kamischke