Hello community, here is the log from the commit of package ntl for openSUSE:Factory checked in at 2019-03-18 10:41:16 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ntl (Old) and /work/SRC/openSUSE:Factory/.ntl.new.28833 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ntl" Mon Mar 18 10:41:16 2019 rev:24 rq:685469 version:11.3.2 Changes: -------- --- /work/SRC/openSUSE:Factory/ntl/ntl.changes 2018-10-29 14:58:18.405961743 +0100 +++ /work/SRC/openSUSE:Factory/.ntl.new.28833/ntl.changes 2019-03-18 10:41:19.947274932 +0100 @@ -1,0 +2,7 @@ +Fri Mar 15 21:32:45 UTC 2019 - Jan Engelhardt <[email protected]> + +- Update to new upstream release 11.3.2 + * Fixed a performance issue in the PowerMod function for the + ZZ class. + +------------------------------------------------------------------- Old: ---- ntl-11.3.1.tar.gz New: ---- ntl-11.3.2.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ntl.spec ++++++ --- /var/tmp/diff_new_pack.dLFpNo/_old 2019-03-18 10:41:20.647274077 +0100 +++ /var/tmp/diff_new_pack.dLFpNo/_new 2019-03-18 10:41:20.651274071 +0100 @@ -1,7 +1,7 @@ # # spec file for package ntl # -# Copyright (c) 2018 SUSE LINUX GmbH, Nuernberg, Germany. +# Copyright (c) 2019 SUSE LINUX GmbH, Nuernberg, Germany. # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -18,7 +18,7 @@ Name: ntl %define lname libntl39 -Version: 11.3.1 +Version: 11.3.2 Release: 0 Summary: Library for Number Theory License: LGPL-2.1-or-later @@ -28,13 +28,10 @@ Source: http://shoup.net/ntl/ntl-%version.tar.gz Patch1: no-static.diff BuildRoot: %{_tmppath}/%{name}-%{version}-build -BuildRequires: autoconf -BuildRequires: automake BuildRequires: fdupes BuildRequires: gcc-c++ BuildRequires: gf2x-devel BuildRequires: gmp-devel >= 3.1 -BuildRequires: libtool %description NTL is a C++ library providing data structures and algorithms for @@ -88,7 +85,6 @@ %install pushd src/ %make_install -# DEF_PREFIX="%_prefix" LIBDIR="%_libdir" mv "%buildroot/%_defaultdocdir/NTL" "%buildroot/%_defaultdocdir/ntl" popd rm -fv "%buildroot/%_libdir"/*.la ++++++ ntl-11.3.1.tar.gz -> ntl-11.3.2.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/README new/ntl-11.3.2/README --- old/ntl-11.3.1/README 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/README 2018-11-16 02:33:03.000000000 +0100 @@ -1,5 +1,5 @@ -NTL -- a library for doing numbery theory -- version 11.3.1 -Release date: 2018.10.20 +NTL -- a library for doing numbery theory -- version 11.3.2 +Release date: 2018.11.15 Author: Victor Shoup ([email protected]) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/doc/tour-changes.html new/ntl-11.3.2/doc/tour-changes.html --- old/ntl-11.3.1/doc/tour-changes.html 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/doc/tour-changes.html 2018-11-16 02:33:03.000000000 +0100 @@ -18,6 +18,32 @@ <p><hr><p> <h3> +2018.11.15: Changes between NTL 11.3.1 and 11.3.2 +</h3> + +<ul> +<li> +Fixed a somewhat embarrassing performance issue +in the <tt>PowerMod</tt> function for the <tt>ZZ</tt> class +(which also impacts the prime testing and generation functions). +When using GMP, NTL will now call GMP's <tt>mpz_powm</tt> +function. +Although GMP does have an <tt>mpn_pown</tt> function, +it is not documented, and so cannot be used by NTL. +This means that NTL is now using some <tt>mpz</tt>-level +functionality, in addition to <tt>mpn</tt>-level functionality. +<ul> +<li> +This leads to a significant speedup (sometimes 2-3x), +especially for numbers +with a small number of limbs. +<li> +Thanks to Niek Bouman for helping to sort this out. +</ul> +</ul> + +<p><hr><p> +<h3> 2018.10.20: Changes between NTL 11.3.0 and 11.3.1 </h3> diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/include/NTL/version.h new/ntl-11.3.2/include/NTL/version.h --- old/ntl-11.3.1/include/NTL/version.h 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/include/NTL/version.h 2018-11-16 02:33:03.000000000 +0100 @@ -2,11 +2,11 @@ #ifndef NTL_version__H #define NTL_version__H -#define NTL_VERSION "11.3.1" +#define NTL_VERSION "11.3.2" #define NTL_MAJOR_VERSION (11) #define NTL_MINOR_VERSION (3) -#define NTL_REVISION (1) +#define NTL_REVISION (2) #endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/src/DIRNAME new/ntl-11.3.2/src/DIRNAME --- old/ntl-11.3.1/src/DIRNAME 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/src/DIRNAME 2018-11-16 02:33:03.000000000 +0100 @@ -1 +1 @@ -ntl-11.3.1 +ntl-11.3.2 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/src/VERSION_INFO new/ntl-11.3.2/src/VERSION_INFO --- old/ntl-11.3.1/src/VERSION_INFO 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/src/VERSION_INFO 2018-11-16 02:33:03.000000000 +0100 @@ -1 +1 @@ -39:1:0 +39:2:0 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/src/WINDIR new/ntl-11.3.2/src/WINDIR --- old/ntl-11.3.1/src/WINDIR 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/src/WINDIR 2018-11-16 02:33:03.000000000 +0100 @@ -1 +1 @@ -WinNTL-11_3_1 +WinNTL-11_3_2 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ntl-11.3.1/src/lip.cpp new/ntl-11.3.2/src/lip.cpp --- old/ntl-11.3.1/src/lip.cpp 2018-10-20 17:34:03.000000000 +0200 +++ new/ntl-11.3.2/src/lip.cpp 2018-11-16 02:33:03.000000000 +0100 @@ -5631,6 +5631,83 @@ } +#if (defined(NTL_GMP_LIP) && NTL_NAIL_BITS == 0) +// DIRT: only works with empty nails +// Assumes: F > 1, 0 < g < F, e > 0 + +struct wrapped_mpz { + mpz_t body; + + wrapped_mpz() { mpz_init(body); } + ~wrapped_mpz() { mpz_clear(body); } +}; + +static +void _ntl_gmp_powermod(_ntl_gbigint g, _ntl_gbigint e, _ntl_gbigint F, + _ntl_gbigint *h) +{ + wrapped_mpz gg; + wrapped_mpz ee; + wrapped_mpz FF; + wrapped_mpz res; + + mpz_import(gg.body, SIZE(g), -1, sizeof(mp_limb_t), 0, 0, DATA(g)); + mpz_import(ee.body, SIZE(e), -1, sizeof(mp_limb_t), 0, 0, DATA(e)); + mpz_import(FF.body, SIZE(F), -1, sizeof(mp_limb_t), 0, 0, DATA(F)); + + mpz_powm(res.body, gg.body, ee.body, FF.body); + + if (mpz_sgn(res.body) == 0) { + _ntl_gzero(h); + return; + } + + long sz = mpz_size(res.body); + + _ntl_gsetlength(h, sz); + _ntl_limb_t *hdata = DATA(*h); + SIZE(*h) = sz; + + mpz_export(hdata, 0, -1, sizeof(mp_limb_t), 0, 0, res.body); +} + + +#if 1 +// This version avoids memory allocations. +// On 2-limb numbers, it is about 10% faster. + +static +void _ntl_gmp_powermod_alt(_ntl_gbigint g, _ntl_gbigint e, _ntl_gbigint F, + _ntl_gbigint *h) +{ + NTL_TLS_LOCAL(wrapped_mpz, gg); + NTL_TLS_LOCAL(wrapped_mpz, ee); + NTL_TLS_LOCAL(wrapped_mpz, FF); + NTL_TLS_LOCAL(wrapped_mpz, res); + + mpz_import(gg.body, SIZE(g), -1, sizeof(mp_limb_t), 0, 0, DATA(g)); + mpz_import(ee.body, SIZE(e), -1, sizeof(mp_limb_t), 0, 0, DATA(e)); + mpz_import(FF.body, SIZE(F), -1, sizeof(mp_limb_t), 0, 0, DATA(F)); + + mpz_powm(res.body, gg.body, ee.body, FF.body); + + if (mpz_sgn(res.body) == 0) { + _ntl_gzero(h); + return; + } + + long sz = mpz_size(res.body); + + _ntl_gsetlength(h, sz); + _ntl_limb_t *hdata = DATA(*h); + SIZE(*h) = sz; + + mpz_export(hdata, 0, -1, sizeof(mp_limb_t), 0, 0, res.body); +} +#endif + + +#endif #define REDC_CROSS (32) @@ -5644,47 +5721,51 @@ */ { - _ntl_gbigint_wrapped res, gg, t; - UniqueArray<_ntl_gbigint_wrapped> v; - - long n, i, k, val, cnt, m; - long use_redc, sF; - _ntl_limb_t inv; - if (_ntl_gsign(g) < 0 || _ntl_gcompare(g, F) >= 0 || + if (_ntl_gsign(e) < 0 || _ntl_gsign(g) < 0 || _ntl_gcompare(g, F) >= 0 || _ntl_gscompare(F, 1) <= 0) { LogicError("PowerMod: bad args"); } - if (_ntl_gscompare(e, 0) == 0) { + if (ZEROP(e)) { _ntl_gone(h); return; } - if (_ntl_gscompare(e, 1) == 0) { + if (ONEP(e)) { _ntl_gcopy(g, h); return; } - if (_ntl_gscompare(e, -1) == 0) { - _ntl_ginvmod(g, F, h); + if (_ntl_gscompare(e, 2) == 0) { + _ntl_gsqmod(g, F, h); return; } - if (_ntl_gscompare(e, 2) == 0) { - _ntl_gsqmod(g, F, h); + if (ZEROP(g)) { + _ntl_gzero(h); return; } - if (_ntl_gscompare(e, -2) == 0) { - res = 0; - _ntl_gsqmod(g, F, &res); - _ntl_ginvmod(res, F, h); + long n = _ntl_g2log(e); + +#if (1 && defined(NTL_GMP_LIP) && NTL_NAIL_BITS == 0) + if (n > 10) { + if (SIZE(F) < 6 && SIZE(e) < 10) + _ntl_gmp_powermod_alt(g, e, F, h); + else + _ntl_gmp_powermod(g, e, F, h); return; } +#endif + + _ntl_gbigint_wrapped res, gg, t; + UniqueArray<_ntl_gbigint_wrapped> v; - n = _ntl_g2log(e); + long i, k, val, cnt, m; + long use_redc, sF; + _ntl_limb_t inv; sF = SIZE(F); @@ -5757,8 +5838,6 @@ } } - if (_ntl_gsign(e) < 0) _ntl_ginvmod(res, F, &res); - _ntl_gcopy(res, h); return; } @@ -5788,8 +5867,6 @@ } } - if (_ntl_gsign(e) < 0) _ntl_ginvmod(res, F, &res); - _ntl_gcopy(res, h); return; } @@ -5860,8 +5937,6 @@ } } - if (_ntl_gsign(e) < 0) _ntl_ginvmod(res, F, &res); - _ntl_gcopy(res, h); }
