[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