[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