View Single Post
2021-11-04, 17:16   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts

Quote:
 Originally Posted by axn It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).
Quote:
 Originally Posted by Zhangrc 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).
sum(1/q^e)=0.000954325
and effective score=1112854.2 what is smaller than the base score:
log2(B)*B=1660964.05

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.