Bill Daly on Tue, 30 Nov 1999 17:55:32 -0500 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
MPQS |
I've been studying the MPQS code to learn how it works, and there are a few pieces of code which look wrong to me. 1. One fairly trivial point. In mpqs_combine_large_primes at lines 2081ff (version 2.0.17), there are a number of fprintf(stderr... statements rather than fprintferr(... These messages are not written to the log file. Was this what was intended? 2. In mpqs_find_k at lines 713ff, the condition kross(smodis(kN, p), p) == 1 precludes the case k == 0 mod p, thus the condition k % p == 0 in line 717 is always false. I think it was intended that the first condition be kross(...) >= 0, but see below. 3. In mpqs_create_FB at lines 823ff, I would have expected that a prime p dividing k would be included in the factor base, since Q(x) can be divisible by such primes. mpqs_sieve does not accumulate log_p for these primes, although I would assume that this is what the condition start1 == start2 is intended to handle, i.e. the equation Y^2 = kN mod p has only one root only when kN (thus also k) is divisible by p. Similarly, in mpqs_eval_candidates, factors of primes dividing k are not removed. Perhaps there is a good reason for this, but if so the comments leave something to be desired. 4. The comment in mpqs() at lines 3120ff says that the optimum size for A is sqrt(kN)/M. I would have thought that the intention was to sieve over values of Q(x) in the range -kN..kN, and in fact values outside this range will not work in mpqs_eval_candidates (see below). But with A ~= sqrt(kN)/M, we have max(|Y|) ~= 2*sqrt(kN), thus max(Q(x) = Y^2-kN) ~= 3kN. To keep Q(x) in the range -kN..kN, we need A ~= sqrt(kN/2)/M. 5. The code in mpqs_eval_candidates looks wrong to me. The sieve locates values of Q(x) = Y^2 - kN which are the products of small primes, but the code treats Q(x) instead as Y^2 mod kN, which is not the same thing. Only if kN <= Y^2 < 2kN will Y^2 - kN = Y^2 mod kN. The sign logic extends this to cover the cases 0 <= Y^2 < kN, but still if Y^2 >= 2kN, the wrong value of Q(x) will be used for factorization. It looks like the useless_cand flag was included to catch this, since if Q(x) is correct it should never happen that the useless_cand flag is set. (Well, actually there is one other case that useless_cand can be set, when p divides A but not Q(x)/4A, but surely this is a bug.) Perhaps I am seeing ghosts here -- if so, I hope someone can show me where I have gone wrong. [Just as an aside, I have recently moved offices and my Internet access is still mostly down. I suspect that I have not been receiving all of my email, so if someone (Gerhard?) replies to this, I may not see it. If you can't reach me at tradition-ny.com, please try tradition.co.uk instead, and if that fails also, please try wdaly@optonline.net.] Regards, Bill ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. This footnote also confirms that this email message has been swept by MIMEsweeper for the presence of computer viruses. **********************************************************************