[Ecm-discuss] Need assist with an ECM-GMP program.

paul zimmermann Paul.Zimmermann at inria.fr
Sam 21 Mar 07:11:20 CET 2020


       Dear Johann,

> Apart from that I might have found an improvement to pm1.
> In pseudo-code, it reads basically:
> 
> a <- some_value
> for p in primes:
>      expo <- get_expo (p)
>      a <- a ** (p ** expo) (mod N)
> return gcd (a-1, N)
> 
> There are cases where a = 1 after the loop, so that no factor is found.
> This happens when there are (still) small factors in N.  If instead:
> 
> a <- some_value
> for p in primes:
>      expo <- get_expo (p)
>      b <- a ** (p ** expo) (mod N)
>      if b = 1:
>          break
>      a <- b
> return gcd (a-1, N)
> 
> This has double benefit:
> 
> 1) It shortens the loop if it's useless to continue.
> 
> 2) Improves chance of finding (small) factors.
> 
> I found that ECM often has a hard time when N is contaminated with
> small factors that remain after, say, trial division.
> 
> It's bit less useful with pm1's cascade-mul, but as comparison
> against 1 is not costly at all, it might still be an improvement?
> 
> And even if gcd(a-1,N) = 1,  b = 1 means we have a factor of Euler's
> phi(N) which should help with factorizing N.

please can you provide a concrete example where that phenomenon appears,
and a patch that implements your idea?

Best regards,
Paul


Plus d'informations sur la liste de diffusion Ecm-discuss