Assigned 28 Mar 17, Due 6 Apr 17.

Implement the quadratic sieve method for factoring. Test your program by trying to factor these examples. Various strategies can be tried. For example, you could try using more than one polynomial to generate the factor base. Helpful information about the quadratic sieve, including possible optimizations, can be found here. Generate timing information for your computations. I don't expect you will be able to compute all of them, but see how well your program performs. You can compare the performance to the factoring algorithm in gp-pari. If your program does in fact successfully compute all these, generate bigger examples until your program fails.

Groups for this project:

- Fischer, Alex; Boratko, Mike; Rubenstein, Yoni; Grosser, Stefan;
- Dugan, William; McCormick, Ned; Hajaj, Nimrod; White, Ethan;
- Bissaillon, Matthew; Egid, Adin; Burdick, Corwin;
- Gramigna, Matthew; Xie, Wei; Greengus, Barry;

Revised: Tue Mar 28 13:16:53 EDT 2017

Paul Gunnells

gunnells at math dot umass dot edu