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

Georg-Johann Lay avr at gjlay.de
Mar 24 Mar 15:10:20 CET 2020


paul zimmermann schrieb:
>        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,

Hi, Paul. Attached a small Python script that shows how it works.
Most of it is just infrastructure to get factor_p_minus_1() running.
Added are some comments to make clear the intentions.  Should work
with Python v2.7 and v3.

> and a patch that implements your idea?

Sorry, I am not experienced enough here to propose substantial patches.

Johann


> Best regards,
> Paul

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: pm1-demo.py
URL: <http://lists.gforge.inria.fr/pipermail/ecm-discuss/attachments/20200324/5c70cb6f/attachment.ksh>


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