QS - reflections and questions

[Peter Hackman]

I haven't had the time to browse this forum so I apologize if my observations and questions are elsewhere to be found. I'll be grateful for a pointer.

Lately I've been toying with a simplified MPQS program, with modest ambitions (I will later modify it into a SIQS version). For the time being it's pretty useless beyond 50 digits (and from 47 to 50 is quite a step).
Some choices: logs ar ints of 2-logs.
Primes below a certain limit (say, 11, 17, 37, 57, 100) are not used, neither are prime powers.
Target is 0.5log(N) + log N -2 (I believe the actual average is
sqrt(2N)M/3, right?), error term is 2*log(pmax). Primefinder is:
if gcd(r,105)=1, Miller-test for prime bases up to 23. Else add 4's until a new gcd=1 is encountered, etc. Final square root is Brillhart-Morrison.


My first observation, in this range, is that the optimum must be very flat, as I can change several parameters quite a bit without discernible change in peformance. Right?

My second observation is a bit puzzling. At first I had the idea of creating
the q's in a=q**2 by simply stepping outwards
in both directions from the ideal value r=
sqrt(sqrt(2N)/M) (if I remember correctly).


But I also tried creating starting points (for prime finding) at random in the interval 0.9*p to 1.1*p. To prevent collisions I then had to create a list of the q's found and check each new q against the list. IN ALL MY RUNS THE SECOND METHOD WAS FASTER! I realize there could be parameter choices
whithin the program
that favor one method over the other; else the only explanation I can find
is the second method requires fewer steps in general before a new prime is found. In the first method we always take the full number of steps between two adjacent primes in the class of 3 mod 4.

Question: I realize of course that square-rooting mod primes in the class of 3 is deterministic, but is it that much faster?