View Single Post
Old 2021-05-23, 22:12   #15
ewmayer's Avatar
Sep 2002
Rep├║blica de California

3·132·23 Posts

[We open our next scene with a hand slapping the owner's forehead, accompanied by the utterance "doh!"]

Re above: In fact it seems silly to use powerful general-modulus factoring machinery like ECM or QS on such (p-1)-found factor-product composites. Here's why: say we have some product of prime factors F = f1*f2*...*fn discovered by running p-1 to stage bounds b1 and b2 on an input Mersenne M(p) (or other bigum modulus with factors of a known form, allowing p-1 to be 'seeded' with a component of same). BY DEFINITION, each prime factor f1-fn will be b1/b2-smooth, in the sense than fj = 2*p*C + 1, where C is a composite all of whose prime factors are <= b1, save possibly one outlier-prime factor > b1 and <= b2. Thus if we again run p-1 to bounds b1/b2, but now with arithmetic modulo the relatively tiny factor product F, we are guaranteed to resolve all the prime factors f1-fn - the only trick is that we will need to do multiple GCDs along the way in order to capture the individual prime factors f1,...,fn, rather than have this secondary p-1 run modulo F again produce the same composite GCD = F which the original p-1 run mod M(p) did. Again, though, since in the followup p-1 run we are working mod F, all the arithmetic is trivially cheap, including the needed GCDs. And since the cost of a p-1 run is effectively akin to a single super-cheap ECM curve, we've reduced the work of resolving the composite F to just that equivalent.

Last fiddled with by ewmayer on 2021-05-23 at 22:17
ewmayer is offline   Reply With Quote