Skip to Content.
Sympa Menu

cado-nfs - [Cado-nfs-discuss] unbearably slow factorization

Subject: Discussion related to cado-nfs

List archive

[Cado-nfs-discuss] unbearably slow factorization


Chronological Thread 
    < Chronological >      < Thread >
  • From: "mike@mikepage.us" <mike@mikepage.us>
  • To: cado-nfs-discuss@lists.gforge.inria.fr
  • Subject: [Cado-nfs-discuss] unbearably slow factorization
  • Date: Fri, 26 Jan 2018 09:07:19 -0700
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=mike@mikepage.us; spf=Pass smtp.mailfrom=mike@mikepage.us; spf=None smtp.helo=postmaster@cockroach.ash.relay.mailchannels.net
  • Ironport-phdr: 9a23:rtavDRQmVr5WKoloxtqMYWP8vtpsv+yvbD5Q0YIujvd0So/mwa6yZxCN2/xhgRfzUJnB7Loc0qyK6/mmATRIyK3CmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TW94jEIBxrwKxd+KPjrFY7OlcS30P2594HObwlSizexfa5+IA+qoQnNq8IbnZZsJqEtxxXTv3BGYf5WxWRmJVKSmxbz+MK994N9/ipTpvws6ddOXb31cKokQ7NYCi8mM30u683wqRbDVwqP6WACXWgQjxFFHhLK7BD+Xpf2ryv6qu9w0zSUMMHqUbw5Xymp4qF2QxHqlSgHLSY0/mHLhcN/gqxVvRGvqQJ4zY7Ve4yaLuZyfqbHcNMaWWZNQMBcXDFBDIOmaIsPCvIMMehdr4n8pFsBswCzBQytBOPs1DBInmX53aIk3Og7DAHGxwIsFM8JvXTRrdX1N7kdXPuwzKnJzjXMcetW1i3y6IfWaBwhvOqMUKt2fMHMx0cvEAbFgU+RqYzjJz6V0uUNs26Y7+V+SO2vimgnpxttrTiow8chjJTCiIENyl3c6yl0zpw5KN62RUJhf9KoDoVcuzuUOoZ0Ws8vQmNltDwnxrACpZK3ZjUGxZA9yxLCdfCKd46F6Q/5WumLOzd3nndldaq/hxms9UigzfXxWdWz0FlWrSpFiN7MuWoR2BzT8MSIUOB9/ke71TaVyQ/T7vtLIEAumareMZEhw7owmYYTsUvZGC/2nlv5jKuNdkk+/Oin9fjnbq3npp+aKYB0lhnzProgl8ClAuk1PBICU3aF9eiizrHu80/0TK1PjvIsk6nZtJ7aJd4cpq68GwJV14cj6xWhADq91dQYnHoHI0xdeB2dgIjmJUvCIO3jDfunmVSjjC9rx+zaPr3mGpjCMmLMn6rmfbpk7U5cxhEzwclC6JJVEbEOPO/zWlTqtNHDCh85Mhe0w/r8CNln2YMeV2WPArWWMKzMq1OI5+QvI/ONZIAPojr9JeIltLbSiioykFMaOK+nxt4baWuzA+99C0GYemb3xNgPFn0Fs0w/SvbrgRuMS219fXG3Cug55zI2IIenDorbT4+gxqGalm/vG5xVa0hDC1OBCX7nesOZQKFfO2qpPsZ9n2lcBvCaQIg72ET27V6o+/9cNuPRvxYgm9fm3dlx6ffUkEhppzl1DMmF2m6ACXxvzDpRG20GmZtnqEk48W+tlLBiiqUDR9lS5P5RWwg3c4PHnbQjVoLCHznZd9LMc26IB9WrBTZqHoA6xNQNeUF0ENXkhwvDmTCnB7YE0bmCBZg/8qva2XX1PIB7xmqUjKQ=
  • List-archive: <http://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/>
  • List-id: A discussion list for Cado-NFS <cado-nfs-discuss.lists.gforge.inria.fr>
I tried to factor the following with cado-nfs:
./cado-nfs.py 45092142015619504885545233428956286716628249204022412001730233506211619093779816252705400749792379537111120400056001524660779352594720896883613951409971968610022842465256891175311

after several hours I killed it
the last few lines of output:
Info:HTTP server: 127.0.0.1 Sending workunit c180_polyselect1_270000-275000 to client localhost
Info:Polynomial Selection (size optimized): Adding workunit c180_polyselect1_320000-325000 to database
Info:Polynomial Selection (size optimized): Parsed 160 polynomials, added 3 to priority queue (has 100)
Info:Polynomial Selection (size optimized): Worst polynomial in queue now has lognorm 50.620000
Info:Polynomial Selection (size optimized): Marking workunit c180_polyselect1_260000-265000 as ok (5.3% => ETA Fri Feb  2 10:55:20 2018)

(ETA was 8 days!!!!)

I was trying to verify the factorization that maxima produced in relatively short order:
(%o1) 17*2652478942095264993267366672291546277448720541413083058925307853306565829045871544276788279399551737477124729415058913215339961917336523346094938318233645212354284850897464186783

maxima uses trial divisions by primes up to 9973, Pollard's rho and p-1 method and elliptic curves but not nfs.

Is this just an issue with suitability of the algorithm? Why is nfs such a poor performer on this input?


Mike Page
Theory and Practice, LLC
www.linkedin.com/in/MikePageHPC
mike@mikepage.us
303-944-8291


Archive powered by MHonArc 2.6.19+.

Top of Page