2016-12-02, 19:01 | #1 |
Oct 2012
2·41 Posts |
Are these polynomials being generated correctly?
I'm just double checking that the polynomials in my upcoming implementation of the MPQS are being generated correctly:
n = 1287871475892167 First prime is near sqrt(sqrt(2*N)/M), where M is the sieve size, in this case: 500,000 Polynomials generated (Ax + B)^2 - N: A: 121 B: 109 A: 169 B: 51 A: 361 B: 345 A: 1849 B: 533 A: 2209 B: 1655 A: 2809 B: 2757 This is how I'm generating them: After finding a prime Q close to sqrt(sqrt(2*N)/M), which is a quadratic residue mod N, I set: A = Q^2 h = N^((Q+1)/4) mod Q v = (2h)^-1 * ((N - h^2)/Q) mod Q B = h + vQ mod Q^2 If B is even, then B = A - B. In the trial division stage, values of X are plugged into the polynomial (Ax + B)^2 - N, and divided by A, before being divided over the factor base. Is this process correct? Are the polynomials above correct for the given input? Thank You Last fiddled with by Sam Kennedy on 2016-12-02 at 19:02 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Externally Generated Polynomials Don't Seem To Be Being Considered | EdH | Msieve | 4 | 2017-02-03 15:13 |
mprime (Linux) doesn't do "affinity" correctly... | chalsall | Software | 16 | 2014-01-03 15:55 |
LLR not doing checkpoints correctly on some numbers | Puzzle-Peter | Conjectures 'R Us | 0 | 2013-08-15 13:45 |
[Win7] GnuPG-generated files not showing up? | ixfd64 | Lounge | 1 | 2012-06-23 12:43 |
Running Glucas correctly? | Unregistered | Software | 15 | 2003-12-14 20:27 |