Cannot factor 71281426948143699070565 with ecm.factor()

[Bill Witzke]

Hi,

I have a hard time factoring the number 71281426948143699070565 using ecm.factor().  No result is given after a few minutes runtime.  Though, plain factor() happily factors the number.  Factoring smaller or larger numbers  work fine with ecm.factor(), too.  Just the single given number seems to be problematic.

Am I doing something wrong?  Can someone confirm?

system:

Ubuntu 22.04

sagemath 9.5-4 (via apt)

Intel Pentium N5000

(SageMath and Python beginner)

example code factoring numbers in the range [71281426948143699070565  - L, 71281426948143699070565 + L]:

# Odd number.
n = 71281426948143699070565
# Limit.
L = 2
# Iterate over interval [-L, L].
for i in range(-L, L + 1):
    m = n + i
    print("%d  =>  %s" % (m, ecm.factor(m)))

[G. M.-S.]

For me, with SageMath version 9.8.beta7

sage: ecm.factor(71281426948143699070565)

does not return quickly either.

Indeed, running

sage: ecm.interact()

seems to show a strange behaviour for 71281426948143699070565 when factoring the factors found.

As this is probabilistic and the output changes every time, I do not copy it here.

Guillermo

[Dima Pasechnik]

On Sun, Jan 29, 2023 at 3:04 PM G. M.-S. <list...@gmail.com> wrote:
>
>
> For me, with SageMath version 9.8.beta7
>
> sage: ecm.factor(71281426948143699070565)
>
> does not return quickly either.
>
> Indeed, running
>
> sage: ecm.interact()
>
> seems to show a strange behaviour for 71281426948143699070565 when factoring the factors found.
> As this is probabilistic and the output changes every time, I do not copy it here.

Basically, the default B1 value is too large in this case.

sage: ecm.factor(71281426948143699070565,B1=200) # almost instant
[5, 53, 337, 1873, 2833, 7507, 20037791]
sage: ecm.factor(71281426948143699070565,B1=2000) # takes looong time

the docs say:

* "B1" -- initial lower bound, defaults to 2000 (15 digit factors).
Used if "factor_digits" is not specified.

>
> Guillermo
>
> On Sun, 29 Jan 2023 at 15:41, Bill Witzke <bwit...@gmail.com> wrote:
>>
>> Hi,
>>
>> I have a hard time factoring the number 71281426948143699070565 using ecm.factor(). No result is given after a few minutes runtime. Though, plain factor() happily factors the number. Factoring smaller or larger numbers work fine with ecm.factor(), too. Just the single given number seems to be problematic.
>>
>> Am I doing something wrong? Can someone confirm?
>>
>> system:
>> Ubuntu 22.04
>> sagemath 9.5-4 (via apt)
>> Intel Pentium N5000
>> (SageMath and Python beginner)
>>
>> example code factoring numbers in the range [71281426948143699070565 - L, 71281426948143699070565 + L]:
>>
>> # Odd number.
>> n = 71281426948143699070565
>> # Limit.
>> L = 2
>> # Iterate over interval [-L, L].
>> for i in range(-L, L + 1):
>> m = n + i
>> print("%d => %s" % (m, ecm.factor(m)))
>
>
>

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/CANnG18_ogCA_MTZ%3DgvC9em6_5PtwxxW7J2dr7PiW5Pq-f-q43A%40mail.gmail.com.

[G. M.-S.]

Thanks Dima, you taught me something new today.

Guillermo

[Bill Witzke]

dim...@gmail.com schrieb am Sonntag, 29. Januar 2023 um 20:50:29 UTC+1:

Basically, the default B1 value is too large in this case.

sage: ecm.factor(71281426948143699070565,B1=200) # almost instant
[5, 53, 337, 1873, 2833, 7507, 20037791]
sage: ecm.factor(71281426948143699070565,B1=2000) # takes looong time

the docs say:

* "B1" -- initial lower bound, defaults to 2000 (15 digit factors).
Used if "factor_digits" is not specified. 

Thanks, that works!

Still, I'm puzzled in what way the default B1 value were too large?  I mean, other numbers of the same magnitude are  factored fine with B1=2000.

[William Stein]

I think everybody understands what's going on regarding ECM now,
thanks to Dima's quick answer.
Paul Zimmerman who wrote this code (and reads sage-support via a daily
digest), sent me this
note to pass on as well:

" Hi William,

please can you forward my answer below?
Thanks,
Paul

##############################################################################

The default B1 value of ecm.factor() is too large. Using B1=2 works:

sage: ecm.factor(71281426948143699070565,B1=2)

[5, 53, 337, 1873, 2833, 7507, 20037791]"

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/CANnG18_HSRJZKhmC8%3DQ476x-FY9s%2BQZToXOKtk0NV1QBquUxtA%40mail.gmail.com.



--
William (http://wstein.org)

[kcrisman]

Is there any notion that the default should be changed, or is that pretty unique to this example?

[Dima Pasechnik]

On Mon, Jan 30, 2023 at 5:29 PM kcrisman <kcri...@gmail.com> wrote:
>
> Is there any notion that the default should be changed, or is that pretty unique to this example?

IMHO a small default is not expensive, as checking for smallish prime
factors should be quick.
But perhaps I'm missing something here.

Dima

>
> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/5272793b-69eb-4e43-8c1a-6997c2f09b16n%40googlegroups.com.