Bill Daly on Tue, 30 Nov 1999 17:55:32 -0500

 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

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

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