View Single Post
Old 2021-11-04, 17:16   #6
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

25·72 Posts

Originally Posted by axn View Post
It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).
Originally Posted by Zhangrc View Post
It's not worth it
Today multiple times I felt the same, but currently I think that this is a working idea, even in P+1/ecm ! Would give a tiny speedup. Let me check my suggestion.
In the general way: for a given T=prod(q_i) exponent the effective score=log2(T)/sum(1/q_i), where smaller score is better.
Since this is a 1st stage idea, let B=B1.

What you all forget that if you include q^e for a possible extended 1st stage in (B,B'), then the extra effort for q^e in (B,B') means only a q-th exponentiation in the method [because in any case you'd process q^(e-1) in the usual way because q^(e-1)<B], and not q^e-th exponentiation, but gives you the largish 1/q>1/B' probability to find a divisor with the P-1 method.

My suggestion is to use B'=2*B, in fact a slightly smaller.
To convince you quickly:

The effective score=log2(T)/sum(1/q^e), where T is the exponent.
You stopped at B, and at that point you've score=log2(B)*B=besteff.

Include all primepowers, but not primes from the (B,2*B) interval, so choose B'=2*B.

For a single primepower the effective score is at most log2(sqrt(2*B))*2*B=0.5*(log2(B)+0.5)*2*B=
=(log2(B)+0.5)*B, almost good, there is a fractional error bit. So shrink it a little:

For a fixed B choose B'=c*B (where c depends on B and e!), then

log2(sqrt(c*B))*c*B=0.5*(log2(B)+log2(c))*c*B<log2(B)*B=besteff for any c<2 if B is "large".

In general the best bound for fixed B and e>1 let B'=U, at an equal effective score you would see:

log2(U^(1/e))*U=log2(B)*B or the same
log(U)*U/e=log(B)*B, because you can change to natural logarithm (and here e>1 is an integer).

Example: for B=10^5 and e=2 this gives U=189482 (as expected close to 2*B for e=2), if we use this same bound
for all e>1 in (B,U) then:

log2(T)=1062.02 (used the product of primepowers's core part).
and effective score=1112854.2 what is smaller than the base score:

ps. as said for e>2 you have to use an even larger bound, and that could be higher than 2*B, so for smallish
primes you have to include more primes, q^2 or more, the analysis is still correct, because in these
cases the algorithm picked up the smaller primepower for a smaller e'<e integer.
R. Gerbicz is offline   Reply With Quote