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

Georg-Johann Lay avr at gjlay.de
Ven 20 Mar 21:55:03 CET 2020


paul zimmermann schrieb:
>        Dear Georg-Johann,
> 
>> From: Georg-Johann Lay <avr at gjlay.de>
>> Date: Fri, 20 Mar 2020 15:32:32 +0100
>>
>> Am 20.03.20 um 14:19 schrieb paul zimmermann:
>>>         Dear Georg-Johann,
>>>
>>> it appears that ep->sigma, which is initially 0 (un-initialized) is set
>>> by ecm_factor, and then if the first call fails, since now ep->sigma is
>>> non-zero, it is taken as the sigma value, and it fails again and again.
>>>
>>> With mpz_set_ui (ep->sigma, 0) after the ecm_factor() call it works better,
>>> but there still seems to be a problem.
>>>
>>> Paul
>> Tried that, but it did not help.
>>
>> What helps though is to use a fresh ecm_params for each ecm_factor call.
>>
>> It this supposed to be the case?  I did not find a documentation of
>> ecm_init() / ecm_clear() and used them similar to respective mpz_*
>> functions, i.e. init once at start of program and clear at the end.
> 
> yes and no. Some of the ecm_param fields are used internally, without being
> restored to their original state. All this would need a major redesign,
> but in the short term you can either use a fresh ecm_params() at each call,
> or use the brand new ecm_reset() functions I've added to the svn version.
> With ecm_reset (ep) added to res = ecm_factor (...) in your code, it works.

Ok, thanks for the pointer!


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.

Johann



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