![]() |
![]() |
#1 |
Oct 2012
2·41 Posts |
![]()
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 | |
![]() |
||||
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 |