MPQS

[Bill Daly <bill.daly@tradition-ny.com>]

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.
**********************************************************************