Changeset 287cc8 in git


Ignore:
Timestamp:
Jan 5, 2010, 5:51:13 PM (14 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '45e267b9942dec9429fe249ce3e5e44ab80a6a3a')
Children:
3c38b3810fd61108b01f123f5a91e13ccff52b20
Parents:
1d43d184dd871d77c1ba8e095d768f22a0fbe92f
Message:
ntl 5.5.2

git-svn-id: file:///usr/local/Singular/svn/trunk@12402 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
ntl
Files:
99 edited

Legend:

Unmodified
Added
Removed
  • ntl/COPYING

    r1d43d18 r287cc8  
    11
    22                  COPYRIGHT NOTICE
    3                     for NTL 5.4
     3                    for NTL 5.5
    44          (modified for Singular 2-0-6 - 3-1)
    55
    66NTL -- A Library for Doing Number Theory
    7 Copyright (C) 1996-2005  Victor Shoup
     7Copyright (C) 1996-2009  Victor Shoup
    88
    99The most recent version of NTL is available at http://www.shoup.net
  • ntl/doc/ZZ.txt

    r1d43d18 r287cc8  
    141141// PROMOTIONS: operator * and procedure mul support promotion
    142142// from long to ZZ on (a, b).
     143
     144/**************************************************************************\
     145
     146                            Combined Multiply and Add
     147
     148\**************************************************************************/
     149
     150
     151void MulAddTo(ZZ& x, const ZZ& a, const ZZ& b); // x += a*b
     152void MulAddTo(ZZ& x, const ZZ& a, long b);      // x += a*b
     153
     154
     155void MulSubFrom(ZZ& x, const ZZ& a, const ZZ& b); // x -= a*b
     156void MulSubFrom(ZZ& x, const ZZ& a, long b);      // x -= a*b
     157
     158// NOTE: these are provided for both convenience and efficiency.
     159// The single-precision versions may be significantly
     160// faster than the code sequence
     161//   mul(tmp, a, b); add(x, x, tmp);
     162
    143163
    144164
  • ntl/doc/tour-changes.html

    r1d43d18 r287cc8  
    1717</p>
    1818</h1>
     19
     20<p> <hr> <p>
     21<h3>
     222009.08.14: Changes between NTL 5.5.1 and 5.5.2
     23</h3>
     24
     25<ul>
     26<li>
     27New routines <tt>MulAddTo</tt> and <tt>MulSubFrom</tt>
     28for computing <tt>x += a*b</tt> and <tt>x -= a*b</tt>,
     29where <tt>x</tt> and <tt>a</tt> are <tt>ZZ</tt>'s and
     30<tt>b</tt> is a <tt>ZZ</tt> or a <tt>long</tt>.
     31In the case where <tt>b</tt> is a <tt>long</tt>,
     32this may be much faster than writing
     33<tt>mul(t, a, b); add(x, x, t)</tt>.
     34See <a href="ZZ.txt">ZZ.txt</a> for details.
     35
     36These new routines are used in a number of places in
     37NTL to get faster algorithms (for example, the <tt>LLL</tt> routine).
     38
     39<li>
     40Fixed a relatively benign indexing bug in <tt>GF2EX</tt>
     41discovered by Berend-Benjamin Tams using the <tt>valgrind</tt> tool.
     42
     43
     44
     45
     46</ul>
    1947
    2048<p> <hr> <p>
  • ntl/doc/tour-unix.html

    r1d43d18 r287cc8  
    502502in this case, you will want to set
    503503<tt>LIBTOOL=glibtool</tt>. 
    504 On other systems, it may be necssary to downlaod and
     504On other systems, it may be necssary to download and
    505505install a fresh copy of the libtool program (which can be obtained from
    506506<a href="http://www.gnu.org/software/libtool">here</a>).
  • ntl/include/NTL/ZZ.h

    r1d43d18 r287cc8  
    421421  { mul(x, x, a); return x; }
    422422
     423// x += a*b
     424
     425inline void
     426MulAddTo(ZZ& x, const ZZ& a, long b)
     427{
     428   NTL_zsaddmul(a.rep, b, &x.rep);
     429}
     430
     431inline void
     432MulAddTo(ZZ& x, const ZZ& a, const ZZ& b)
     433{
     434   NTL_zaddmul(a.rep, b.rep, &x.rep);
     435}
     436
     437// x -= a*b
     438
     439inline void
     440MulSubFrom(ZZ& x, const ZZ& a, long b)
     441{
     442   NTL_zssubmul(a.rep, b, &x.rep);
     443}
     444
     445inline void
     446MulSubFrom(ZZ& x, const ZZ& a, const ZZ& b)
     447{
     448   NTL_zsubmul(a.rep, b.rep, &x.rep);
     449}
     450
    423451
    424452// Special routines for implementing CRT in ZZ_pX arithmetic
  • ntl/include/NTL/c_lip.h

    r1d43d18 r287cc8  
    193193          The division is performed in place (but may sometimes
    194194          cause *r to grow by one digit) */
     195
     196    void _ntl_zsaddmul(_ntl_verylong x, long y,  _ntl_verylong *ww);
     197      /* *ww += x*y */
     198
     199    void _ntl_zaddmul(_ntl_verylong x, _ntl_verylong y,  _ntl_verylong *ww);
     200      /* *ww += x*y */
     201
     202    void _ntl_zssubmul(_ntl_verylong x, long y,  _ntl_verylong *ww);
     203      /* *ww -= x*y */
     204
     205    void _ntl_zsubmul(_ntl_verylong x, _ntl_verylong y,  _ntl_verylong *ww);
     206      /* *ww -= x*y */
     207
    195208
    196209/********************************************************************
     
    642655#define NTL_zzero _ntl_zzero1
    643656
     657#define NTL_zsaddmul _ntl_zsaddmul
     658#define NTL_zaddmul _ntl_zaddmul
     659#define NTL_zssubmul _ntl_zssubmul
     660#define NTL_zsubmul _ntl_zsubmul
     661
  • ntl/include/NTL/g_lip.h

    r1d43d18 r287cc8  
    9595          assumes b > 0 and *r >= 0;
    9696          cause *r to grow by one digit) */
     97
     98    void _ntl_gsaddmul(_ntl_gbigint x, long y,  _ntl_gbigint *ww);
     99      /* *ww += x*y */
     100
     101    void _ntl_gaddmul(_ntl_gbigint x, _ntl_gbigint y,  _ntl_gbigint *ww);
     102      /* *ww += x*y */
     103
     104    void _ntl_gssubmul(_ntl_gbigint x, long y,  _ntl_gbigint *ww);
     105      /* *ww -= x*y */
     106
     107    void _ntl_gsubmul(_ntl_gbigint x, _ntl_gbigint y,  _ntl_gbigint *ww);
     108      /* *ww -= x*y */
     109
    97110
    98111/********************************************************************
     
    529542#define NTL_zzero _ntl_gzero
    530543
     544#define NTL_zsaddmul _ntl_gsaddmul
     545#define NTL_zaddmul _ntl_gaddmul
     546#define NTL_zssubmul _ntl_gssubmul
     547#define NTL_zsubmul _ntl_gsubmul
     548
    531549#define NTL_GMP_LIP
    532550
  • ntl/include/NTL/tools.h

    r1d43d18 r287cc8  
    251251#endif
    252252long IsWhiteSpace(long c);
     253long IsEOFChar(long c);
    253254
    254255long CharToIntVal(long c);
  • ntl/include/NTL/version.h

    r1d43d18 r287cc8  
    33#define NTL_version__H
    44
    5 #define NTL_VERSION "5.5.1"
     5#define NTL_VERSION "5.5.2"
    66
    77#define NTL_MAJOR_VERSION  (5)
    88#define NTL_MINOR_VERSION  (5)
    9 #define NTL_REVISION       (1)
     9#define NTL_REVISION       (2)
    1010
    1111#endif
  • ntl/src/CanZassTest.c

    r1d43d18 r287cc8  
    7373
    7474   cerr << "\n";
    75  
     75
    7676
    7777   cout << factors << "\n";
  • ntl/src/DIRNAME

    r1d43d18 r287cc8  
    1 ntl-5.5.1
     1ntl-5.5.2
  • ntl/src/DoConfig

    r1d43d18 r287cc8  
    8686
    8787
     88%Variable = ();
     89
     90
    8891foreach $arg (@ARGV) {
    8992
     
    9497
    9598   if (($name, $val) = ($arg =~ /(.*?)=(.*)/)) {
     99
     100      $Variable{$name} = 0;
    96101     
    97102      if (exists($MakeFlag{$name}) && ($val =~ 'on|off')) {
     
    139144}
    140145
    141 # a special MakeVal value that is determined by NTL_GMP_LIP
    142 # and NTL_GMP_HACK
    143 
     146# special GMP variables
     147
     148$MakeVal{'GMPI'} = '# ';
     149$MakeVal{'GMPL'} = '# ';
     150$MakeVal{'GMP'} =  '# ';
    144151
    145152if ($ConfigFlag{'NTL_GMP_LIP'} eq 'on' || $ConfigFlag{'NTL_GMP_HACK'} eq 'on') {
    146153   $MakeVal{'GMP'} = '';
    147 }
    148 else {
    149    $MakeVal{'GMP'} = '# ';
    150 }
    151 
    152 # a special MakeVal value that is determined by NTL_GF2X_LIB
     154   if (exists($Variable{'DEF_PREFIX'}) ||
     155       exists($Variable{'GMP_PREFIX'}) ||
     156       exists($Variable{'GMP_INCDIR'})) {
     157      $MakeVal{'GMPI'} = '';
     158   }
     159   if (exists($Variable{'DEF_PREFIX'}) ||
     160       exists($Variable{'GMP_PREFIX'}) ||
     161       exists($Variable{'GMP_LIBDIR'})) {
     162      $MakeVal{'GMPL'} = '';
     163   }
     164}
     165
     166# special GF2X variables
     167
     168
     169$MakeVal{'GF2XI'} = '# ';
     170$MakeVal{'GF2XL'} = '# ';
     171$MakeVal{'GF2X'} =  '# ';
    153172
    154173
    155174if ($ConfigFlag{'NTL_GF2X_LIB'} eq 'on') {
    156175   $MakeVal{'GF2X'} = '';
    157 }
    158 else {
    159    $MakeVal{'GF2X'} = '# ';
     176   if (exists($Variable{'DEF_PREFIX'}) ||
     177       exists($Variable{'GF2X_PREFIX'}) ||
     178       exists($Variable{'GF2X_INCDIR'})) {
     179      $MakeVal{'GF2XI'} = '';
     180   }
     181   if (exists($Variable{'DEF_PREFIX'}) ||
     182       exists($Variable{'GF2X_PREFIX'}) ||
     183       exists($Variable{'GF2X_LIBDIR'})) {
     184      $MakeVal{'GF2XL'} = '';
     185   }
    160186}
    161187
  • ntl/src/FFT.c

    r1d43d18 r287cc8  
    2929
    3030   if (n % 7 == 0) return 0;
    31    
     31
    3232   m = n - 1;
    3333   k = 0;
     
    5454      if (z != 1 || y !=  n-1) return 0;
    5555
    56       if (j == k) 
     56      if (j == k)
    5757         break;
    5858   }
     
    6565   if (TrialBound > 0) {
    6666      if (!ProbPrime(n, 5)) return 0;
    67    
     67
    6868      /* we have to do trial division by special numbers */
    69    
     69
    7070      TrialBound = SqrRoot(TrialBound);
    71    
     71
    7272      long a, b;
    73    
     73
    7474      for (a = 1; a <= TrialBound; a++) {
    7575         b = (a << k) + 1;
    76          if (n % b == 0) return 0; 
     76         if (n % b == 0) return 0;
    7777      }
    7878   }
     
    127127      return NTL_FFTMaxRoot;
    128128   else
    129       return k; 
     129      return k;
    130130}
    131131
     
    146146   // tables are allocated in increments of 100
    147147
    148    if (index == 0) { 
     148   if (index == 0) {
    149149      FFTPrime = (long *) NTL_MALLOC(100, sizeof(long), 0);
    150150      RootTable = (long **) NTL_MALLOC(100, sizeof(long *), 0);
     
    155155   else if ((index % 100) == 0) {
    156156      FFTPrime = (long *) NTL_REALLOC(FFTPrime, index+100, sizeof(long), 0);
    157       RootTable = (long **) 
     157      RootTable = (long **)
    158158                  NTL_REALLOC(RootTable, index+100, sizeof(long *), 0);
    159       RootInvTable = (long **) 
     159      RootInvTable = (long **)
    160160                     NTL_REALLOC(RootInvTable, index+100, sizeof(long *), 0);
    161       TwoInvTable = (long **) 
     161      TwoInvTable = (long **)
    162162                    NTL_REALLOC(TwoInvTable, index+100, sizeof(long *), 0);
    163       FFTPrimeInv = (double *) 
     163      FFTPrimeInv = (double *)
    164164                    NTL_REALLOC(FFTPrimeInv, index+100, sizeof(double), 0);
    165165   }
    166166
    167167   if (!FFTPrime || !RootTable || !RootInvTable || !TwoInvTable ||
    168        !FFTPrimeInv) 
     168       !FFTPrimeInv)
    169169      Error("out of space");
    170170
     
    200200   NumFFTPrimes++;
    201201}
    202    
     202
    203203
    204204static
     
    207207   long j, m;
    208208
    209    j = k; 
     209   j = k;
    210210   m = 1L << (k-1);
    211211
     
    272272   // assume k > 1
    273273
    274    
     274
    275275
    276276   static long tab_size = 0;
     
    282282
    283283      wtab = (long *) NTL_MALLOC(1L << (k-2), sizeof(long), 0);
    284       wqinvtab = (mulmod_precon_t *) 
     284      wqinvtab = (mulmod_precon_t *)
    285285                 NTL_MALLOC(1L << (k-2), sizeof(mulmod_precon_t), 0);
    286286      if (!wtab || !wqinvtab) Error("out of space");
     
    290290
    291291      wtab = (long *) NTL_REALLOC(wtab, 1L << (k-2), sizeof(long), 0);
    292       wqinvtab = (mulmod_precon_t *) 
     292      wqinvtab = (mulmod_precon_t *)
    293293                 NTL_REALLOC(wqinvtab, 1L << (k-2), sizeof(mulmod_precon_t), 0);
    294294      if (!wtab || !wqinvtab) Error("out of space");
     
    320320   }
    321321
    322    
    323  
     322
     323
    324324   for (s = 2; s < k; s++) {
    325325      m = 1L << s;
     
    341341      for (i = 0; i < n; i+= m) {
    342342
    343          
     343
    344344         t = A[i + m_half];
    345345         u = A[i];
     
    402402      t = MulModPrecon(A[j + m_half], wtab[j >> 1], q, wqinvtab[j >> 1]);
    403403      u = A[j];
    404       t1 = MulModPrecon(A[j + 1+ m_half], wtab[j >> 1], q, 
     404      t1 = MulModPrecon(A[j + 1+ m_half], wtab[j >> 1], q,
    405405                        wqinvtab[j >> 1]);
    406406      t1 = MulModPrecon(t1, w, q, wqinv);
     
    411411      A[j + 1] = AddMod(u1, t1, q);
    412412      A[j + 1 + m_half] = SubMod(u1, t1, q);
    413      
     413
    414414   }
    415415}
  • ntl/src/FacVec.c

    r1d43d18 r287cc8  
    6060            (fvec[NumFactors].a)++;
    6161            fvec[NumFactors].val *= q;
    62          }         
     62         }
    6363         fvec[NumFactors].link = -1;
    6464         NumFactors++;
  • ntl/src/GF2.c

    r1d43d18 r287cc8  
    3838   }
    3939
    40    if (e < 0 && a == 0) 
     40   if (e < 0 && a == 0)
    4141      Error("GF2: division by zero");
    4242
  • ntl/src/GF2E.c

    r1d43d18 r287cc8  
    2626   else if (p.size == 6)
    2727      KarCross = 3;
    28    else 
     28   else
    2929      KarCross = 2;
    3030
     
    5757   else if (p.size <= 13)
    5858      DivCross = 100;
    59    else 
     59   else
    6060      DivCross = 75;
    6161
     
    8080
    8181
    82 GF2EInfoT *GF2EInfo = 0; 
     82GF2EInfoT *GF2EInfo = 0;
    8383
    8484
     
    8787
    8888
    89 static 
     89static
    9090void CopyPointer(GF2EInfoPtr& dst, GF2EInfoPtr src)
    9191{
     
    9595      dst->ref_count--;
    9696
    97       if (dst->ref_count < 0) 
     97      if (dst->ref_count < 0)
    9898         Error("internal error: negative GF2EContext ref_count");
    9999
     
    102102
    103103   if (src) {
    104       if (src->ref_count == NTL_MAX_LONG) 
     104      if (src->ref_count == NTL_MAX_LONG)
    105105         Error("internal error: GF2EContext ref_count overflow");
    106106
     
    111111   dst = src;
    112112}
    113    
     113
    114114
    115115
  • ntl/src/GF2EX.c

    r1d43d18 r287cc8  
    5656   long j, m;
    5757
    58    if (i < 0) 
     58   if (i < 0)
    5959      Error("SetCoeff: negative index");
    6060
     
    6363
    6464   m = deg(x);
     65
     66   if (i > m && IsZero(a)) return;
    6567
    6668   if (i > m) {
     
    114116   long j, m;
    115117
    116    if (i < 0) 
     118   if (i < 0)
    117119      Error("coefficient index out of range");
    118120
     
    143145   return deg(a) == 1 && IsOne(LeadCoeff(a)) && IsZero(ConstTerm(a));
    144146}
    145      
    146      
     147
     148
    147149
    148150const GF2E& coeff(const GF2EX& a, long i)
     
    210212{
    211213   GF2X a = aa; // in case a aliases the rep of a coefficient of x
    212    
     214
    213215   long n = deg(a)+1;
    214216   long i;
     
    235237
    236238   long i;
    237    const GF2E *ap, *bp; 
     239   const GF2E *ap, *bp;
    238240   GF2E* xp;
    239241
     
    326328   const GF2E *ap, *bp;
    327329   GF2E *xp;
    328    
     330
    329331   GF2EX la, lb;
    330332
     
    388390
    389391
    390 static 
     392static
    391393void PlainMul1(GF2X *xp, const GF2X *ap, long sa, const GF2X& b)
    392394{
     
    506508
    507509static
    508 void KarMul(GF2X *c, const GF2X *a, 
     510void KarMul(GF2X *c, const GF2X *a,
    509511            long sa, const GF2X *b, long sb, GF2X *stk)
    510512{
     
    514516   }
    515517
    516    if (sb == 1) { 
    517       if (sa == 1) 
     518   if (sb == 1) {
     519      if (sa == 1)
    518520         mul(*c, *a, *b);
    519521      else
     
    531533      q_add(c[1], c[1], c[0]);
    532534      q_add(c[1], c[1], c[2]);
    533      
     535
    534536      return;
    535537   }
     
    618620         cp[i] = (ap[i+wn] >> bn) | (ap[i+wn+1] << (NTL_BITS_PER_LONG - bn));
    619621
    620       if ((k + n) % NTL_BITS_PER_LONG != 0)
     622      if (k > sc*NTL_BITS_PER_LONG - bn)
    621623         cp[sc-1] = (ap[sc+wn-1] >> bn)|(ap[sc+wn] << (NTL_BITS_PER_LONG - bn));
    622624      else
     
    625627
    626628   long p = k % NTL_BITS_PER_LONG;
    627    if (p != 0) 
     629   if (p != 0)
    628630      cp[sc-1] &= ((1UL << p) - 1UL);
    629631
     
    649651      paa[i] = 0;
    650652
    651    for (i = 0; i < sa; i++) 
     653   for (i = 0; i < sa; i++)
    652654      ShiftAdd(paa, rep(a.rep[i]).xrep.elts(), rep(a.rep[i]).xrep.length(),
    653655               blocksz*i);
    654656
    655    aa.normalize(); 
     657   aa.normalize();
    656658}
    657659
     
    736738      return;
    737739   }
    738    
     740
    739741
    740742   /* karatsuba */
     
    751753
    752754   GF2XVec stk;
    753    stk.SetSize(sp + 2*(sa+sb)-1, 2*GF2E::WordLength()); 
     755   stk.SetSize(sp + 2*(sa+sb)-1, 2*GF2E::WordLength());
    754756
    755757   long i;
     
    761763      stk[i+2*sa+sb-1] = rep(b.rep[i]);
    762764
    763    KarMul(&stk[0], &stk[sa+sb-1], sa, &stk[2*sa+sb-1], sb, 
     765   KarMul(&stk[0], &stk[sa+sb-1], sa, &stk[2*sa+sb-1], sb,
    764766          &stk[2*(sa+sb)-1]);
    765767
     
    11681170
    11691171
    1170    inv(t, LeadCoeff(x)); 
    1171    mul(x, x, t); 
    1172 }
    1173 
    1174 
    1175 
    1176          
     1172   inv(t, LeadCoeff(x));
     1173   mul(x, x, t);
     1174}
     1175
     1176
     1177
     1178
    11771179
    11781180void XGCD(GF2EX& d, GF2EX& s, GF2EX& t, const GF2EX& a, const GF2EX& b)
     
    11941196      long e = max(deg(a), deg(b)) + 1;
    11951197
    1196       GF2EX temp(INIT_SIZE, e), u(INIT_SIZE, e), v(INIT_SIZE, e), 
    1197             u0(INIT_SIZE, e), v0(INIT_SIZE, e), 
    1198             u1(INIT_SIZE, e), v1(INIT_SIZE, e), 
     1198      GF2EX temp(INIT_SIZE, e), u(INIT_SIZE, e), v(INIT_SIZE, e),
     1199            u0(INIT_SIZE, e), v0(INIT_SIZE, e),
     1200            u1(INIT_SIZE, e), v1(INIT_SIZE, e),
    11991201            u2(INIT_SIZE, e), v2(INIT_SIZE, e), q(INIT_SIZE, e);
    12001202
     
    12361238void MulMod(GF2EX& x, const GF2EX& a, const GF2EX& b, const GF2EX& f)
    12371239{
    1238    if (deg(a) >= deg(f) || deg(b) >= deg(f) || deg(f) == 0) 
     1240   if (deg(a) >= deg(f) || deg(b) >= deg(f) || deg(f) == 0)
    12391241      Error("MulMod: bad args");
    12401242
     
    13501352
    13511353   for (i = 0; i < n; i++)
    1352       random(x.rep[i]); 
     1354      random(x.rep[i]);
    13531355
    13541356   x.normalize();
     
    13811383
    13821384   x.normalize();
    1383 } 
     1385}
    13841386
    13851387
     
    13871389void trunc(GF2EX& x, const GF2EX& a, long m)
    13881390
    1389 // x = a % X^m, output may alias input 
     1391// x = a % X^m, output may alias input
    13901392
    13911393{
     
    17911793   return k;
    17921794}
    1793      
     1795
    17941796
    17951797
     
    18571859
    18581860   v[0] = g;
    1859  
     1861
    18601862   if (k > 1) {
    18611863      GF2EX t;
     
    18731875   val = 0;
    18741876   for (i = n-1; i >= 0; i--) {
    1875       val = (val << 1) | bit(e, i); 
     1877      val = (val << 1) | bit(e, i);
    18761878      if (val == 0)
    18771879         SqrMod(res, res, F);
     
    19051907}
    19061908
    1907    
     1909
    19081910
    19091911
     
    19381940
    19391941
    1940      
     1942
    19411943
    19421944
     
    19581960   mul(P1, P2, b);
    19591961   add(P1, P1, a);
    1960    
     1962
    19611963   r = P1;
    19621964}
     
    19791981   mul(P1, P2, b);
    19801982   add(P1, P1, a);
    1981    
     1983
    19821984   r = P1;
    19831985   q = P2;
     
    19992001   mul(P2, P1, P2);
    20002002   RightShift(P2, P2, da-db);
    2001    
     2003
    20022004   q = P2;
    20032005}
     
    20592061   q = a;
    20602062}
    2061    
     2063
    20622064
    20632065
     
    21212123   long da = deg(a);
    21222124   long i;
    2123  
     2125
    21242126   if (da < n) {
    21252127      clear(x);
     
    21472149
    21482150   if (n < 0) {
    2149       if (n < -NTL_MAX_LONG) 
     2151      if (n < -NTL_MAX_LONG)
    21502152         clear(x);
    21512153      else
     
    22142216      mul(a[0], a[0], b);
    22152217   }
    2216 } 
     2218}
    22172219
    22182220
     
    22662268   b.SetLength(m);
    22672269   long i;
    2268    for (i = 0; i < m; i++) 
     2270   for (i = 0; i < m; i++)
    22692271      eval(b[i], f, a[i]);
    22702272}
     
    23412343}
    23422344
    2343    
    2344 void InnerProduct(GF2EX& x, const vec_GF2E& v, long low, long high, 
     2345
     2346void InnerProduct(GF2EX& x, const vec_GF2E& v, long low, long high,
    23452347                   const vec_GF2EX& H, long n, GF2XVec& t)
    23462348{
     
    23702372
    23712373
    2372 void CompMod(GF2EX& x, const GF2EX& g, const GF2EXArgument& A, 
     2374void CompMod(GF2EX& x, const GF2EX& g, const GF2EXArgument& A,
    23732375             const GF2EXModulus& F)
    23742376{
     
    24202422   set(A.H[0]);
    24212423   A.H[1] = h;
    2422    for (i = 2; i <= m; i++) 
     2424   for (i = 2; i <= m; i++)
    24232425      MulMod(A.H[i], A.H[i-1], h, F);
    24242426}
     
    24752477}
    24762478
    2477 void Comp3Mod(GF2EX& x1, GF2EX& x2, GF2EX& x3, 
     2479void Comp3Mod(GF2EX& x1, GF2EX& x2, GF2EX& x3,
    24782480              const GF2EX& g1, const GF2EX& g2, const GF2EX& g3,
    24792481              const GF2EX& h, const GF2EXModulus& F)
     
    25272529      B.shamt_fbi = 0;
    25282530   else
    2529       B.shamt_fbi = F.n-2 - d; 
     2531      B.shamt_fbi = F.n-2 - d;
    25302532
    25312533   CopyReverse(B.fbi, t, d);
    25322534
    2533    // The following code optimizes the case when 
     2535   // The following code optimizes the case when
    25342536   // f = X^n + low degree poly
    25352537
     
    25742576
    25752577
    2576 void UpdateMap(vec_GF2E& x, const vec_GF2E& a, 
     2578void UpdateMap(vec_GF2E& x, const vec_GF2E& a,
    25772579         const GF2EXTransMultiplier& B, const GF2EXModulus& F)
    25782580{
     
    25812583   x = xx.rep;
    25822584}
    2583    
     2585
    25842586
    25852587
    25862588static
    2587 void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, 
     2589void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k,
    25882590                   const GF2EXArgument& H, const GF2EXModulus& F)
    25892591{
    2590    if (k < 0 || NTL_OVERFLOW(k, 1, 0) || deg(a) >= F.n) 
     2592   if (k < 0 || NTL_OVERFLOW(k, 1, 0) || deg(a) >= F.n)
    25912593      Error("ProjectPowers: bad args");
    25922594
     
    26142616
    26152617static
    2616 void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, const GF2EX& h, 
     2618void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, const GF2EX& h,
    26172619                   const GF2EXModulus& F)
    26182620{
     
    26392641}
    26402642
    2641 void ProjectPowers(vec_GF2E& x, const vec_GF2E& a, long k, 
     2643void ProjectPowers(vec_GF2E& x, const vec_GF2E& a, long k,
    26422644                   const GF2EX& h, const GF2EXModulus& F)
    26432645{
     
    27042706   }
    27052707
    2706    // cerr << "finished: " << L << " " << deg(Lambda) << "\n"; 
     2708   // cerr << "finished: " << L << " " << deg(Lambda) << "\n";
    27072709
    27082710   dl = deg(Lambda);
     
    27262728
    27272729
    2728 void DoMinPolyMod(GF2EX& h, const GF2EX& g, const GF2EXModulus& F, long m, 
     2730void DoMinPolyMod(GF2EX& h, const GF2EX& g, const GF2EXModulus& F, long m,
    27292731               const GF2EX& R)
    27302732{
     
    27702772   GF2EX R;
    27712773   GF2EXTransMultiplier H1;
    2772    
     2774
    27732775
    27742776   for (;;) {
     
    28392841   GF2EX lq, r;
    28402842   DivRem(lq, r, a, b);
    2841    if (!IsZero(r)) return 0; 
     2843   if (!IsZero(r)) return 0;
    28422844   q = lq;
    28432845   return 1;
     
    28492851   GF2EX lq, r;
    28502852   DivRem(lq, r, a, b);
    2851    if (!IsZero(r)) return 0; 
     2853   if (!IsZero(r)) return 0;
    28522854   return 1;
    28532855}
     
    29142916   res.SetMaxLength(da*e + 1);
    29152917   res = 1;
    2916    
     2918
    29172919   long k = NumBits(e);
    29182920   long i;
     
    30253027      Error("trace: bad args");
    30263028
    3027    if (F.tracevec.length() == 0) 
     3029   if (F.tracevec.length() == 0)
    30283030      ComputeTraceVec(F);
    30293031
     
    30433045{
    30443046   GF2E res;
    3045  
     3047
    30463048   if (IsZero(a) || IsZero(b))
    30473049      clear(res);
    3048    else if (deg(a) == 0 && deg(b) == 0) 
     3050   else if (deg(a) == 0 && deg(b) == 0)
    30493051      set(res);
    30503052   else {
     
    30813083            else
    30823084               clear(res);
    3083        
     3085
    30843086            break;
    30853087         }
     
    30923094void resultant(GF2E& rres, const GF2EX& a, const GF2EX& b)
    30933095{
    3094    PlainResultant(rres, a, b); 
     3096   PlainResultant(rres, a, b);
    30953097}
    30963098
     
    30983100void NormMod(GF2E& x, const GF2EX& a, const GF2EX& f)
    30993101{
    3100    if (deg(f) <= 0 || deg(a) >= deg(f)) 
     3102   if (deg(f) <= 0 || deg(a) >= deg(f))
    31013103      Error("norm: bad args");
    31023104
     
    31793181
    31803182
    3181 void CompTower(GF2EX& x, const GF2X& g, const GF2EX& h, 
     3183void CompTower(GF2EX& x, const GF2X& g, const GF2EX& h,
    31823184             const GF2EXModulus& F)
    31833185   // x = g(h) mod f
     
    32133215}
    32143216
    3215 void ProjectedInnerProduct(GF2& x, const vec_GF2E& a, 
     3217void ProjectedInnerProduct(GF2& x, const vec_GF2E& a,
    32163218                           const vec_vec_GF2& b)
    32173219{
     
    33173319
    33183320   ProjectPowersTower(x, R, 2*m, g, F, proj);
    3319    
     3321
    33203322   MinPolySeq(h, x, m);
    33213323}
    33223324
    33233325
    3324 void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F, 
     3326void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F,
    33253327                      long m)
    33263328{
     
    33393341}
    33403342
    3341 void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F, 
     3343void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F,
    33423344                      long m, const vec_GF2& proj)
    33433345{
     
    33803382   vec_GF2E R;
    33813383   GF2EXTransMultiplier H1;
    3382    
     3384
    33833385
    33843386   for (;;) {
     
    33933395      CompTower(h3, h2, g, F);
    33943396      MulMod(h1, h3, h1, F);
    3395       if (IsZero(h1)) { 
    3396          hh = h; 
    3397          return; 
     3397      if (IsZero(h1)) {
     3398         hh = h;
     3399         return;
    33983400      }
    33993401   }
  • ntl/src/GF2EXFactoring.c

    r1d43d18 r287cc8  
    2929   c = res;
    3030}
    31    
     31
    3232
    3333
     
    7979         d = deg(r)/2;
    8080         f.rep.SetLength(d+1);
    81          for (k = 0; k <= d; k++) 
     81         for (k = 0; k <= d; k++)
    8282            IterSqr(f.rep[k], r.rep[k*2], GF2E::degree()-1);
    8383         m = m*2;
     
    8585   } while (!finished);
    8686}
    87          
     87
    8888
    8989
     
    216216   SetX(res);
    217217   long i;
    218    for (i = 0; i < GF2E::degree(); i++) 
     218   for (i = 0; i < GF2E::degree(); i++)
    219219      SqrMod(res, res, F);
    220220
     
    241241         long m1 = 2*m;
    242242         if (i & d) m1++;
    243    
     243
    244244         if (m1 >= NTL_BITS_PER_LONG-1 || (1L << m1) >= n) break;
    245    
     245
    246246         m = m1;
    247247         i = i >> 1;
     
    290290         long m1 = 2*m;
    291291         if (i & d) m1++;
    292    
     292
    293293         if (m1 >= NTL_BITS_PER_LONG-1 || (1L << m1) >= n) break;
    294    
     294
    295295         m = m1;
    296296         i = i >> 1;
     
    344344
    345345
    346    
     346
    347347
    348348
     
    359359      return;
    360360   }
    361      
     361
    362362   GF2EX h;
    363363
    364364   GF2E r;
    365365
    366    
     366
    367367   {
    368368      GF2EXModulus F;
     
    379379
    380380   RecFindRoots(x, h);
    381    div(h, f, h); 
     381   div(h, f, h);
    382382   RecFindRoots(x, h);
    383383}
     
    435435static
    436436void split(GF2EX& f1, GF2EX& g1, GF2EX& f2, GF2EX& g2,
    437            const GF2EX& f, const GF2EX& g, 
     437           const GF2EX& f, const GF2EX& g,
    438438           const vec_GF2E& roots, long lo, long mid)
    439439{
     
    456456
    457457   GCD(f1, a, f);
    458    
     458
    459459   div(f2, f, f1);
    460460
     
    520520
    521521
    522    
     522
    523523
    524524void SFBerlekamp(vec_GF2EX& factors, const GF2EX& ff, long verbose)
     
    619619      Error("berlekamp: bad args");
    620620
    621    
     621
    622622   SquareFreeDecomp(sfd, f);
    623623
     
    644644
    645645static
    646 void ProcessTable(GF2EX& f, vec_pair_GF2EX_long& factors, 
     646void ProcessTable(GF2EX& f, vec_pair_GF2EX_long& factors,
    647647                  const GF2EXModulus& F, long limit, const vec_GF2EX& tbl,
    648648                  long d, long verbose)
     
    681681
    682682   while (2*d <= deg(t1)) {
    683       GCD(t2, tbl[i], t1); 
     683      GCD(t2, tbl[i], t1);
    684684      if (deg(t2) > 0) {
    685685         AddFactor(factors, t2, d, verbose);
     
    696696
    697697
    698 void TraceMap(GF2EX& w, const GF2EX& a, long d, const GF2EXModulus& F, 
     698void TraceMap(GF2EX& w, const GF2EX& a, long d, const GF2EXModulus& F,
    699699              const GF2EX& b)
    700700
     
    710710   while (d) {
    711711      if (d == 1) {
    712          if (IsZero(w)) 
     712         if (IsZero(w))
    713713            w = y;
    714714         else {
     
    817817long GF2EX_BlockingFactor = 10;
    818818
    819 void DDF(vec_pair_GF2EX_long& factors, const GF2EX& ff, const GF2EX& hh, 
     819void DDF(vec_pair_GF2EX_long& factors, const GF2EX& ff, const GF2EX& hh,
    820820         long verbose)
    821821{
     
    836836   }
    837837
    838    long CompTableSize = 2*SqrRoot(deg(f)); 
     838   long CompTableSize = 2*SqrRoot(deg(f));
    839839
    840840   long GCDTableSize = GF2EX_BlockingFactor;
     
    876876
    877877         if (deg(f) < old_n) {
    878             // f has changed 
     878            // f has changed
    879879
    880880            build(F, f);
     
    916916   GF2EXModulus F;
    917917   vec_GF2E roots;
    918    
     918
    919919   build(F, f);
    920920   long n = F.n;
     
    947947   }
    948948}
    949          
     949
    950950
    951951void EDF(vec_GF2EX& factors, const GF2EX& ff, const GF2EX& bb,
     
    978978   }
    979979
    980    
     980
    981981   factors.SetLength(0);
    982982
     
    10081008   double t;
    10091009
    1010    
     1010
    10111011   GF2EXModulus F;
    10121012   build(F, f);
     
    10501050   }
    10511051}
    1052    
     1052
    10531053void CanZass(vec_pair_GF2EX_long& factors, const GF2EX& f, long verbose)
    10541054{
     
    10601060   vec_GF2EX x;
    10611061
    1062    
     1062
    10631063   SquareFreeDecomp(sfd, f);
    10641064
     
    11211121
    11221122static
    1123 void TandemPowerCompose(GF2EX& y1, GF2EX& y2, const GF2EX& h, 
     1123void TandemPowerCompose(GF2EX& y1, GF2EX& y2, const GF2EX& h,
    11241124                        long q1, long q2, const GF2EXModulus& F)
    11251125{
     
    12011201   long q1, q2, r1, r2;
    12021202
    1203    q1 = fvec[fvec[u].link].val; 
     1203   q1 = fvec[fvec[u].link].val;
    12041204   q2 = fvec[fvec[u].link+1].val;
    12051205
     
    12101210}
    12111211
    1212    
     1212
    12131213
    12141214
     
    12181218   // the common degree of the irreducible factors of f is computed
    12191219{
    1220    if (F.n == 1 || IsX(h)) 
     1220   if (F.n == 1 || IsX(h))
    12211221      return 1;
    12221222
     
    12391239
    12401240   f = ff;
    1241    
     1241
    12421242   if (!IsOne(LeadCoeff(f)))
    12431243      Error("FindRoot: bad args");
     
    12611261      }
    12621262   }
    1263  
     1263
    12641264   root = ConstTerm(f);
    12651265}
     
    13081308
    13091309
    1310    q1 = fvec[fvec[u].link].val; 
     1310   q1 = fvec[fvec[u].link].val;
    13111311   q2 = fvec[fvec[u].link+1].val;
    13121312
    13131313   TandemPowerCompose(h1, h2, h, q1, q2, F);
    1314    return RecIrredTest(fvec[u].link, h2, F, fvec) 
     1314   return RecIrredTest(fvec[u].link, h2, F, fvec)
    13151315          && RecIrredTest(fvec[u].link+1, h1, F, fvec);
    13161316}
     
    13241324
    13251325   build(F, f);
    1326    
     1326
    13271327   GF2EX h;
    13281328
     
    13501350
    13511351   build(F, f);
    1352    
     1352
    13531353   GF2EX h;
    13541354
     
    16721672   long i;
    16731673
    1674    long HexOutput = GF2X::HexOutput; 
     1674   long HexOutput = GF2X::HexOutput;
    16751675   GF2X::HexOutput = 1;
    16761676
     
    17081708}
    17091709
    1710    
     1710
    17111711
    17121712
     
    17781778   }
    17791779}
    1780      
     1780
    17811781
    17821782
     
    18381838
    18391839         long i;
    1840          for (i = 1; i <= k-1; i++) 
     1840         for (i = 1; i <= k-1; i++)
    18411841            rem(BabyStep[i], BabyStep[i], F);
    18421842      }
     
    18471847   }
    18481848
    1849    if (deg(f) > 0) 
     1849   if (deg(f) > 0)
    18501850      NewAddFactor(u, f, 0, verbose);
    18511851
     
    19021902   NewProcessTable(factors, f, F, buf, size, first_d, 1, verbose);
    19031903
    1904    if (deg(f) > 0) 
     1904   if (deg(f) > 0)
    19051905      NewAddFactor(factors, f, deg(f), verbose);
    19061906}
    1907    
     1907
    19081908
    19091909
     
    19351935}
    19361936
    1937      
    1938      
    1939 
    1940      
     1937
     1938
     1939
     1940
    19411941
    19421942void NewDDF(vec_pair_GF2EX_long& factors,
     
    19621962   if (!GF2EX_stem[0])
    19631963      sprintf(GF2EX_stem, "ddf-%ld", RandomBnd(10000));
    1964      
     1964
    19651965   long B = deg(f)/2;
    19661966   long k = SqrRoot(B);
  • ntl/src/GF2X.c

    r1d43d18 r287cc8  
    5555}
    5656
    57 long IsZero(const GF2X& a) 
     57long IsZero(const GF2X& a)
    5858   { return a.xrep.length() == 0; }
    5959
     
    133133   x.xrep[wi] |= (1UL << bi);
    134134}
    135    
     135
    136136
    137137
     
    157157   long wi = i/NTL_BITS_PER_LONG;
    158158
    159    if (wi >= n) 
     159   if (wi >= n)
    160160      return;
    161161
     
    204204   return NTL_BITS_PER_LONG*(n-1) + i - 1;
    205205}
    206    
     206
    207207
    208208long operator==(const GF2X& a, const GF2X& b)
     
    213213long operator==(const GF2X& a, long b)
    214214{
    215    if (b & 1) 
     215   if (b & 1)
    216216      return IsOne(a);
    217217   else
     
    221221long operator==(const GF2X& a, GF2 b)
    222222{
    223    if (b == 1) 
     223   if (b == 1)
    224224      return IsOne(a);
    225225   else
     
    274274      x.xrep.QuickSetLength(i+1);
    275275   }
    276    
     276
    277277   else if (sa < sb) {
    278278      x.xrep.SetLength(sb);
     
    342342
    343343
    344 static 
     344static
    345345void mul1(_ntl_ulong *c, _ntl_ulong a, _ntl_ulong b)
    346346{
     
    368368}
    369369
    370 #define mul1_IL mul1_inline 
     370#define mul1_IL mul1_inline
    371371#endif
    372372
    373373
    374 static 
     374static
    375375void Mul1(_ntl_ulong *cp, const _ntl_ulong *bp, long sb, _ntl_ulong a)
    376376{
    377  
     377
    378378
    379379NTL_EFF_BB_MUL_CODE1
     
    382382}
    383383
    384 static 
     384static
    385385void AddMul1(_ntl_ulong *cp, const _ntl_ulong* bp, long sb, _ntl_ulong a)
    386386{
     
    393393
    394394
    395 static 
     395static
    396396void Mul1_short(_ntl_ulong *cp, const _ntl_ulong *bp, long sb, _ntl_ulong a)
    397397{
    398  
     398
    399399
    400400NTL_EFF_SHORT_BB_MUL_CODE1
     
    407407
    408408
    409 static 
     409static
    410410void mul_half(_ntl_ulong *c, _ntl_ulong a, _ntl_ulong b)
    411411{
     
    445445
    446446/*
    447  * This version of mul3 I got from Weimerskirch, Stebila, 
     447 * This version of mul3 I got from Weimerskirch, Stebila,
    448448 * and Shantz, "Generic GF(2^m) arithmetic in software
    449449 * an its application to ECC" (ACISP 2003).
     
    462462   mul1_IL(d12, a[1]^a[2], b[1]^b[2]);
    463463
    464    
     464
    465465   c[0] = d0[0];
    466466   c[1] = d0[1] ^ d01[0] ^ d1[0] ^ d0[0];
     
    484484
    485485   mul2(c, a, b);
    486    mul2(c+4, a+2, b+2); 
     486   mul2(c+4, a+2, b+2);
    487487   mul2(hl2, hs0, hs1);
    488488
     
    491491   hl2[2] = hl2[2] ^ c[2] ^ c[6];
    492492   hl2[3] = hl2[3] ^ c[3] ^ c[7];
    493    
     493
    494494   c[2] ^= hl2[0];
    495495   c[3] ^= hl2[1];
     
    504504   _ntl_ulong hl2[6];
    505505
    506    hs0[0] = a[0] ^ a[3]; 
     506   hs0[0] = a[0] ^ a[3];
    507507   hs0[1] = a[1] ^ a[4];
    508508   hs0[2] = a[2];
    509    hs1[0] = b[0] ^ b[3]; 
     509   hs1[0] = b[0] ^ b[3];
    510510   hs1[1] = b[1] ^ b[4];
    511511   hs1[2] = b[2];
    512512
    513    mul3(c, a, b); 
     513   mul3(c, a, b);
    514514   mul3(hl2, hs0, hs1);
    515515   mul2(c+6, a+3, b+3);
    516516
    517    hl2[0] = hl2[0] ^ c[0] ^ c[6]; 
     517   hl2[0] = hl2[0] ^ c[0] ^ c[6];
    518518   hl2[1] = hl2[1] ^ c[1] ^ c[7];
    519519   hl2[2] = hl2[2] ^ c[2] ^ c[8];
     
    522522   hl2[5] = hl2[5] ^ c[5];
    523523
    524  
     524
    525525   c[3] ^= hl2[0];
    526526   c[4] ^= hl2[1];
     
    537537   _ntl_ulong hl2[6];
    538538
    539    hs0[0] = a[0] ^ a[3];   
     539   hs0[0] = a[0] ^ a[3];
    540540   hs0[1] = a[1] ^ a[4];
    541541   hs0[2] = a[2] ^ a[5];
    542    hs1[0] = b[0] ^ b[3];   
     542   hs1[0] = b[0] ^ b[3];
    543543   hs1[1] = b[1] ^ b[4];
    544544   hs1[2] = b[2] ^ b[5];
    545545
    546    mul3(c, a, b);   
    547    mul3(c+6, a+3, b+3); 
    548    mul3(hl2, hs0, hs1); 
     546   mul3(c, a, b);
     547   mul3(c+6, a+3, b+3);
     548   mul3(hl2, hs0, hs1);
    549549
    550550   hl2[0] = hl2[0] ^ c[0] ^ c[6];
     
    554554   hl2[4] = hl2[4] ^ c[4] ^ c[10];
    555555   hl2[5] = hl2[5] ^ c[5] ^ c[11];
    556    
     556
    557557   c[3] ^= hl2[0];
    558558   c[4] ^= hl2[1];
     
    569569   _ntl_ulong hl2[8];
    570570
    571    hs0[0] = a[0] ^ a[4]; 
     571   hs0[0] = a[0] ^ a[4];
    572572   hs0[1] = a[1] ^ a[5];
    573573   hs0[2] = a[2] ^ a[6];
    574574   hs0[3] = a[3];
    575    hs1[0] = b[0] ^ b[4]; 
     575   hs1[0] = b[0] ^ b[4];
    576576   hs1[1] = b[1] ^ b[5];
    577577   hs1[2] = b[2] ^ b[6];
    578578   hs1[3] = b[3];
    579579
    580    mul4(c, a, b); 
     580   mul4(c, a, b);
    581581   mul4(hl2, hs0, hs1);
    582    mul3(c+8, a+4, b+4); 
     582   mul3(c+8, a+4, b+4);
    583583
    584584   hl2[0] = hl2[0] ^ c[0] ^ c[8];
     
    590590   hl2[6] = hl2[6] ^ c[6];
    591591   hl2[7] = hl2[7] ^ c[7];
    592    
     592
    593593   c[4]  ^= hl2[0];
    594594   c[5]  ^= hl2[1];
     
    607607   _ntl_ulong hl2[8];
    608608
    609    hs0[0] = a[0] ^ a[4]; 
     609   hs0[0] = a[0] ^ a[4];
    610610   hs0[1] = a[1] ^ a[5];
    611611   hs0[2] = a[2] ^ a[6];
    612612   hs0[3] = a[3] ^ a[7];
    613    hs1[0] = b[0] ^ b[4]; 
     613   hs1[0] = b[0] ^ b[4];
    614614   hs1[1] = b[1] ^ b[5];
    615615   hs1[2] = b[2] ^ b[6];
    616616   hs1[3] = b[3] ^ b[7];
    617617
    618    mul4(c, a, b); 
     618   mul4(c, a, b);
    619619   mul4(c+8, a+4, b+4);
    620    mul4(hl2, hs0, hs1); 
     620   mul4(hl2, hs0, hs1);
    621621
    622622   hl2[0] = hl2[0] ^ c[0] ^ c[8];
     
    628628   hl2[6] = hl2[6] ^ c[6] ^ c[14];
    629629   hl2[7] = hl2[7] ^ c[7] ^ c[15];
    630    
     630
    631631   c[4]  ^= hl2[0];
    632632   c[5]  ^= hl2[1];
     
    640640
    641641static
    642 void KarMul(_ntl_ulong *c, const _ntl_ulong *a, const _ntl_ulong *b, 
     642void KarMul(_ntl_ulong *c, const _ntl_ulong *a, const _ntl_ulong *b,
    643643            long len, _ntl_ulong *stk)
    644644{
     
    717717      return;
    718718   }
    719  
     719
    720720   _ntl_ulong a0 = a.xrep[0];
    721721   _ntl_ulong b0 = b.xrep[0];
     
    868868      return;
    869869   }
    870  
     870
    871871   _ntl_ulong a0 = a.xrep[0];
    872872   _ntl_ulong b0 = b.xrep[0];
     
    10571057            }
    10581058         }
    1059          return; 
     1059         return;
    10601060
    10611061         case 7: {
     
    10981098            }
    10991099         }
    1100          return; 
     1100         return;
    11011101
    11021102         case 8: {
     
    11431143            }
    11441144         }
    1145          return; 
     1145         return;
    11461146
    11471147      }
     
    11831183   // finally: the general case
    11841184
    1185    
     1185
    11861186   static WordVector mem;
    11871187   static WordVector stk;
     
    12441244      if (sa == 1) {
    12451245         AddMul1(cp, bp, sb, ap[0]);
    1246          
     1246
    12471247         break;
    12481248      }
     
    12531253         KarMul(v, ap, bp + i, sa, stk_p);
    12541254         for (j = 0; j < 2*sa; j++)
    1255             cp[i+j] ^= v[j]; 
     1255            cp[i+j] ^= v[j];
    12561256      }
    12571257
     
    13141314      }
    13151315   }
    1316    else if (n*NTL_BITS_PER_LONG <= m) 
     1316   else if (n*NTL_BITS_PER_LONG <= m)
    13171317      x = a;
    13181318   else {
     
    13341334   }
    13351335}
    1336      
     1336
    13371337
    13381338/****** implementation of vec_GF2X ******/
     
    13761376static _ntl_ulong sqrtab[256] = {
    13771377
    1378 0UL, 1UL, 4UL, 5UL, 16UL, 17UL, 20UL, 21UL, 64UL, 
    1379 65UL, 68UL, 69UL, 80UL, 81UL, 84UL, 85UL, 256UL, 
    1380 257UL, 260UL, 261UL, 272UL, 273UL, 276UL, 277UL, 320UL, 
    1381 321UL, 324UL, 325UL, 336UL, 337UL, 340UL, 341UL, 1024UL, 
    1382 1025UL, 1028UL, 1029UL, 1040UL, 1041UL, 1044UL, 1045UL, 1088UL, 
    1383 1089UL, 1092UL, 1093UL, 1104UL, 1105UL, 1108UL, 1109UL, 1280UL, 
    1384 1281UL, 1284UL, 1285UL, 1296UL, 1297UL, 1300UL, 1301UL, 1344UL, 
    1385 1345UL, 1348UL, 1349UL, 1360UL, 1361UL, 1364UL, 1365UL, 4096UL, 
    1386 4097UL, 4100UL, 4101UL, 4112UL, 4113UL, 4116UL, 4117UL, 4160UL, 
    1387 4161UL, 4164UL, 4165UL, 4176UL, 4177UL, 4180UL, 4181UL, 4352UL, 
    1388 4353UL, 4356UL, 4357UL, 4368UL, 4369UL, 4372UL, 4373UL, 4416UL, 
    1389 4417UL, 4420UL, 4421UL, 4432UL, 4433UL, 4436UL, 4437UL, 5120UL, 
    1390 5121UL, 5124UL, 5125UL, 5136UL, 5137UL, 5140UL, 5141UL, 5184UL, 
    1391 5185UL, 5188UL, 5189UL, 5200UL, 5201UL, 5204UL, 5205UL, 5376UL, 
    1392 5377UL, 5380UL, 5381UL, 5392UL, 5393UL, 5396UL, 5397UL, 5440UL, 
    1393 5441UL, 5444UL, 5445UL, 5456UL, 5457UL, 5460UL, 5461UL, 16384UL, 
    1394 16385UL, 16388UL, 16389UL, 16400UL, 16401UL, 16404UL, 16405UL, 16448UL, 
    1395 16449UL, 16452UL, 16453UL, 16464UL, 16465UL, 16468UL, 16469UL, 16640UL, 
    1396 16641UL, 16644UL, 16645UL, 16656UL, 16657UL, 16660UL, 16661UL, 16704UL, 
    1397 16705UL, 16708UL, 16709UL, 16720UL, 16721UL, 16724UL, 16725UL, 17408UL, 
    1398 17409UL, 17412UL, 17413UL, 17424UL, 17425UL, 17428UL, 17429UL, 17472UL, 
    1399 17473UL, 17476UL, 17477UL, 17488UL, 17489UL, 17492UL, 17493UL, 17664UL, 
    1400 17665UL, 17668UL, 17669UL, 17680UL, 17681UL, 17684UL, 17685UL, 17728UL, 
    1401 17729UL, 17732UL, 17733UL, 17744UL, 17745UL, 17748UL, 17749UL, 20480UL, 
    1402 20481UL, 20484UL, 20485UL, 20496UL, 20497UL, 20500UL, 20501UL, 20544UL, 
    1403 20545UL, 20548UL, 20549UL, 20560UL, 20561UL, 20564UL, 20565UL, 20736UL, 
    1404 20737UL, 20740UL, 20741UL, 20752UL, 20753UL, 20756UL, 20757UL, 20800UL, 
    1405 20801UL, 20804UL, 20805UL, 20816UL, 20817UL, 20820UL, 20821UL, 21504UL, 
    1406 21505UL, 21508UL, 21509UL, 21520UL, 21521UL, 21524UL, 21525UL, 21568UL, 
    1407 21569UL, 21572UL, 21573UL, 21584UL, 21585UL, 21588UL, 21589UL, 21760UL, 
    1408 21761UL, 21764UL, 21765UL, 21776UL, 21777UL, 21780UL, 21781UL, 21824UL, 
     13780UL, 1UL, 4UL, 5UL, 16UL, 17UL, 20UL, 21UL, 64UL,
     137965UL, 68UL, 69UL, 80UL, 81UL, 84UL, 85UL, 256UL,
     1380257UL, 260UL, 261UL, 272UL, 273UL, 276UL, 277UL, 320UL,
     1381321UL, 324UL, 325UL, 336UL, 337UL, 340UL, 341UL, 1024UL,
     13821025UL, 1028UL, 1029UL, 1040UL, 1041UL, 1044UL, 1045UL, 1088UL,
     13831089UL, 1092UL, 1093UL, 1104UL, 1105UL, 1108UL, 1109UL, 1280UL,
     13841281UL, 1284UL, 1285UL, 1296UL, 1297UL, 1300UL, 1301UL, 1344UL,
     13851345UL, 1348UL, 1349UL, 1360UL, 1361UL, 1364UL, 1365UL, 4096UL,
     13864097UL, 4100UL, 4101UL, 4112UL, 4113UL, 4116UL, 4117UL, 4160UL,
     13874161UL, 4164UL, 4165UL, 4176UL, 4177UL, 4180UL, 4181UL, 4352UL,
     13884353UL, 4356UL, 4357UL, 4368UL, 4369UL, 4372UL, 4373UL, 4416UL,
     13894417UL, 4420UL, 4421UL, 4432UL, 4433UL, 4436UL, 4437UL, 5120UL,
     13905121UL, 5124UL, 5125UL, 5136UL, 5137UL, 5140UL, 5141UL, 5184UL,
     13915185UL, 5188UL, 5189UL, 5200UL, 5201UL, 5204UL, 5205UL, 5376UL,
     13925377UL, 5380UL, 5381UL, 5392UL, 5393UL, 5396UL, 5397UL, 5440UL,
     13935441UL, 5444UL, 5445UL, 5456UL, 5457UL, 5460UL, 5461UL, 16384UL,
     139416385UL, 16388UL, 16389UL, 16400UL, 16401UL, 16404UL, 16405UL, 16448UL,
     139516449UL, 16452UL, 16453UL, 16464UL, 16465UL, 16468UL, 16469UL, 16640UL,
     139616641UL, 16644UL, 16645UL, 16656UL, 16657UL, 16660UL, 16661UL, 16704UL,
     139716705UL, 16708UL, 16709UL, 16720UL, 16721UL, 16724UL, 16725UL, 17408UL,
     139817409UL, 17412UL, 17413UL, 17424UL, 17425UL, 17428UL, 17429UL, 17472UL,
     139917473UL, 17476UL, 17477UL, 17488UL, 17489UL, 17492UL, 17493UL, 17664UL,
     140017665UL, 17668UL, 17669UL, 17680UL, 17681UL, 17684UL, 17685UL, 17728UL,
     140117729UL, 17732UL, 17733UL, 17744UL, 17745UL, 17748UL, 17749UL, 20480UL,
     140220481UL, 20484UL, 20485UL, 20496UL, 20497UL, 20500UL, 20501UL, 20544UL,
     140320545UL, 20548UL, 20549UL, 20560UL, 20561UL, 20564UL, 20565UL, 20736UL,
     140420737UL, 20740UL, 20741UL, 20752UL, 20753UL, 20756UL, 20757UL, 20800UL,
     140520801UL, 20804UL, 20805UL, 20816UL, 20817UL, 20820UL, 20821UL, 21504UL,
     140621505UL, 21508UL, 21509UL, 21520UL, 21521UL, 21524UL, 21525UL, 21568UL,
     140721569UL, 21572UL, 21573UL, 21584UL, 21585UL, 21588UL, 21589UL, 21760UL,
     140821761UL, 21764UL, 21765UL, 21776UL, 21777UL, 21780UL, 21781UL, 21824UL,
    1409140921825UL, 21828UL, 21829UL, 21840UL, 21841UL, 21844UL, 21845UL };
    14101410
     
    14121412
    14131413
    1414 static inline 
     1414static inline
    14151415void sqr1(_ntl_ulong *c, _ntl_ulong a)
    14161416{
     
    14611461
    14621462   if (n < 0) {
    1463       if (n < -NTL_MAX_LONG) 
     1463      if (n < -NTL_MAX_LONG)
    14641464         clear(c);
    14651465      else
     
    15351535   if (bn) ss++;
    15361536
    1537    if (ss > sc) 
     1537   if (ss > sc)
    15381538      c.xrep.SetLength(ss);
    15391539
     
    16141614static _ntl_ulong revtab[256] = {
    16151615
    1616 0UL, 128UL, 64UL, 192UL, 32UL, 160UL, 96UL, 224UL, 16UL, 144UL, 
    1617 80UL, 208UL, 48UL, 176UL, 112UL, 240UL, 8UL, 136UL, 72UL, 200UL, 
    1618 40UL, 168UL, 104UL, 232UL, 24UL, 152UL, 88UL, 216UL, 56UL, 184UL, 
    1619 120UL, 248UL, 4UL, 132UL, 68UL, 196UL, 36UL, 164UL, 100UL, 228UL, 
    1620 20UL, 148UL, 84UL, 212UL, 52UL, 180UL, 116UL, 244UL, 12UL, 140UL, 
    1621 76UL, 204UL, 44UL, 172UL, 108UL, 236UL, 28UL, 156UL, 92UL, 220UL, 
    1622 60UL, 188UL, 124UL, 252UL, 2UL, 130UL, 66UL, 194UL, 34UL, 162UL, 
    1623 98UL, 226UL, 18UL, 146UL, 82UL, 210UL, 50UL, 178UL, 114UL, 242UL, 
    1624 10UL, 138UL, 74UL, 202UL, 42UL, 170UL, 106UL, 234UL, 26UL, 154UL, 
    1625 90UL, 218UL, 58UL, 186UL, 122UL, 250UL, 6UL, 134UL, 70UL, 198UL, 
    1626 38UL, 166UL, 102UL, 230UL, 22UL, 150UL, 86UL, 214UL, 54UL, 182UL, 
    1627 118UL, 246UL, 14UL, 142UL, 78UL, 206UL, 46UL, 174UL, 110UL, 238UL, 
    1628 30UL, 158UL, 94UL, 222UL, 62UL, 190UL, 126UL, 254UL, 1UL, 129UL, 
    1629 65UL, 193UL, 33UL, 161UL, 97UL, 225UL, 17UL, 145UL, 81UL, 209UL, 
    1630 49UL, 177UL, 113UL, 241UL, 9UL, 137UL, 73UL, 201UL, 41UL, 169UL, 
    1631 105UL, 233UL, 25UL, 153UL, 89UL, 217UL, 57UL, 185UL, 121UL, 249UL, 
    1632 5UL, 133UL, 69UL, 197UL, 37UL, 165UL, 101UL, 229UL, 21UL, 149UL, 
    1633 85UL, 213UL, 53UL, 181UL, 117UL, 245UL, 13UL, 141UL, 77UL, 205UL, 
    1634 45UL, 173UL, 109UL, 237UL, 29UL, 157UL, 93UL, 221UL, 61UL, 189UL, 
    1635 125UL, 253UL, 3UL, 131UL, 67UL, 195UL, 35UL, 163UL, 99UL, 227UL, 
    1636 19UL, 147UL, 83UL, 211UL, 51UL, 179UL, 115UL, 243UL, 11UL, 139UL, 
    1637 75UL, 203UL, 43UL, 171UL, 107UL, 235UL, 27UL, 155UL, 91UL, 219UL, 
    1638 59UL, 187UL, 123UL, 251UL, 7UL, 135UL, 71UL, 199UL, 39UL, 167UL, 
    1639 103UL, 231UL, 23UL, 151UL, 87UL, 215UL, 55UL, 183UL, 119UL, 247UL, 
    1640 15UL, 143UL, 79UL, 207UL, 47UL, 175UL, 111UL, 239UL, 31UL, 159UL, 
    1641 95UL, 223UL, 63UL, 191UL, 127UL, 255UL  }; 
    1642 
    1643 static inline 
     16160UL, 128UL, 64UL, 192UL, 32UL, 160UL, 96UL, 224UL, 16UL, 144UL,
     161780UL, 208UL, 48UL, 176UL, 112UL, 240UL, 8UL, 136UL, 72UL, 200UL,
     161840UL, 168UL, 104UL, 232UL, 24UL, 152UL, 88UL, 216UL, 56UL, 184UL,
     1619120UL, 248UL, 4UL, 132UL, 68UL, 196UL, 36UL, 164UL, 100UL, 228UL,
     162020UL, 148UL, 84UL, 212UL, 52UL, 180UL, 116UL, 244UL, 12UL, 140UL,
     162176UL, 204UL, 44UL, 172UL, 108UL, 236UL, 28UL, 156UL, 92UL, 220UL,
     162260UL, 188UL, 124UL, 252UL, 2UL, 130UL, 66UL, 194UL, 34UL, 162UL,
     162398UL, 226UL, 18UL, 146UL, 82UL, 210UL, 50UL, 178UL, 114UL, 242UL,
     162410UL, 138UL, 74UL, 202UL, 42UL, 170UL, 106UL, 234UL, 26UL, 154UL,
     162590UL, 218UL, 58UL, 186UL, 122UL, 250UL, 6UL, 134UL, 70UL, 198UL,
     162638UL, 166UL, 102UL, 230UL, 22UL, 150UL, 86UL, 214UL, 54UL, 182UL,
     1627118UL, 246UL, 14UL, 142UL, 78UL, 206UL, 46UL, 174UL, 110UL, 238UL,
     162830UL, 158UL, 94UL, 222UL, 62UL, 190UL, 126UL, 254UL, 1UL, 129UL,
     162965UL, 193UL, 33UL, 161UL, 97UL, 225UL, 17UL, 145UL, 81UL, 209UL,
     163049UL, 177UL, 113UL, 241UL, 9UL, 137UL, 73UL, 201UL, 41UL, 169UL,
     1631105UL, 233UL, 25UL, 153UL, 89UL, 217UL, 57UL, 185UL, 121UL, 249UL,
     16325UL, 133UL, 69UL, 197UL, 37UL, 165UL, 101UL, 229UL, 21UL, 149UL,
     163385UL, 213UL, 53UL, 181UL, 117UL, 245UL, 13UL, 141UL, 77UL, 205UL,
     163445UL, 173UL, 109UL, 237UL, 29UL, 157UL, 93UL, 221UL, 61UL, 189UL,
     1635125UL, 253UL, 3UL, 131UL, 67UL, 195UL, 35UL, 163UL, 99UL, 227UL,
     163619UL, 147UL, 83UL, 211UL, 51UL, 179UL, 115UL, 243UL, 11UL, 139UL,
     163775UL, 203UL, 43UL, 171UL, 107UL, 235UL, 27UL, 155UL, 91UL, 219UL,
     163859UL, 187UL, 123UL, 251UL, 7UL, 135UL, 71UL, 199UL, 39UL, 167UL,
     1639103UL, 231UL, 23UL, 151UL, 87UL, 215UL, 55UL, 183UL, 119UL, 247UL,
     164015UL, 143UL, 79UL, 207UL, 47UL, 175UL, 111UL, 239UL, 31UL, 159UL,
     164195UL, 223UL, 63UL, 191UL, 127UL, 255UL  };
     1642
     1643static inline
    16441644_ntl_ulong rev1(_ntl_ulong a)
    16451645{
     
    16751675
    16761676   c.xrep.SetLength(wn);
    1677  
     1677
    16781678   _ntl_ulong *cp = c.xrep.elts();
    16791679   const _ntl_ulong *ap = a.xrep.elts();
     
    17371737   r = n - lw*BytesPerLong;
    17381738
    1739    if (r != 0) 
     1739   if (r != 0)
    17401740      lw++;
    17411741   else
  • ntl/src/GF2X1.c

    r1d43d18 r287cc8  
    1616#ifdef NTL_GF2X_LIB
    1717
    18 #define NTL_GF2X_GCD_CROSSOVER (400L*NTL_BITS_PER_LONG) 
     18#define NTL_GF2X_GCD_CROSSOVER (400L*NTL_BITS_PER_LONG)
    1919#define NTL_GF2X_HalfGCD_CROSSOVER (6L*NTL_BITS_PER_LONG)
    2020#define NTL_GF2X_BERMASS_CROSSOVER (200L*NTL_BITS_PER_LONG)
     
    2222#else
    2323
    24 #define NTL_GF2X_GCD_CROSSOVER (900L*NTL_BITS_PER_LONG) 
     24#define NTL_GF2X_GCD_CROSSOVER (900L*NTL_BITS_PER_LONG)
    2525#define NTL_GF2X_HalfGCD_CROSSOVER (6L*NTL_BITS_PER_LONG)
    2626#define NTL_GF2X_BERMASS_CROSSOVER (450L*NTL_BITS_PER_LONG)
     
    4646
    4747~GF2XRegisterType()
    48 { xrep->xrep.release(); 
     48{ xrep->xrep.release();
    4949  GF2XRegisterTop--; }
    5050
     
    102102
    103103   stab[posb] = b;
    104    for (i = 1; i <= min(dq, NTL_BITS_PER_LONG-1); i++) 
    105       MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
     104   for (i = 1; i <= min(dq, NTL_BITS_PER_LONG-1); i++)
     105      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
    106106             stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
    107107
     
    206206
    207207   stab[posb] = b;
    208    for (i = 1; i <= min(da-db, NTL_BITS_PER_LONG-1); i++) 
    209       MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
     208   for (i = 1; i <= min(da-db, NTL_BITS_PER_LONG-1); i++)
     209      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
    210210             stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
    211211
     
    349349
    350350
    351 static 
     351static
    352352long weight1(_ntl_ulong a)
    353353{
     
    392392
    393393   trunc(g, g, n);
    394    
     394
    395395   long t = deg(g);
    396396
     
    440440   long posb = n - NTL_BITS_PER_LONG*(sb-1);
    441441
    442    F.posn = posb; 
     442   F.posn = posb;
    443443
    444444   if (F.posn > 0) {
     
    467467   long deg_f0 = deg(f0);
    468468
    469    if (F.sn > 1 && deg_f0 < NTL_BITS_PER_LONG 
     469   if (F.sn > 1 && deg_f0 < NTL_BITS_PER_LONG
    470470       && deg_f0 >= NTL_BITS_PER_LONG/2) {
    471471      if (F.size >= 6)
     
    482482   else if (F.size >= 8)
    483483      F.method = GF2X_MOD_MUL;
    484    else 
     484   else
    485485      F.method = GF2X_MOD_PLAIN;
    486      
     486
    487487
    488488   if (F.method == GF2X_MOD_SPECIAL) {
     
    505505
    506506         stab1[kk1<<1] = stab1[kk0<<1] << 1;
    507          stab1[(kk1<<1)+1] = (stab1[(kk0<<1)+1] << 1) 
     507         stab1[(kk1<<1)+1] = (stab1[(kk0<<1)+1] << 1)
    508508                          | (stab1[kk0<<1] >> (NTL_BITS_PER_LONG-1));
    509509
    510          if (kk1 < posb) 
     510         if (kk1 < posb)
    511511            stab_cnt[kk1] = -sb;
    512512         else
     
    526526      long *stab_cnt = F.stab_cnt;
    527527      if (!stab_cnt) Error("out of memory");
    528      
    529    
     528
     529
    530530      stab[posb] = f;
    531       for (i = 1; i < NTL_BITS_PER_LONG; i++) 
    532          MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
     531      for (i = 1; i < NTL_BITS_PER_LONG; i++)
     532         MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
    533533                stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
    534    
    535    
     534
     535
    536536      for (i = 0; i < NTL_BITS_PER_LONG; i++) {
    537537         WordVector& st = stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG].xrep;
     
    568568GF2XModulus::GF2XModulus(const GF2XModulus& F) :
    569569   f(F.f), n(F.n), sn(F.sn), posn(F.posn), k3(F.k3), k2(F.k2), k1(F.k1),
    570    size(F.size), 
     570   size(F.size),
    571571   msk(F.msk), method(F.method), stab(F.stab), h0(F.h0), f0(F.f0),
    572572   stab_cnt(0), stab_ptr(0), stab1(0), tracevec(F.tracevec)
     
    596596         stab_ptr = NTL_NEW_OP _ntl_ulong_ptr[NTL_BITS_PER_LONG];
    597597         if (!stab_ptr) Error("GF2XModulus: out of memory");
    598      
     598
    599599         for (i = 0; i < NTL_BITS_PER_LONG; i++) {
    600600            WordVector& st = stab[((_ntl_ulong)(posn+i))%NTL_BITS_PER_LONG].xrep;
     
    611611   if (this == &F) return *this;
    612612
    613    f=F.f; n=F.n; sn=F.sn; posn=F.posn; 
     613   f=F.f; n=F.n; sn=F.sn; posn=F.posn;
    614614   k3=F.k3; k2=F.k2; k1=F.k1;
    615    size=F.size; 
     615   size=F.size;
    616616   msk=F.msk; method=F.method; stab=F.stab; h0=F.h0; f0 = F.f0;
    617617   tracevec=F.tracevec;
     
    641641         if (!stab_ptr) stab_ptr = NTL_NEW_OP _ntl_ulong_ptr[NTL_BITS_PER_LONG];
    642642         if (!stab_ptr) Error("GF2XModulus: out of memory");
    643      
     643
    644644         for (i = 0; i < NTL_BITS_PER_LONG; i++) {
    645645            WordVector& st = stab[((_ntl_ulong)(posn+i))%NTL_BITS_PER_LONG].xrep;
     
    653653   return *this;
    654654}
    655    
    656 
    657 
    658 GF2XModulus::~GF2XModulus() 
    659 { 
    660    delete [] stab_ptr; 
    661    delete [] stab_cnt; 
    662    delete [] stab1; 
     655
     656
     657
     658GF2XModulus::~GF2XModulus()
     659{
     660   delete [] stab_ptr;
     661   delete [] stab_cnt;
     662   delete [] stab1;
    663663}
    664664
     
    751751   r = buf;
    752752}
    753    
     753
    754754
    755755void UseMulDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, const GF2XModulus& F)
     
    795795   GF2XRegister(qq);
    796796   GF2XRegister(qbuf);
    797    
     797
    798798   clear(buf);
    799799   a = aa;
     
    890890         p[0] ^= (w >> bn);
    891891
    892          p[m] &= ((1UL<<bn)-1UL); 
     892         p[m] &= ((1UL<<bn)-1UL);
    893893      }
    894894      else {
     
    911911         if (m-wdiff-1 >= 0) p[m-wdiff-1] ^= (w << (NTL_BITS_PER_LONG-bdiff));
    912912         p[0] ^= (w >> bn);
    913          p[m] &= ((1UL<<bn)-1UL); 
     913         p[m] &= ((1UL<<bn)-1UL);
    914914      }
    915915   }
     
    960960      w = p[m];
    961961
    962       if (bn == 0) 
     962      if (bn == 0)
    963963         p[m-wn] ^= w;
    964964      else {
     
    968968      }
    969969
    970       if (bdiff1 == 0) 
     970      if (bdiff1 == 0)
    971971         p[m-wdiff1] ^= w;
    972972      else {
     
    976976      }
    977977
    978       if (bdiff2 == 0) 
     978      if (bdiff2 == 0)
    979979         p[m-wdiff2] ^= w;
    980980      else {
     
    984984      }
    985985
    986       if (bdiff3 == 0) 
     986      if (bdiff3 == 0)
    987987         p[m-wdiff3] ^= w;
    988988      else {
     
    997997   w = (p[m] >> bn) << bn;
    998998
    999    p[0] ^= (w >> bn); 
     999   p[0] ^= (w >> bn);
    10001000
    10011001   if (bdiff1 == 0)
     
    10231023      p[m] &= ((1UL<<bn)-1UL);
    10241024
    1025    
     1025
    10261026   if (bn == 0)
    10271027      wn--;
     
    10921092
    10931093   RightShift(P1, a, n);
    1094    if (k != 1) 
     1094   if (k != 1)
    10951095      RightShiftAdd(P1, P1, n-k);
    10961096
     
    10981098}
    10991099
    1100 static 
     1100static
    11011101void TriDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n, long k)
    11021102{
     
    11201120
    11211121   RightShift(P1, a, n);
    1122    
     1122
    11231123   RightShift(P2, P1, n-k3);
    11241124   RightShiftAdd(P2, P1, n-k2);
     
    11321132}
    11331133
    1134 static 
    1135 void PentDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n, 
     1134static
     1135void PentDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n,
    11361136                  long k3, long k2, long k1)
    11371137{
     
    11851185   GF2XRegister(qq);
    11861186   GF2XRegister(qbuf);
    1187    
     1187
    11881188   clear(buf);
    11891189   a = aa;
     
    12111211
    12121212static
    1213 void PentDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, long n, 
     1213void PentDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, long n,
    12141214                  long k3, long k2, long k1)
    12151215{
     
    12541254   GF2XRegister(qq);
    12551255   GF2XRegister(qbuf);
    1256    
     1256
    12571257   clear(buf);
    12581258   a = aa;
     
    13041304   }
    13051305   else if (F.method == GF2X_MOD_MUL) {
    1306       if (da <= 2*(n-1)) 
     1306      if (da <= 2*(n-1))
    13071307         UseMulRem21(r, a, F);
    13081308      else
     
    13121312      long sa = a.xrep.length();
    13131313      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1314    
     1314
    13151315      _ntl_ulong *ap;
    13161316      if (&r == &a)
     
    13201320         ap = GF2X_rembuf.elts();
    13211321      }
    1322    
     1322
    13231323      _ntl_ulong *atop = &ap[sa-1];
    13241324      _ntl_ulong *stab_top;
    1325    
     1325
    13261326      long i;
    1327    
     1327
    13281328      while (1) {
    13291329         if (atop[0] & (1UL << posa)) {
     
    13431343         }
    13441344      }
    1345    
     1345
    13461346      long sn = F.size;
    13471347      r.xrep.SetLength(sn);
     
    13571357      long sa = a.xrep.length();
    13581358      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1359    
    1360    
     1359
     1360
    13611361      _ntl_ulong *ap;
    13621362      if (&r == &a)
     
    13661366         ap = GF2X_rembuf.elts();
    13671367      }
    1368    
     1368
    13691369      _ntl_ulong *atop = &ap[sa-1];
    13701370      _ntl_ulong *stab_top;
    1371    
     1371
    13721372      long i;
    1373    
     1373
    13741374      while (1) {
    13751375         if (atop[0] & (1UL << posa)) {
     
    13781378               atop[i] ^= stab_top[i];
    13791379         }
    1380    
     1380
    13811381         da--;
    13821382         if (da < n) break;
     
    13881388         }
    13891389      }
    1390    
     1390
    13911391      long sn = F.size;
    13921392      r.xrep.SetLength(sn);
     
    14141414   }
    14151415   else if (F.method == GF2X_MOD_TRI) {
    1416       if (da <= 2*(n-1)) 
     1416      if (da <= 2*(n-1))
    14171417         TriDivRem21(q, r, a, F.n, F.k3);
    14181418      else
     
    14201420   }
    14211421   else if (F.method == GF2X_MOD_PENT) {
    1422       if (da <= 2*(n-1)) 
     1422      if (da <= 2*(n-1))
    14231423         PentDivRem21(q, r, a, F.n, F.k3, F.k2, F.k1);
    14241424      else
     
    14261426   }
    14271427   else if (F.method == GF2X_MOD_MUL) {
    1428       if (da <= 2*(n-1)) 
     1428      if (da <= 2*(n-1))
    14291429         UseMulDivRem21(q, r, a, F);
    14301430      else
     
    14341434      long sa = a.xrep.length();
    14351435      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1436    
     1436
    14371437      long dq = da - n;
    14381438      long sq = dq/NTL_BITS_PER_LONG + 1;
    14391439      long posq = dq - NTL_BITS_PER_LONG*(sq-1);
    1440    
     1440
    14411441      _ntl_ulong *ap;
    14421442      if (&r == &a)
     
    14461446         ap = GF2X_rembuf.elts();
    14471447      }
    1448    
     1448
    14491449      _ntl_ulong *atop = &ap[sa-1];
    14501450      _ntl_ulong *stab_top;
     
    14591459      _ntl_ulong *qtop = &qp[sq-1];
    14601460
    1461    
     1461
    14621462      while (1) {
    14631463         if (atop[0] & (1UL << posa)) {
     
    14681468            atop[i+1] ^= stab_top[1];
    14691469         }
    1470    
     1470
    14711471         da--;
    14721472         if (da < n) break;
     
    14841484         }
    14851485      }
    1486    
     1486
    14871487      long sn = F.size;
    14881488      r.xrep.SetLength(sn);
     
    14981498      long sa = a.xrep.length();
    14991499      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1500    
     1500
    15011501      long dq = da - n;
    15021502      long sq = dq/NTL_BITS_PER_LONG + 1;
    15031503      long posq = dq - NTL_BITS_PER_LONG*(sq-1);
    1504    
     1504
    15051505      _ntl_ulong *ap;
    15061506      if (&r == &a)
     
    15101510         ap = GF2X_rembuf.elts();
    15111511      }
    1512    
     1512
    15131513      _ntl_ulong *atop = &ap[sa-1];
    15141514      _ntl_ulong *stab_top;
    1515    
     1515
    15161516      long i;
    15171517
     
    15221522
    15231523      _ntl_ulong *qtop = &qp[sq-1];
    1524    
     1524
    15251525      while (1) {
    15261526         if (atop[0] & (1UL << posa)) {
     
    15301530               atop[i] ^= stab_top[i];
    15311531         }
    1532    
     1532
    15331533         da--;
    15341534         if (da < n) break;
     
    15461546         }
    15471547      }
    1548    
     1548
    15491549      long sn = F.size;
    15501550      r.xrep.SetLength(sn);
     
    15741574   }
    15751575   else if (F.method == GF2X_MOD_TRI) {
    1576       if (da <= 2*(n-1)) 
     1576      if (da <= 2*(n-1))
    15771577         TriDiv21(q, a, F.n, F.k3);
    15781578      else
     
    15801580   }
    15811581   else if (F.method == GF2X_MOD_PENT) {
    1582       if (da <= 2*(n-1)) 
     1582      if (da <= 2*(n-1))
    15831583         PentDiv21(q, a, F.n, F.k3, F.k2, F.k1);
    15841584      else
     
    15861586   }
    15871587   else if (F.method == GF2X_MOD_MUL) {
    1588       if (da <= 2*(n-1)) 
     1588      if (da <= 2*(n-1))
    15891589         UseMulDiv21(q, a, F);
    15901590      else
     
    15941594      long sa = a.xrep.length();
    15951595      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1596    
     1596
    15971597      long dq = da - n;
    15981598      long sq = dq/NTL_BITS_PER_LONG + 1;
    15991599      long posq = dq - NTL_BITS_PER_LONG*(sq-1);
    1600    
     1600
    16011601      _ntl_ulong *ap;
    16021602      GF2X_rembuf = a.xrep;
    16031603      ap = GF2X_rembuf.elts();
    16041604
    1605    
     1605
    16061606      _ntl_ulong *atop = &ap[sa-1];
    16071607      _ntl_ulong *stab_top;
     
    16151615
    16161616      _ntl_ulong *qtop = &qp[sq-1];
    1617    
     1617
    16181618      while (1) {
    16191619         if (atop[0] & (1UL << posa)) {
     
    16241624            atop[i+1] ^= stab_top[1];
    16251625         }
    1626    
     1626
    16271627         da--;
    16281628         if (da < n) break;
     
    16441644      long sa = a.xrep.length();
    16451645      long posa = da - NTL_BITS_PER_LONG*(sa-1);
    1646    
     1646
    16471647      long dq = da - n;
    16481648      long sq = dq/NTL_BITS_PER_LONG + 1;
    16491649      long posq = dq - NTL_BITS_PER_LONG*(sq-1);
    1650    
     1650
    16511651      _ntl_ulong *ap;
    16521652      GF2X_rembuf = a.xrep;
    16531653      ap = GF2X_rembuf.elts();
    1654    
     1654
    16551655      _ntl_ulong *atop = &ap[sa-1];
    16561656      _ntl_ulong *stab_top;
    1657    
     1657
    16581658      long i;
    16591659
     
    16641664
    16651665      _ntl_ulong *qtop = &qp[sq-1];
    1666    
     1666
    16671667      while (1) {
    16681668         if (atop[0] & (1UL << posa)) {
     
    16721672               atop[i] ^= stab_top[i];
    16731673         }
    1674    
     1674
    16751675         da--;
    16761676         if (da < n) break;
     
    17541754   return k;
    17551755}
    1756      
     1756
    17571757
    17581758
     
    18211821
    18221822   v[0] = g;
    1823  
     1823
    18241824   if (k > 1) {
    18251825      GF2X t;
     
    18371837   val = 0;
    18381838   for (i = n-1; i >= 0; i--) {
    1839       val = (val << 1) | bit(e, i); 
     1839      val = (val << 1) | bit(e, i);
    18401840      if (val == 0)
    18411841         SqrMod(res, res, F);
     
    18691869}
    18701870
    1871    
     1871
    18721872
    18731873
     
    19041904
    19051905
    1906      
     1906
    19071907
    19081908
     
    19241924   mul(P1, P2, b);
    19251925   add(P1, P1, a);
    1926    
     1926
    19271927   r = P1;
    19281928}
     
    19451945   mul(P1, P2, b);
    19461946   add(P1, P1, a);
    1947    
     1947
    19481948   r = P1;
    19491949   q = P2;
     
    19651965   mul(P2, P1, P2);
    19661966   RightShift(P2, P2, da-db);
    1967    
     1967
    19681968   q = P2;
    19691969}
    19701970
    19711971
    1972 const long GF2X_DIV_CROSS = 100; 
     1972const long GF2X_DIV_CROSS = 100;
    19731973
    19741974void DivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2X& b)
     
    20212021
    20222022
    2023 static inline 
    2024 void swap(_ntl_ulong_ptr& a, _ntl_ulong_ptr& b) 
     2023static inline
     2024void swap(_ntl_ulong_ptr& a, _ntl_ulong_ptr& b)
    20252025{  _ntl_ulong_ptr t;  t = a; a = b; b = t; }
    20262026
     
    20332033   GF2XRegister(a);
    20342034   GF2XRegister(b);
    2035    
     2035
    20362036   if (IsZero(a_in)) {
    20372037      d = b_in;
     
    20432043      return;
    20442044   }
    2045      
     2045
    20462046   a.xrep.SetMaxLength(a_in.xrep.length()+1);
    20472047   b.xrep.SetMaxLength(b_in.xrep.length()+1);
     
    22402240      return;
    22412241   }
    2242      
     2242
    22432243   a.xrep.SetMaxLength(a_in.xrep.length()+1);
    22442244   b.xrep.SetMaxLength(b_in.xrep.length()+1);
     
    23482348      BaseXGCD(d, s1, t1, b, r);
    23492349
    2350      
     2350
    23512351      mul(r, t1, q);
    23522352      add(r, r, s1);  // r = s1 - t1*q, but sign doesn't matter
    23532353
    23542354      s = t1;
    2355       t = r;   
     2355      t = r;
    23562356   }
    23572357   else if (sa >= 10 && 2*sb > 3*sa) {
     
    23652365      BaseXGCD(d, s1, t1, a, r);
    23662366
    2367      
     2367
    23682368      mul(r, t1, q);
    23692369      add(r, r, s1);  // r = s1 - t1*q, but sign doesn't matter
    23702370
    23712371      t = t1;
    2372       s = r; 
     2372      s = r;
    23732373   }
    23742374   else {
     
    23892389   long sf = f.xrep.length();
    23902390
    2391    if ((sa >= 10 && 2*sf > 3*sa) || 
     2391   if ((sa >= 10 && 2*sf > 3*sa) ||
    23922392       sf > NTL_GF2X_GCD_CROSSOVER/NTL_BITS_PER_LONG) {
    23932393      GF2XRegister(t);
     
    24042404
    24052405void InvMod(GF2X& c, const GF2X& a, const GF2X& f)
    2406 { 
     2406{
    24072407   GF2XRegister(d);
    24082408   GF2XRegister(s);
     
    24172417
    24182418long InvModStatus(GF2X& c, const GF2X& a, const GF2X& f)
    2419 { 
     2419{
    24202420   GF2XRegister(d);
    24212421   GF2XRegister(s);
     
    24332433
    24342434
    2435    
     2435
    24362436void diff(GF2X& c, const GF2X& a)
    24372437{
    24382438   RightShift(c, a, 1);
    2439    
     2439
    24402440   // clear odd coeffs
    24412441
     
    24752475void VectorCopy(vec_GF2& x, const GF2X& a, long n)
    24762476{
    2477    if (n < 0) Error("VectorCopy: negative length"); 
     2477   if (n < 0) Error("VectorCopy: negative length");
    24782478
    24792479   if (NTL_OVERFLOW(n, 1, 0))
     
    25112511   if (b & 1) {
    25122512      long n = c.xrep.length();
    2513       if (n == 0) 
     2513      if (n == 0)
    25142514         set(c);
    25152515      else {
     
    25772577
    25782578
    2579 void InnerProduct(GF2X& x, const GF2X& v, long dv, long low, long high, 
     2579void InnerProduct(GF2X& x, const GF2X& v, long dv, long low, long high,
    25802580                   const vec_GF2X& H, long n, WordVector& t)
    25812581{
     
    25912591   long b_low = low - w_low*NTL_BITS_PER_LONG;
    25922592
    2593    
     2593
    25942594   const _ntl_ulong *vp = &v.xrep[w_low];
    25952595   _ntl_ulong msk = 1UL << b_low;
     
    26602660   set(A.H[0]);
    26612661   A.H[1] = h;
    2662    for (i = 2; i <= m; i++) 
     2662   for (i = 2; i <= m; i++)
    26632663      MulMod(A.H[i], A.H[i-1], h, F);
    26642664}
     
    27102710}
    27112711
    2712 void Comp3Mod(GF2X& x1, GF2X& x2, GF2X& x3, 
     2712void Comp3Mod(GF2X& x1, GF2X& x2, GF2X& x3,
    27132713              const GF2X& g1, const GF2X& g2, const GF2X& g3,
    27142714              const GF2X& h, const GF2XModulus& F)
     
    27602760      B.shamt_fbi = 0;
    27612761   else
    2762       B.shamt_fbi = F.n-2 - d; 
     2762      B.shamt_fbi = F.n-2 - d;
    27632763
    27642764   CopyReverse(B.fbi, t, d);
    27652765
    27662766   if (F.method != GF2X_MOD_TRI && F.method != GF2X_MOD_PENT) {
    2767    
    2768       // The following code optimizes the case when 
     2767
     2768      // The following code optimizes the case when
    27692769      // f = X^n + low degree poly
    2770    
     2770
    27712771      trunc(t, F.f, F.n);
    27722772      d = deg(t);
     
    28362836   conv(x, xx);
    28372837}
    2838    
     2838
    28392839
    28402840void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2XArgument& H,
     
    28432843   long n = F.n;
    28442844
    2845    if (deg(a) >= n || k < 0 || NTL_OVERFLOW(k, 1, 0)) 
     2845   if (deg(a) >= n || k < 0 || NTL_OVERFLOW(k, 1, 0))
    28462846      Error("ProjectPowers: bad args");
    28472847
     
    28702870
    28712871
    2872 void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k, 
     2872void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k,
    28732873                   const GF2XArgument& H, const GF2XModulus& F)
    28742874{
     
    28792879
    28802880
    2881 void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2X& h, 
     2881void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2X& h,
    28822882                   const GF2XModulus& F)
    28832883{
     
    29202920
    29212921   CopyReverse(b_in, x, 2*m-1);
    2922      
     2922
    29232923   a.xrep.SetMaxLength(a_in.xrep.length()+1);
    29242924   b.xrep.SetMaxLength(b_in.xrep.length()+1);
     
    29772977      long t = ss + (da-db+NTL_BITS_PER_LONG-1)/NTL_BITS_PER_LONG;
    29782978      if (t > sr) {
    2979          while (t > 0 && rp[t-1] == 0) t--; 
     2979         while (t > 0 && rp[t-1] == 0) t--;
    29802980         sr = t;
    29812981      }
     
    30123012
    30133013
    3014 void DoMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m, 
     3014void DoMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m,
    30153015               const GF2X& R)
    30163016{
     
    30663066   GF2X R;
    30673067   GF2XTransMultiplier H1;
    3068    
     3068
    30693069
    30703070   for (;;) {
     
    31123112   long da = deg(a);
    31133113   long df = deg(F);
    3114    if (da >= df) Error("MulByXMod: bad args"); 
     3114   if (da >= df) Error("MulByXMod: bad args");
    31153115
    31163116   MulByX(c, a);
     
    31253125   long da = deg(a);
    31263126   long df = deg(f);
    3127    if (da >= df) Error("MulByXMod: bad args"); 
     3127   if (da >= df) Error("MulByXMod: bad args");
    31283128
    31293129   MulByX(c, a);
     
    31713171   res.SetMaxLength(da*e + 1);
    31723172   res = 1;
    3173    
     3173
    31743174   long k = NumBits(e);
    31753175   long i;
     
    32033203   long n = deg(f);
    32043204
    3205    if (n <= 0) 
     3205   if (n <= 0)
    32063206      Error("TraceVec: bad args");
    32073207
     
    32133213   GF2X x = reverse(-LeftShift(reverse(diff(reverse(f)), n-1), n-1)/f, n-1);
    32143214
    3215    VectorCopy(S, x, n); 
     3215   VectorCopy(S, x, n);
    32163216   S.put(0, to_GF2(n));
    32173217}
     
    32463246      Error("trace: bad args");
    32473247
    3248    if (F.tracevec.length() == 0) 
     3248   if (F.tracevec.length() == 0)
    32493249      ComputeTraceVec(F);
    32503250
     
    34993499      return;
    35003500   }
    3501    
     3501
    35023502   GF2X u1, v1;
    35033503
     
    36653665
    36663666void MinPolyInternal(GF2X& h, const GF2X& x, long m)
    3667 { 
     3667{
    36683668   if (m < NTL_GF2X_BERMASS_CROSSOVER) {
    36693669      OldMinPolyInternal(h, x, m);
     
    36733673   GF2X a, b;
    36743674   _NTL_GF2XMatrix M;
    3675      
     3675
    36763676   SetCoeff(b, 2*m);
    36773677   CopyReverse(a, x, 2*m-1);
  • ntl/src/GF2XFactoring.c

    r1d43d18 r287cc8  
    1717
    1818   build(F, f);
    19    
     19
    2020   GF2X h;
    2121   SetX(h);
     
    119119   } while (!finished);
    120120}
    121          
     121
    122122
    123123
     
    130130
    131131static
    132 void ProcessTable(GF2X& f, vec_pair_GF2X_long& factors, 
     132void ProcessTable(GF2X& f, vec_pair_GF2X_long& factors,
    133133                  const GF2XModulus& F, long limit, const vec_GF2X& tbl,
    134134                  long d, long verbose)
     
    167167
    168168   while (2*d <= deg(t1)) {
    169       GCD(t2, tbl[i], t1); 
     169      GCD(t2, tbl[i], t1);
    170170      if (deg(t2) > 0) {
    171171         AddFactor(factors, t2, d, verbose);
     
    255255
    256256         if (deg(f) < old_n) {
    257             // f has changed 
     257            // f has changed
    258258
    259259            build(F, f);
     
    278278   GF2X a, g;
    279279   GF2XModulus F;
    280    
     280
    281281   build(F, f);
    282282   long n = F.n;
     
    305305   RecEDF(factors, f2, d);
    306306}
    307          
     307
    308308
    309309void EDF(vec_GF2X& factors, const GF2X& ff, long d, long verbose)
     
    338338   }
    339339
    340    
     340
    341341   double t;
    342342
     
    369369   double t;
    370370
    371    
     371
    372372   vec_pair_GF2X_long u;
    373373   DDF(u, f, verbose);
     
    394394   }
    395395}
    396    
     396
    397397void CanZass(vec_pair_GF2X_long& factors, const GF2X& f, long verbose)
    398398{
     
    404404   vec_GF2X x;
    405405
    406    
     406
    407407   SquareFreeDecomp(sfd, f);
    408408
     
    497497
    498498
    499 static int GF2X_irred_tab[][3] = 
     499static int GF2X_irred_tab[][3] =
    500500
    501501{{0,0,0}, {0,0,0},
    502 {1,0,0}, {1,0,0}, {1,0,0}, {2,0,0}, {1,0,0}, {1,0,0}, 
    503 {4,3,1}, {1,0,0}, {3,0,0}, {2,0,0}, {3,0,0}, {4,3,1}, 
    504 {5,0,0}, {1,0,0}, {5,3,1}, {3,0,0}, {3,0,0}, {5,2,1}, 
    505 {3,0,0}, {2,0,0}, {1,0,0}, {5,0,0}, {4,3,1}, {3,0,0}, 
    506 {4,3,1}, {5,2,1}, {1,0,0}, {2,0,0}, {1,0,0}, {3,0,0}, 
    507 {7,3,2}, {10,0,0}, {7,0,0}, {2,0,0}, {9,0,0}, {6,4,1}, 
    508 {6,5,1}, {4,0,0}, {5,4,3}, {3,0,0}, {7,0,0}, {6,4,3}, 
    509 {5,0,0}, {4,3,1}, {1,0,0}, {5,0,0}, {5,3,2}, {9,0,0}, 
    510 {4,3,2}, {6,3,1}, {3,0,0}, {6,2,1}, {9,0,0}, {7,0,0}, 
    511 {7,4,2}, {4,0,0}, {19,0,0}, {7,4,2}, {1,0,0}, {5,2,1}, 
    512 {29,0,0}, {1,0,0}, {4,3,1}, {18,0,0}, {3,0,0}, {5,2,1}, 
    513 {9,0,0}, {6,5,2}, {5,3,1}, {6,0,0}, {10,9,3}, {25,0,0}, 
    514 {35,0,0}, {6,3,1}, {21,0,0}, {6,5,2}, {6,5,3}, {9,0,0}, 
    515 {9,4,2}, {4,0,0}, {8,3,1}, {7,4,2}, {5,0,0}, {8,2,1}, 
    516 {21,0,0}, {13,0,0}, {7,6,2}, {38,0,0}, {27,0,0}, {8,5,1}, 
    517 {21,0,0}, {2,0,0}, {21,0,0}, {11,0,0}, {10,9,6}, {6,0,0}, 
    518 {11,0,0}, {6,3,1}, {15,0,0}, {7,6,1}, {29,0,0}, {9,0,0}, 
    519 {4,3,1}, {4,0,0}, {15,0,0}, {9,7,4}, {17,0,0}, {5,4,2}, 
    520 {33,0,0}, {10,0,0}, {5,4,3}, {9,0,0}, {5,3,2}, {8,7,5}, 
    521 {4,2,1}, {5,2,1}, {33,0,0}, {8,0,0}, {4,3,1}, {18,0,0}, 
    522 {6,2,1}, {2,0,0}, {19,0,0}, {7,6,5}, {21,0,0}, {1,0,0}, 
    523 {7,2,1}, {5,0,0}, {3,0,0}, {8,3,2}, {17,0,0}, {9,8,2}, 
    524 {57,0,0}, {11,0,0}, {5,3,2}, {21,0,0}, {8,7,1}, {8,5,3}, 
    525 {15,0,0}, {10,4,1}, {21,0,0}, {5,3,2}, {7,4,2}, {52,0,0}, 
    526 {71,0,0}, {14,0,0}, {27,0,0}, {10,9,7}, {53,0,0}, {3,0,0}, 
    527 {6,3,2}, {1,0,0}, {15,0,0}, {62,0,0}, {9,0,0}, {6,5,2}, 
    528 {8,6,5}, {31,0,0}, {5,3,2}, {18,0,0}, {27,0,0}, {7,6,3}, 
    529 {10,8,7}, {9,8,3}, {37,0,0}, {6,0,0}, {15,3,2}, {34,0,0}, 
    530 {11,0,0}, {6,5,2}, {1,0,0}, {8,5,2}, {13,0,0}, {6,0,0}, 
    531 {11,3,2}, {8,0,0}, {31,0,0}, {4,2,1}, {3,0,0}, {7,6,1}, 
    532 {81,0,0}, {56,0,0}, {9,8,7}, {24,0,0}, {11,0,0}, {7,6,5}, 
    533 {6,5,2}, {6,5,2}, {8,7,6}, {9,0,0}, {7,2,1}, {15,0,0}, 
    534 {87,0,0}, {8,3,2}, {3,0,0}, {9,4,2}, {9,0,0}, {34,0,0}, 
    535 {5,3,2}, {14,0,0}, {55,0,0}, {8,7,1}, {27,0,0}, {9,5,2}, 
    536 {10,9,5}, {43,0,0}, {9,3,1}, {6,0,0}, {7,0,0}, {11,10,8}, 
    537 {105,0,0}, {6,5,2}, {73,0,0}, {23,0,0}, {7,3,1}, {45,0,0}, 
    538 {11,0,0}, {8,4,1}, {7,0,0}, {8,6,2}, {5,4,2}, {33,0,0}, 
    539 {9,8,3}, {32,0,0}, {10,7,3}, {10,9,4}, {113,0,0}, {10,4,1}, 
    540 {8,7,6}, {26,0,0}, {9,4,2}, {74,0,0}, {31,0,0}, {9,6,1}, 
    541 {5,0,0}, {7,4,1}, {73,0,0}, {36,0,0}, {8,5,3}, {70,0,0}, 
    542 {95,0,0}, {8,5,1}, {111,0,0}, {6,4,1}, {11,2,1}, {82,0,0}, 
    543 {15,14,10}, {35,0,0}, {103,0,0}, {7,4,2}, {15,0,0}, {46,0,0}, 
    544 {7,2,1}, {52,0,0}, {10,5,2}, {12,0,0}, {71,0,0}, {10,6,2}, 
    545 {15,0,0}, {7,6,4}, {9,8,4}, {93,0,0}, {9,6,2}, {42,0,0}, 
    546 {47,0,0}, {8,6,3}, {25,0,0}, {7,6,1}, {53,0,0}, {58,0,0}, 
    547 {9,3,2}, {23,0,0}, {67,0,0}, {11,10,9}, {63,0,0}, {12,6,3}, 
    548 {5,0,0}, {5,0,0}, {9,5,2}, {93,0,0}, {35,0,0}, {12,7,5}, 
    549 {53,0,0}, {10,7,5}, {69,0,0}, {71,0,0}, {11,10,1}, {21,0,0}, 
    550 {5,3,2}, {12,11,5}, {37,0,0}, {11,6,1}, {33,0,0}, {48,0,0}, 
    551 {7,3,2}, {5,0,0}, {11,8,4}, {11,6,4}, {5,0,0}, {9,5,2}, 
    552 {41,0,0}, {1,0,0}, {11,2,1}, {102,0,0}, {7,3,1}, {8,4,2}, 
    553 {15,0,0}, {10,6,4}, {93,0,0}, {7,5,3}, {9,7,4}, {79,0,0}, 
    554 {15,0,0}, {10,9,1}, {63,0,0}, {7,4,2}, {45,0,0}, {36,0,0}, 
    555 {4,3,1}, {31,0,0}, {67,0,0}, {10,3,1}, {51,0,0}, {10,5,2}, 
    556 {10,3,1}, {34,0,0}, {8,3,1}, {50,0,0}, {99,0,0}, {10,6,2}, 
    557 {89,0,0}, {2,0,0}, {5,2,1}, {10,7,2}, {7,4,1}, {55,0,0}, 
    558 {4,3,1}, {16,10,7}, {45,0,0}, {10,8,6}, {125,0,0}, {75,0,0}, 
    559 {7,2,1}, {22,0,0}, {63,0,0}, {11,10,3}, {103,0,0}, {6,5,2}, 
    560 {53,0,0}, {34,0,0}, {13,11,6}, {69,0,0}, {99,0,0}, {6,5,1}, 
    561 {10,9,7}, {11,10,2}, {57,0,0}, {68,0,0}, {5,3,2}, {7,4,1}, 
    562 {63,0,0}, {8,5,3}, {9,0,0}, {9,6,5}, {29,0,0}, {21,0,0}, 
    563 {7,3,2}, {91,0,0}, {139,0,0}, {8,3,2}, {111,0,0}, {8,7,2}, 
    564 {8,6,5}, {16,0,0}, {8,7,5}, {41,0,0}, {43,0,0}, {10,8,5}, 
    565 {47,0,0}, {5,2,1}, {81,0,0}, {90,0,0}, {12,3,2}, {6,0,0}, 
    566 {83,0,0}, {8,7,1}, {159,0,0}, {10,9,5}, {9,0,0}, {28,0,0}, 
    567 {13,10,6}, {7,0,0}, {135,0,0}, {11,6,5}, {25,0,0}, {12,7,6}, 
    568 {7,6,2}, {26,0,0}, {5,3,2}, {152,0,0}, {171,0,0}, {9,8,5}, 
    569 {65,0,0}, {13,8,2}, {141,0,0}, {71,0,0}, {5,3,2}, {87,0,0}, 
    570 {10,4,3}, {12,10,3}, {147,0,0}, {10,7,6}, {13,0,0}, {102,0,0}, 
    571 {9,5,2}, {107,0,0}, {199,0,0}, {15,5,4}, {7,0,0}, {5,4,2}, 
    572 {149,0,0}, {25,0,0}, {9,7,2}, {12,0,0}, {63,0,0}, {11,6,5}, 
    573 {105,0,0}, {10,8,7}, {14,6,1}, {120,0,0}, {13,4,3}, {33,0,0}, 
    574 {12,11,5}, {12,9,5}, {165,0,0}, {6,2,1}, {65,0,0}, {49,0,0}, 
    575 {4,3,1}, {7,0,0}, {7,5,2}, {10,6,1}, {81,0,0}, {7,6,4}, 
    576 {105,0,0}, {73,0,0}, {11,6,4}, {134,0,0}, {47,0,0}, {16,10,1}, 
    577 {6,5,4}, {15,6,4}, {8,6,1}, {38,0,0}, {18,9,6}, {16,0,0}, 
    578 {203,0,0}, {12,5,2}, {19,0,0}, {7,6,1}, {73,0,0}, {93,0,0}, 
    579 {19,18,13}, {31,0,0}, {14,11,6}, {11,6,1}, {27,0,0}, {9,5,2}, 
    580 {9,0,0}, {1,0,0}, {11,3,2}, {200,0,0}, {191,0,0}, {9,8,4}, 
    581 {9,0,0}, {16,15,7}, {121,0,0}, {104,0,0}, {15,9,6}, {138,0,0}, 
    582 {9,6,5}, {9,6,4}, {105,0,0}, {17,16,6}, {81,0,0}, {94,0,0}, 
    583 {4,3,1}, {83,0,0}, {219,0,0}, {11,6,3}, {7,0,0}, {10,5,3}, 
    584 {17,0,0}, {76,0,0}, {16,5,2}, {78,0,0}, {155,0,0}, {11,6,5}, 
    585 {27,0,0}, {5,4,2}, {8,5,4}, {3,0,0}, {15,14,6}, {156,0,0}, 
    586 {23,0,0}, {13,6,3}, {9,0,0}, {8,7,3}, {69,0,0}, {10,0,0}, 
    587 {8,5,2}, {26,0,0}, {67,0,0}, {14,7,4}, {21,0,0}, {12,10,2}, 
    588 {33,0,0}, {79,0,0}, {15,11,2}, {32,0,0}, {39,0,0}, {13,6,2}, 
    589 {167,0,0}, {6,4,1}, {97,0,0}, {47,0,0}, {11,6,2}, {42,0,0}, 
    590 {10,7,3}, {10,5,4}, {1,0,0}, {4,3,2}, {161,0,0}, {8,6,2}, 
    591 {7,5,3}, {94,0,0}, {195,0,0}, {10,5,4}, {9,0,0}, {13,10,4}, 
    592 {8,6,1}, {16,0,0}, {8,3,1}, {122,0,0}, {8,2,1}, {13,7,4}, 
    593 {10,5,3}, {16,4,3}, {193,0,0}, {135,0,0}, {19,16,9}, {39,0,0}, 
    594 {10,8,7}, {10,9,4}, {153,0,0}, {7,6,5}, {73,0,0}, {34,0,0}, 
    595 {11,9,6}, {71,0,0}, {11,4,2}, {14,7,3}, {163,0,0}, {11,6,1}, 
    596 {153,0,0}, {28,0,0}, {15,7,6}, {77,0,0}, {67,0,0}, {10,5,2}, 
    597 {12,8,1}, {10,6,4}, {13,0,0}, {146,0,0}, {13,4,3}, {25,0,0}, 
    598 {23,22,16}, {12,9,7}, {237,0,0}, {13,7,6}, {85,0,0}, {130,0,0}, 
    599 {14,13,3}, {88,0,0}, {7,5,2}, {11,6,1}, {35,0,0}, {10,4,3}, 
    600 {93,0,0}, {9,6,4}, {13,6,3}, {86,0,0}, {19,0,0}, {9,2,1}, 
    601 {273,0,0}, {14,12,9}, {7,6,1}, {30,0,0}, {9,5,2}, {201,0,0}, 
    602 {215,0,0}, {6,4,3}, {105,0,0}, {10,7,5}, {165,0,0}, {105,0,0}, 
    603 {19,13,6}, {31,0,0}, {127,0,0}, {10,4,2}, {81,0,0}, {19,10,4}, 
    604 {45,0,0}, {211,0,0}, {19,10,3}, {200,0,0}, {295,0,0}, {9,8,5}, 
    605 {9,0,0}, {12,6,5}, {297,0,0}, {68,0,0}, {11,6,5}, {133,0,0}, 
    606 {251,0,0}, {13,8,4}, {223,0,0}, {6,5,2}, {7,4,2}, {307,0,0}, 
    607 {9,2,1}, {101,0,0}, {39,0,0}, {14,10,4}, {217,0,0}, {14,9,1}, 
    608 {6,5,1}, {16,0,0}, {14,3,2}, {11,0,0}, {119,0,0}, {11,3,2}, 
    609 {11,6,5}, {11,8,4}, {249,0,0}, {5,0,0}, {13,3,1}, {37,0,0}, 
    610 {3,0,0}, {14,0,0}, {93,0,0}, {10,8,7}, {33,0,0}, {88,0,0}, 
    611 {7,5,4}, {38,0,0}, {55,0,0}, {15,4,2}, {11,0,0}, {12,11,4}, 
    612 {21,0,0}, {107,0,0}, {11,9,8}, {33,0,0}, {10,7,2}, {18,7,3}, 
    613 {147,0,0}, {5,4,2}, {153,0,0}, {15,0,0}, {11,6,5}, {28,0,0}, 
    614 {11,7,4}, {6,3,1}, {31,0,0}, {8,4,3}, {15,5,3}, {66,0,0}, 
    615 {23,16,9}, {11,9,3}, {171,0,0}, {11,6,1}, {209,0,0}, {4,3,1}, 
    616 {197,0,0}, {13,0,0}, {19,14,6}, {14,0,0}, {79,0,0}, {13,6,2}, 
    617 {299,0,0}, {15,8,2}, {169,0,0}, {177,0,0}, {23,10,2}, {267,0,0}, 
    618 {215,0,0}, {15,10,1}, {75,0,0}, {16,4,2}, {37,0,0}, {12,7,1}, 
    619 {8,3,2}, {17,0,0}, {12,11,8}, {15,8,5}, {15,0,0}, {4,3,1}, 
    620 {13,12,4}, {92,0,0}, {5,4,3}, {41,0,0}, {23,0,0}, {7,4,1}, 
    621 {183,0,0}, {16,7,1}, {165,0,0}, {150,0,0}, {9,6,4}, {9,0,0}, 
    622 {231,0,0}, {16,10,4}, {207,0,0}, {9,6,5}, {5,0,0}, {180,0,0}, 
    623 {4,3,2}, {58,0,0}, {147,0,0}, {8,6,2}, {343,0,0}, {8,7,2}, 
    624 {11,6,1}, {44,0,0}, {13,8,6}, {5,0,0}, {347,0,0}, {18,16,8}, 
    625 {135,0,0}, {9,8,3}, {85,0,0}, {90,0,0}, {13,11,1}, {258,0,0}, 
    626 {351,0,0}, {10,6,4}, {19,0,0}, {7,6,1}, {309,0,0}, {18,0,0}, 
    627 {13,10,3}, {158,0,0}, {19,0,0}, {12,10,1}, {45,0,0}, {7,6,1}, 
    628 {233,0,0}, {98,0,0}, {11,6,5}, {3,0,0}, {83,0,0}, {16,14,9}, 
    629 {6,5,3}, {9,7,4}, {22,19,9}, {168,0,0}, {19,17,4}, {120,0,0}, 
    630 {14,5,2}, {17,15,6}, {7,0,0}, {10,8,6}, {185,0,0}, {93,0,0}, 
    631 {15,14,7}, {29,0,0}, {375,0,0}, {10,8,3}, {13,0,0}, {17,16,2}, 
    632 {329,0,0}, {68,0,0}, {13,9,6}, {92,0,0}, {12,10,3}, {7,6,3}, 
    633 {17,10,3}, {5,2,1}, {9,6,1}, {30,0,0}, {9,7,3}, {253,0,0}, 
    634 {143,0,0}, {7,4,1}, {9,4,1}, {12,10,4}, {53,0,0}, {25,0,0}, 
    635 {9,7,1}, {217,0,0}, {15,13,9}, {14,9,2}, {75,0,0}, {8,7,2}, 
    636 {21,0,0}, {7,0,0}, {14,3,2}, {15,0,0}, {159,0,0}, {12,10,8}, 
    637 {29,0,0}, {10,3,1}, {21,0,0}, {333,0,0}, {11,8,2}, {52,0,0}, 
    638 {119,0,0}, {16,9,7}, {123,0,0}, {15,11,2}, {17,0,0}, {9,0,0}, 
    639 {11,6,4}, {38,0,0}, {255,0,0}, {12,10,7}, {189,0,0}, {4,3,1}, 
    640 {17,10,7}, {49,0,0}, {13,5,2}, {149,0,0}, {15,0,0}, {14,7,5}, 
    641 {10,9,2}, {8,6,5}, {61,0,0}, {54,0,0}, {11,5,1}, {144,0,0}, 
    642 {47,0,0}, {11,10,7}, {105,0,0}, {2,0,0}, {105,0,0}, {136,0,0}, 
    643 {11,4,1}, {253,0,0}, {111,0,0}, {13,10,5}, {159,0,0}, {10,7,1}, 
    644 {7,5,3}, {29,0,0}, {19,10,3}, {119,0,0}, {207,0,0}, {17,15,4}, 
    645 {35,0,0}, {14,0,0}, {349,0,0}, {6,3,2}, {21,10,6}, {1,0,0}, 
    646 {75,0,0}, {9,5,2}, {145,0,0}, {11,7,6}, {301,0,0}, {378,0,0}, 
    647 {13,3,1}, {352,0,0}, {12,7,4}, {12,8,1}, {149,0,0}, {6,5,4}, 
    648 {12,9,8}, {11,0,0}, {15,7,5}, {78,0,0}, {99,0,0}, {17,16,12}, 
    649 {173,0,0}, {8,7,1}, {13,9,8}, {147,0,0}, {19,18,10}, {127,0,0}, 
    650 {183,0,0}, {12,4,1}, {31,0,0}, {11,8,6}, {173,0,0}, {12,0,0}, 
    651 {7,5,3}, {113,0,0}, {207,0,0}, {18,15,5}, {1,0,0}, {13,7,6}, 
    652 {21,0,0}, {35,0,0}, {12,7,2}, {117,0,0}, {123,0,0}, {12,10,2}, 
    653 {143,0,0}, {14,4,1}, {15,9,7}, {204,0,0}, {7,5,1}, {91,0,0}, 
    654 {4,2,1}, {8,6,3}, {183,0,0}, {12,10,7}, {77,0,0}, {36,0,0}, 
    655 {14,9,6}, {221,0,0}, {7,6,5}, {16,14,13}, {31,0,0}, {16,15,7}, 
    656 {365,0,0}, {403,0,0}, {10,3,2}, {11,4,3}, {31,0,0}, {10,9,4}, 
    657 {177,0,0}, {16,6,1}, {22,6,5}, {417,0,0}, {15,13,12}, {217,0,0}, 
    658 {207,0,0}, {7,5,4}, {10,7,1}, {11,6,1}, {45,0,0}, {24,0,0}, 
    659 {12,11,9}, {77,0,0}, {21,20,13}, {9,6,5}, {189,0,0}, {8,3,2}, 
    660 {13,12,10}, {260,0,0}, {16,9,7}, {168,0,0}, {131,0,0}, {7,6,3}, 
    661 {305,0,0}, {10,9,6}, {13,9,4}, {143,0,0}, {12,9,3}, {18,0,0}, 
    662 {15,8,5}, {20,9,6}, {103,0,0}, {15,4,2}, {201,0,0}, {36,0,0}, 
    663 {9,5,2}, {31,0,0}, {11,7,2}, {6,2,1}, {7,0,0}, {13,6,4}, 
    664 {9,8,7}, {19,0,0}, {17,10,6}, {15,0,0}, {9,3,1}, {178,0,0}, 
    665 {8,7,6}, {12,6,5}, {177,0,0}, {230,0,0}, {24,9,3}, {222,0,0}, 
    666 {3,0,0}, {16,13,12}, {121,0,0}, {10,4,2}, {161,0,0}, {39,0,0}, 
    667 {17,15,13}, {62,0,0}, {223,0,0}, {15,12,2}, {65,0,0}, {12,6,3}, 
    668 {101,0,0}, {59,0,0}, {5,4,3}, {17,0,0}, {5,3,2}, {13,8,3}, 
    669 {10,9,7}, {12,8,2}, {5,4,3}, {75,0,0}, {19,17,8}, {55,0,0}, 
    670 {99,0,0}, {10,7,4}, {115,0,0}, {9,8,6}, {385,0,0}, {186,0,0}, 
    671 {15,6,3}, {9,4,1}, {12,10,5}, {10,8,1}, {135,0,0}, {5,2,1}, 
    672 {317,0,0}, {7,0,0}, {19,6,1}, {294,0,0}, {35,0,0}, {13,12,6}, 
    673 {119,0,0}, {98,0,0}, {93,0,0}, {68,0,0}, {21,15,3}, {108,0,0}, 
    674 {75,0,0}, {12,6,5}, {411,0,0}, {12,7,2}, {13,7,2}, {21,0,0}, 
    675 {15,10,8}, {412,0,0}, {439,0,0}, {10,7,6}, {41,0,0}, {13,9,6}, 
    676 {8,5,2}, {10,0,0}, {15,7,2}, {141,0,0}, {159,0,0}, {13,12,10}, 
    677 {291,0,0}, {10,9,1}, {105,0,0}, {24,0,0}, {11,2,1}, {198,0,0}, 
    678 {27,0,0}, {6,3,1}, {439,0,0}, {10,3,1}, {49,0,0}, {168,0,0}, 
    679 {13,11,9}, {463,0,0}, {10,9,3}, {13,9,8}, {15,8,3}, {18,16,8}, 
    680 {15,14,11}, {7,0,0}, {19,9,8}, {12,6,3}, {7,4,3}, {15,14,5}, 
    681 {8,6,3}, {10,9,7}, {361,0,0}, {230,0,0}, {15,9,6}, {24,0,0}, 
    682 {407,0,0}, {16,7,2}, {189,0,0}, {62,0,0}, {189,0,0}, {112,0,0}, 
    683 {22,21,10}, {91,0,0}, {79,0,0}, {12,10,5}, {23,0,0}, {7,6,1}, 
    684 {57,0,0}, {139,0,0}, {24,15,6}, {14,0,0}, {83,0,0}, {16,9,1}, 
    685 {35,0,0}, {9,7,4}, {117,0,0}, {65,0,0}, {21,9,6}, {21,0,0}, 
    686 {195,0,0}, {23,11,10}, {327,0,0}, {17,14,3}, {417,0,0}, {13,0,0}, 
    687 {15,8,6}, {107,0,0}, {19,10,6}, {18,15,3}, {59,0,0}, {12,10,4}, 
    688 {9,7,5}, {283,0,0}, {13,9,6}, {62,0,0}, {427,0,0}, {14,7,3}, 
    689 {8,7,4}, {15,8,3}, {105,0,0}, {27,0,0}, {7,3,1}, {103,0,0}, 
    690 {551,0,0}, {10,6,1}, {6,4,1}, {11,6,4}, {129,0,0}, {9,0,0}, 
    691 {9,4,2}, {277,0,0}, {31,0,0}, {13,12,5}, {141,0,0}, {12,7,3}, 
    692 {357,0,0}, {7,2,1}, {11,9,7}, {227,0,0}, {131,0,0}, {7,6,3}, 
    693 {23,0,0}, {20,17,3}, {13,4,1}, {90,0,0}, {15,3,2}, {241,0,0}, 
    694 {75,0,0}, {13,6,1}, {307,0,0}, {8,7,3}, {245,0,0}, {66,0,0}, 
    695 {15,11,2}, {365,0,0}, {18,16,11}, {11,10,1}, {19,0,0}, {8,6,1}, 
    696 {189,0,0}, {133,0,0}, {12,7,2}, {114,0,0}, {27,0,0}, {6,5,1}, 
    697 {15,5,2}, {17,14,5}, {133,0,0}, {476,0,0}, {11,9,3}, {16,0,0}, 
    698 {375,0,0}, {15,8,6}, {25,0,0}, {17,11,6}, {77,0,0}, {87,0,0}, 
    699 {5,3,2}, {134,0,0}, {171,0,0}, {13,8,4}, {75,0,0}, {8,3,1}, 
    700 {233,0,0}, {196,0,0}, {9,8,7}, {173,0,0}, {15,14,12}, {13,6,5}, 
    701 {281,0,0}, {9,8,2}, {405,0,0}, {114,0,0}, {15,9,6}, {171,0,0}, 
    702 {287,0,0}, {8,4,2}, {43,0,0}, {4,2,1}, {513,0,0}, {273,0,0}, 
    703 {11,10,6}, {118,0,0}, {243,0,0}, {14,7,1}, {203,0,0}, {9,5,2}, 
    704 {257,0,0}, {302,0,0}, {27,25,9}, {393,0,0}, {91,0,0}, {12,10,6}, 
    705 {413,0,0}, {15,14,9}, {18,16,1}, {255,0,0}, {12,9,7}, {234,0,0}, 
    706 {167,0,0}, {16,13,10}, {27,0,0}, {15,6,2}, {433,0,0}, {105,0,0}, 
    707 {25,10,2}, {151,0,0}, {427,0,0}, {13,9,8}, {49,0,0}, {10,6,4}, 
    708 {153,0,0}, {4,0,0}, {17,7,5}, {54,0,0}, {203,0,0}, {16,15,1}, 
    709 {16,14,7}, {13,6,1}, {25,0,0}, {14,0,0}, {15,5,3}, {187,0,0}, 
    710 {15,13,10}, {13,10,5}, {97,0,0}, {11,10,9}, {19,10,4}, {589,0,0}, 
    711 {31,30,2}, {289,0,0}, {9,6,4}, {11,8,6}, {21,0,0}, {7,4,1}, 
    712 {7,4,2}, {77,0,0}, {5,3,2}, {119,0,0}, {7,0,0}, {9,5,2}, 
    713 {345,0,0}, {17,10,8}, {333,0,0}, {17,0,0}, {16,9,7}, {168,0,0}, 
    714 {15,13,4}, {11,10,1}, {217,0,0}, {18,11,10}, {189,0,0}, {216,0,0}, 
    715 {12,7,5}, {229,0,0}, {231,0,0}, {12,9,3}, {223,0,0}, {10,9,1}, 
    716 {153,0,0}, {470,0,0}, {23,16,6}, {99,0,0}, {10,4,3}, {9,8,4}, 
    717 {12,10,1}, {14,9,6}, {201,0,0}, {38,0,0}, {15,14,2}, {198,0,0}, 
    718 {399,0,0}, {14,11,5}, {75,0,0}, {11,10,1}, {77,0,0}, {16,12,8}, 
    719 {20,17,15}, {326,0,0}, {39,0,0}, {14,12,9}, {495,0,0}, {8,3,2}, 
    720 {333,0,0}, {476,0,0}, {15,14,2}, {164,0,0}, {19,0,0}, {12,4,2}, 
    721 {8,6,3}, {13,12,3}, {12,11,5}, {129,0,0}, {12,9,3}, {52,0,0}, 
    722 {10,8,3}, {17,16,2}, {337,0,0}, {12,9,3}, {397,0,0}, {277,0,0}, 
    723 {21,11,3}, {73,0,0}, {11,6,1}, {7,5,4}, {95,0,0}, {11,3,2}, 
    724 {617,0,0}, {392,0,0}, {8,3,2}, {75,0,0}, {315,0,0}, {15,6,4}, 
    725 {125,0,0}, {6,5,2}, {15,9,7}, {348,0,0}, {15,6,1}, {553,0,0}, 
    726 {6,3,2}, {10,9,7}, {553,0,0}, {14,10,4}, {237,0,0}, {39,0,0}, 
    727 {17,14,6}, {371,0,0}, {255,0,0}, {8,4,1}, {131,0,0}, {14,6,1}, 
    728 {117,0,0}, {98,0,0}, {5,3,2}, {56,0,0}, {655,0,0}, {9,5,2}, 
    729 {239,0,0}, {11,8,4}, {1,0,0}, {134,0,0}, {15,9,5}, {88,0,0}, 
    730 {10,5,3}, {10,9,4}, {181,0,0}, {15,11,2}, {609,0,0}, {52,0,0}, 
    731 {19,18,10}, {100,0,0}, {7,6,3}, {15,8,2}, {183,0,0}, {18,7,6}, 
    732 {10,9,2}, {130,0,0}, {11,5,1}, {12,0,0}, {219,0,0}, {13,10,7}, 
    733 {11,0,0}, {19,9,4}, {129,0,0}, {3,0,0}, {17,15,5}, {300,0,0}, 
    734 {17,13,9}, {14,6,5}, {97,0,0}, {13,8,3}, {601,0,0}, {55,0,0}, 
    735 {8,3,1}, {92,0,0}, {127,0,0}, {12,11,2}, {81,0,0}, {15,10,8}, 
    736 {13,2,1}, {47,0,0}, {14,13,6}, {194,0,0}, {383,0,0}, {25,14,11}, 
    737 {125,0,0}, {20,19,16}, {429,0,0}, {282,0,0}, {10,9,6}, {342,0,0}, 
    738 {5,3,2}, {15,9,4}, {33,0,0}, {9,4,2}, {49,0,0}, {15,0,0}, 
    739 {11,6,2}, {28,0,0}, {103,0,0}, {18,17,8}, {27,0,0}, {11,6,5}, 
    740 {33,0,0}, {17,0,0}, {11,10,6}, {387,0,0}, {363,0,0}, {15,10,9}, 
    741 {83,0,0}, {7,6,4}, {357,0,0}, {13,12,4}, {14,13,7}, {322,0,0}, 
    742 {395,0,0}, {16,5,1}, {595,0,0}, {13,10,3}, {421,0,0}, {195,0,0}, 
    743 {11,3,2}, {13,0,0}, {16,12,3}, {14,3,1}, {315,0,0}, {26,10,5}, 
    744 {297,0,0}, {52,0,0}, {9,4,2}, {314,0,0}, {243,0,0}, {16,14,9}, 
    745 {185,0,0}, {12,5,3}, {13,5,2}, {575,0,0}, {12,9,3}, {39,0,0}, 
    746 {311,0,0}, {13,5,2}, {181,0,0}, {20,18,14}, {49,0,0}, {25,0,0}, 
    747 {11,4,1}, {77,0,0}, {17,11,10}, {15,14,8}, {21,0,0}, {17,10,5}, 
    748 {69,0,0}, {49,0,0}, {11,10,2}, {32,0,0}, {411,0,0}, {21,16,3}, 
    749 {11,7,4}, {22,10,3}, {85,0,0}, {140,0,0}, {9,8,6}, {252,0,0}, 
    750 {279,0,0}, {9,5,2}, {307,0,0}, {17,10,4}, {13,12,9}, {94,0,0}, 
    751 {13,11,4}, {49,0,0}, {17,11,10}, {16,12,5}, {25,0,0}, {6,5,2}, 
    752 {12,5,1}, {80,0,0}, {8,3,2}, {246,0,0}, {11,5,2}, {11,10,2}, 
    753 {599,0,0}, {18,12,10}, {189,0,0}, {278,0,0}, {10,9,3}, {399,0,0}, 
    754 {299,0,0}, {13,10,6}, {277,0,0}, {13,10,6}, {69,0,0}, {220,0,0}, 
    755 {13,10,3}, {229,0,0}, {18,11,10}, {16,15,1}, {27,0,0}, {18,9,3}, 
    756 {473,0,0}, {373,0,0}, {18,17,7}, {60,0,0}, {207,0,0}, {13,9,8}, 
    757 {22,20,13}, {25,18,7}, {225,0,0}, {404,0,0}, {21,6,2}, {46,0,0}, 
    758 {6,2,1}, {17,12,6}, {75,0,0}, {4,2,1}, {365,0,0}, {445,0,0}, 
    759 {11,7,1}, {44,0,0}, {10,8,5}, {12,5,2}, {63,0,0}, {17,4,2}, 
    760 {189,0,0}, {557,0,0}, {19,12,2}, {252,0,0}, {99,0,0}, {10,8,5}, 
    761 {65,0,0}, {14,9,3}, {9,0,0}, {119,0,0}, {8,5,2}, {339,0,0}, 
    762 {95,0,0}, {12,9,7}, {7,0,0}, {13,10,2}, {77,0,0}, {127,0,0}, 
    763 {21,10,7}, {319,0,0}, {667,0,0}, {17,10,3}, {501,0,0}, {18,12,9}, 
    764 {9,8,5}, {17,0,0}, {20,9,2}, {341,0,0}, {731,0,0}, {7,6,5}, 
    765 {647,0,0}, {10,4,2}, {121,0,0}, {20,0,0}, {21,19,13}, {574,0,0}, 
    766 {399,0,0}, {15,10,7}, {85,0,0}, {16,8,3}, {169,0,0}, {15,0,0}, 
    767 {12,7,5}, {568,0,0}, {10,7,1}, {18,2,1}, {3,0,0}, {14,3,2}, 
    768 {13,7,3}, {643,0,0}, {14,11,1}, {548,0,0}, {783,0,0}, {14,11,1}, 
    769 {317,0,0}, {7,6,4}, {153,0,0}, {87,0,0}, {15,13,1}, {231,0,0}, 
    770 {11,5,3}, {18,13,7}, {771,0,0}, {30,20,11}, {15,6,3}, {103,0,0}, 
    771 {13,4,3}, {182,0,0}, {211,0,0}, {17,6,1}, {27,0,0}, {13,12,10}, 
    772 {15,14,10}, {17,0,0}, {13,11,5}, {69,0,0}, {11,5,1}, {18,6,1}, 
    773 {603,0,0}, {10,4,2}, {741,0,0}, {668,0,0}, {17,15,3}, {147,0,0}, 
    774 {227,0,0}, {15,10,9}, {37,0,0}, {16,6,1}, {173,0,0}, {427,0,0}, 
    775 {7,5,1}, {287,0,0}, {231,0,0}, {20,15,10}, {18,9,1}, {14,12,5}, 
    776 {16,5,1}, {310,0,0}, {18,13,1}, {434,0,0}, {579,0,0}, {18,13,8}, 
    777 {45,0,0}, {12,8,3}, {16,9,5}, {53,0,0}, {19,15,10}, {16,0,0}, 
    778 {17,6,5}, {17,10,1}, {37,0,0}, {17,10,9}, {21,13,7}, {99,0,0}, 
    779 {17,9,6}, {176,0,0}, {271,0,0}, {18,17,13}, {459,0,0}, {21,17,10}, 
    780 {6,5,2}, {202,0,0}, {5,4,3}, {90,0,0}, {755,0,0}, {15,7,2}, 
    781 {363,0,0}, {8,4,2}, {129,0,0}, {20,0,0}, {11,6,2}, {135,0,0}, 
    782 {15,8,7}, {14,13,2}, {10,4,3}, {24,13,10}, {19,14,11}, {31,0,0}, 
    783 {15,8,6}, {758,0,0}, {16,11,5}, {16,5,1}, {359,0,0}, {23,18,17}, 
    784 {501,0,0}, {29,0,0}, {15,6,3}, {201,0,0}, {459,0,0}, {12,10,7}, 
    785 {225,0,0}, {22,17,13}, {24,22,5}, {161,0,0}, {14,11,3}, {52,0,0}, 
    786 {19,17,6}, {21,14,12}, {93,0,0}, {13,10,3}, {201,0,0}, {178,0,0}, 
    787 {15,12,5}, {250,0,0}, {7,6,4}, {17,13,6}, {221,0,0}, {13,11,8}, 
    788 {17,14,9}, {113,0,0}, {17,14,10}, {300,0,0}, {39,0,0}, {18,13,3}, 
    789 {261,0,0}, {15,14,8}, {753,0,0}, {8,4,3}, {11,10,5}, {94,0,0}, 
    790 {15,13,1}, {10,4,2}, {14,11,10}, {8,6,2}, {461,0,0}, {418,0,0}, 
    791 {19,14,6}, {403,0,0}, {267,0,0}, {10,9,2}, {259,0,0}, {20,4,3}, 
    792 {869,0,0}, {173,0,0}, {19,18,2}, {369,0,0}, {255,0,0}, {22,12,9}, 
    793 {567,0,0}, {20,11,7}, {457,0,0}, {482,0,0}, {6,3,2}, {775,0,0}, 
    794 {19,17,6}, {6,4,3}, {99,0,0}, {15,14,8}, {6,5,2}, {165,0,0}, 
    795 {8,3,2}, {13,12,10}, {25,21,17}, {17,14,9}, {105,0,0}, {17,15,14}, 
    796 {10,3,2}, {250,0,0}, {25,6,5}, {327,0,0}, {279,0,0}, {13,6,5}, 
    797 {371,0,0}, {15,9,4}, {117,0,0}, {486,0,0}, {10,9,3}, {217,0,0}, 
    798 {635,0,0}, {30,27,17}, {457,0,0}, {16,6,2}, {57,0,0}, {439,0,0}, 
    799 {23,21,6}, {214,0,0}, {20,13,6}, {20,16,1}, {819,0,0}, {15,11,8}, 
    800 {593,0,0}, {190,0,0}, {17,14,3}, {114,0,0}, {21,18,3}, {10,5,2}, 
    801 {12,9,5}, {8,6,3}, {69,0,0}, {312,0,0}, {22,5,2}, {502,0,0}, 
    802 {843,0,0}, {15,10,3}, {747,0,0}, {6,5,2}, {101,0,0}, {123,0,0}, 
    803 {19,16,9}, {521,0,0}, {171,0,0}, {16,7,2}, {12,6,5}, {22,21,20}, 
    804 {545,0,0}, {163,0,0}, {23,18,1}, {479,0,0}, {495,0,0}, {13,6,5}, 
    805 {11,0,0}, {17,5,2}, {18,8,1}, {684,0,0}, {7,5,1}, {9,0,0}, 
    806 {18,11,3}, {22,20,13}, {273,0,0}, {4,3,2}, {381,0,0}, {51,0,0}, 
    807 {18,13,7}, {518,0,0}, {9,5,1}, {14,12,3}, {243,0,0}, {21,17,2}, 
    808 {53,0,0}, {836,0,0}, {21,10,2}, {66,0,0}, {12,10,7}, {13,9,8}, 
    809 {339,0,0}, {16,11,5}, {901,0,0}, {180,0,0}, {16,13,3}, {49,0,0}, 
    810 {6,3,2}, {15,4,1}, {16,13,6}, {18,15,12}, {885,0,0}, {39,0,0}, 
    811 {11,9,4}, {688,0,0}, {16,15,7}, {13,10,6}, {13,0,0}, {25,23,12}, 
    812 {149,0,0}, {260,0,0}, {11,9,1}, {53,0,0}, {11,0,0}, {12,4,2}, 
    813 {9,7,5}, {11,8,1}, {121,0,0}, {261,0,0}, {10,5,2}, {199,0,0}, 
    814 {20,4,3}, {17,9,2}, {13,9,4}, {12,8,7}, {253,0,0}, {174,0,0}, 
    815 {15,4,2}, {370,0,0}, {9,6,1}, {16,10,9}, {669,0,0}, {20,10,9}, 
    816 {833,0,0}, {353,0,0}, {17,13,2}, {29,0,0}, {371,0,0}, {9,8,5}, 
    817 {8,7,1}, {19,8,7}, {12,11,10}, {873,0,0}, {26,11,2}, {12,9,1}, 
    818 {10,7,2}, {13,6,1}, {235,0,0}, {26,24,19}, {733,0,0}, {778,0,0}, 
    819 {12,11,1}, {344,0,0}, {931,0,0}, {16,6,4}, {945,0,0}, {21,19,14}, 
    820 {18,13,11}, {67,0,0}, {20,15,10}, {462,0,0}, {14,5,1}, {10,9,6}, 
    821 {18,11,10}, {16,9,7}, {477,0,0}, {105,0,0}, {11,3,2}, {468,0,0}, 
    822 {23,16,15}, {16,15,6}, {327,0,0}, {23,10,4}, {357,0,0}, {25,0,0}, 
    823 {17,16,7}, {31,0,0}, {7,5,2}, {16,7,6}, {277,0,0}, {14,13,6}, 
    824 {413,0,0}, {103,0,0}, {15,10,1}, {231,0,0}, {747,0,0}, {5,2,1}, 
    825 {113,0,0}, {20,10,7}, {15,9,6}, {11,0,0}, {27,22,18}, {91,0,0}, 
    826 {51,0,0}, {18,13,12}, {603,0,0}, {10,7,3}, {9,0,0}, {121,0,0}, 
    827 {15,14,6}, {17,0,0}, {16,11,2}, {23,15,6}, {279,0,0}, {16,12,6}, 
    828 {89,0,0}, {371,0,0}, {17,15,2}, {771,0,0}, {99,0,0}, {7,6,3}, 
    829 {21,0,0}, {10,7,5}, {801,0,0}, {26,0,0}, {25,19,14}, {175,0,0}, 
    830 {10,7,2}, {20,5,4}, {12,11,1}, {22,5,1}, {165,0,0}, {841,0,0}, 
    831 {25,19,17}, {238,0,0}, {11,8,6}, {22,21,4}, {33,0,0}, {8,7,6}, 
    832 {14,9,2}, {113,0,0}, {13,11,5}, {311,0,0}, {891,0,0}, {20,16,14}, 
    833 {555,0,0}, {23,14,8}, {133,0,0}, {546,0,0}, {6,3,2}, {103,0,0}, 
    834 {15,0,0}, {10,7,3}, {307,0,0}, {14,10,1}, {15,12,2}, {367,0,0}, 
    835 {13,10,6}, {169,0,0}, {22,21,11}, {12,10,8}, {441,0,0}, {17,12,7}, 
    836 {917,0,0}, {205,0,0}, {26,23,13}, {54,0,0}, {459,0,0}, {17,15,4}, 
    837 {19,15,4}, {5,4,2}, {9,7,6}, {42,0,0}, {21,15,7}, {330,0,0}, 
    838 {20,7,3}, {20,7,2}, {81,0,0}, {19,14,1}, {349,0,0}, {165,0,0}, 
    839 {40,35,9}, {274,0,0}, {475,0,0}, {11,10,3}, {93,0,0}, {12,7,4}, 
    840 {13,12,2}, {386,0,0}, {7,6,2}, {881,0,0}, {143,0,0}, {9,8,4}, 
    841 {71,0,0}, {19,18,3}, {16,11,6}, {155,0,0}, {7,2,1}, {735,0,0}, 
    842 {16,8,7}, {9,7,4}, {45,0,0}, {7,6,4}, {12,11,3}, {3,0,0}, 
     502{1,0,0}, {1,0,0}, {1,0,0}, {2,0,0}, {1,0,0}, {1,0,0},
     503{4,3,1}, {1,0,0}, {3,0,0}, {2,0,0}, {3,0,0}, {4,3,1},
     504{5,0,0}, {1,0,0}, {5,3,1}, {3,0,0}, {3,0,0}, {5,2,1},
     505{3,0,0}, {2,0,0}, {1,0,0}, {5,0,0}, {4,3,1}, {3,0,0},
     506{4,3,1}, {5,2,1}, {1,0,0}, {2,0,0}, {1,0,0}, {3,0,0},
     507{7,3,2}, {10,0,0}, {7,0,0}, {2,0,0}, {9,0,0}, {6,4,1},
     508{6,5,1}, {4,0,0}, {5,4,3}, {3,0,0}, {7,0,0}, {6,4,3},
     509{5,0,0}, {4,3,1}, {1,0,0}, {5,0,0}, {5,3,2}, {9,0,0},
     510{4,3,2}, {6,3,1}, {3,0,0}, {6,2,1}, {9,0,0}, {7,0,0},
     511{7,4,2}, {4,0,0}, {19,0,0}, {7,4,2}, {1,0,0}, {5,2,1},
     512{29,0,0}, {1,0,0}, {4,3,1}, {18,0,0}, {3,0,0}, {5,2,1},
     513{9,0,0}, {6,5,2}, {5,3,1}, {6,0,0}, {10,9,3}, {25,0,0},
     514{35,0,0}, {6,3,1}, {21,0,0}, {6,5,2}, {6,5,3}, {9,0,0},
     515{9,4,2}, {4,0,0}, {8,3,1}, {7,4,2}, {5,0,0}, {8,2,1},
     516{21,0,0}, {13,0,0}, {7,6,2}, {38,0,0}, {27,0,0}, {8,5,1},
     517{21,0,0}, {2,0,0}, {21,0,0}, {11,0,0}, {10,9,6}, {6,0,0},
     518{11,0,0}, {6,3,1}, {15,0,0}, {7,6,1}, {29,0,0}, {9,0,0},
     519{4,3,1}, {4,0,0}, {15,0,0}, {9,7,4}, {17,0,0}, {5,4,2},
     520{33,0,0}, {10,0,0}, {5,4,3}, {9,0,0}, {5,3,2}, {8,7,5},
     521{4,2,1}, {5,2,1}, {33,0,0}, {8,0,0}, {4,3,1}, {18,0,0},
     522{6,2,1}, {2,0,0}, {19,0,0}, {7,6,5}, {21,0,0}, {1,0,0},
     523{7,2,1}, {5,0,0}, {3,0,0}, {8,3,2}, {17,0,0}, {9,8,2},
     524{57,0,0}, {11,0,0}, {5,3,2}, {21,0,0}, {8,7,1}, {8,5,3},
     525{15,0,0}, {10,4,1}, {21,0,0}, {5,3,2}, {7,4,2}, {52,0,0},
     526{71,0,0}, {14,0,0}, {27,0,0}, {10,9,7}, {53,0,0}, {3,0,0},
     527{6,3,2}, {1,0,0}, {15,0,0}, {62,0,0}, {9,0,0}, {6,5,2},
     528{8,6,5}, {31,0,0}, {5,3,2}, {18,0,0}, {27,0,0}, {7,6,3},
     529{10,8,7}, {9,8,3}, {37,0,0}, {6,0,0}, {15,3,2}, {34,0,0},
     530{11,0,0}, {6,5,2}, {1,0,0}, {8,5,2}, {13,0,0}, {6,0,0},
     531{11,3,2}, {8,0,0}, {31,0,0}, {4,2,1}, {3,0,0}, {7,6,1},
     532{81,0,0}, {56,0,0}, {9,8,7}, {24,0,0}, {11,0,0}, {7,6,5},
     533{6,5,2}, {6,5,2}, {8,7,6}, {9,0,0}, {7,2,1}, {15,0,0},
     534{87,0,0}, {8,3,2}, {3,0,0}, {9,4,2}, {9,0,0}, {34,0,0},
     535{5,3,2}, {14,0,0}, {55,0,0}, {8,7,1}, {27,0,0}, {9,5,2},
     536{10,9,5}, {43,0,0}, {9,3,1}, {6,0,0}, {7,0,0}, {11,10,8},
     537{105,0,0}, {6,5,2}, {73,0,0}, {23,0,0}, {7,3,1}, {45,0,0},
     538{11,0,0}, {8,4,1}, {7,0,0}, {8,6,2}, {5,4,2}, {33,0,0},
     539{9,8,3}, {32,0,0}, {10,7,3}, {10,9,4}, {113,0,0}, {10,4,1},
     540{8,7,6}, {26,0,0}, {9,4,2}, {74,0,0}, {31,0,0}, {9,6,1},
     541{5,0,0}, {7,4,1}, {73,0,0}, {36,0,0}, {8,5,3}, {70,0,0},
     542{95,0,0}, {8,5,1}, {111,0,0}, {6,4,1}, {11,2,1}, {82,0,0},
     543{15,14,10}, {35,0,0}, {103,0,0}, {7,4,2}, {15,0,0}, {46,0,0},
     544{7,2,1}, {52,0,0}, {10,5,2}, {12,0,0}, {71,0,0}, {10,6,2},
     545{15,0,0}, {7,6,4}, {9,8,4}, {93,0,0}, {9,6,2}, {42,0,0},
     546{47,0,0}, {8,6,3}, {25,0,0}, {7,6,1}, {53,0,0}, {58,0,0},
     547{9,3,2}, {23,0,0}, {67,0,0}, {11,10,9}, {63,0,0}, {12,6,3},
     548{5,0,0}, {5,0,0}, {9,5,2}, {93,0,0}, {35,0,0}, {12,7,5},
     549{53,0,0}, {10,7,5}, {69,0,0}, {71,0,0}, {11,10,1}, {21,0,0},
     550{5,3,2}, {12,11,5}, {37,0,0}, {11,6,1}, {33,0,0}, {48,0,0},
     551{7,3,2}, {5,0,0}, {11,8,4}, {11,6,4}, {5,0,0}, {9,5,2},
     552{41,0,0}, {1,0,0}, {11,2,1}, {102,0,0}, {7,3,1}, {8,4,2},
     553{15,0,0}, {10,6,4}, {93,0,0}, {7,5,3}, {9,7,4}, {79,0,0},
     554{15,0,0}, {10,9,1}, {63,0,0}, {7,4,2}, {45,0,0}, {36,0,0},
     555{4,3,1}, {31,0,0}, {67,0,0}, {10,3,1}, {51,0,0}, {10,5,2},
     556{10,3,1}, {34,0,0}, {8,3,1}, {50,0,0}, {99,0,0}, {10,6,2},
     557{89,0,0}, {2,0,0}, {5,2,1}, {10,7,2}, {7,4,1}, {55,0,0},
     558{4,3,1}, {16,10,7}, {45,0,0}, {10,8,6}, {125,0,0}, {75,0,0},
     559{7,2,1}, {22,0,0}, {63,0,0}, {11,10,3}, {103,0,0}, {6,5,2},
     560{53,0,0}, {34,0,0}, {13,11,6}, {69,0,0}, {99,0,0}, {6,5,1},
     561{10,9,7}, {11,10,2}, {57,0,0}, {68,0,0}, {5,3,2}, {7,4,1},
     562{63,0,0}, {8,5,3}, {9,0,0}, {9,6,5}, {29,0,0}, {21,0,0},
     563{7,3,2}, {91,0,0}, {139,0,0}, {8,3,2}, {111,0,0}, {8,7,2},
     564{8,6,5}, {16,0,0}, {8,7,5}, {41,0,0}, {43,0,0}, {10,8,5},
     565{47,0,0}, {5,2,1}, {81,0,0}, {90,0,0}, {12,3,2}, {6,0,0},
     566{83,0,0}, {8,7,1}, {159,0,0}, {10,9,5}, {9,0,0}, {28,0,0},
     567{13,10,6}, {7,0,0}, {135,0,0}, {11,6,5}, {25,0,0}, {12,7,6},
     568{7,6,2}, {26,0,0}, {5,3,2}, {152,0,0}, {171,0,0}, {9,8,5},
     569{65,0,0}, {13,8,2}, {141,0,0}, {71,0,0}, {5,3,2}, {87,0,0},
     570{10,4,3}, {12,10,3}, {147,0,0}, {10,7,6}, {13,0,0}, {102,0,0},
     571{9,5,2}, {107,0,0}, {199,0,0}, {15,5,4}, {7,0,0}, {5,4,2},
     572{149,0,0}, {25,0,0}, {9,7,2}, {12,0,0}, {63,0,0}, {11,6,5},
     573{105,0,0}, {10,8,7}, {14,6,1}, {120,0,0}, {13,4,3}, {33,0,0},
     574{12,11,5}, {12,9,5}, {165,0,0}, {6,2,1}, {65,0,0}, {49,0,0},
     575{4,3,1}, {7,0,0}, {7,5,2}, {10,6,1}, {81,0,0}, {7,6,4},
     576{105,0,0}, {73,0,0}, {11,6,4}, {134,0,0}, {47,0,0}, {16,10,1},
     577{6,5,4}, {15,6,4}, {8,6,1}, {38,0,0}, {18,9,6}, {16,0,0},
     578{203,0,0}, {12,5,2}, {19,0,0}, {7,6,1}, {73,0,0}, {93,0,0},
     579{19,18,13}, {31,0,0}, {14,11,6}, {11,6,1}, {27,0,0}, {9,5,2},
     580{9,0,0}, {1,0,0}, {11,3,2}, {200,0,0}, {191,0,0}, {9,8,4},
     581{9,0,0}, {16,15,7}, {121,0,0}, {104,0,0}, {15,9,6}, {138,0,0},
     582{9,6,5}, {9,6,4}, {105,0,0}, {17,16,6}, {81,0,0}, {94,0,0},
     583{4,3,1}, {83,0,0}, {219,0,0}, {11,6,3}, {7,0,0}, {10,5,3},
     584{17,0,0}, {76,0,0}, {16,5,2}, {78,0,0}, {155,0,0}, {11,6,5},
     585{27,0,0}, {5,4,2}, {8,5,4}, {3,0,0}, {15,14,6}, {156,0,0},
     586{23,0,0}, {13,6,3}, {9,0,0}, {8,7,3}, {69,0,0}, {10,0,0},
     587{8,5,2}, {26,0,0}, {67,0,0}, {14,7,4}, {21,0,0}, {12,10,2},
     588{33,0,0}, {79,0,0}, {15,11,2}, {32,0,0}, {39,0,0}, {13,6,2},
     589{167,0,0}, {6,4,1}, {97,0,0}, {47,0,0}, {11,6,2}, {42,0,0},
     590{10,7,3}, {10,5,4}, {1,0,0}, {4,3,2}, {161,0,0}, {8,6,2},
     591{7,5,3}, {94,0,0}, {195,0,0}, {10,5,4}, {9,0,0}, {13,10,4},
     592{8,6,1}, {16,0,0}, {8,3,1}, {122,0,0}, {8,2,1}, {13,7,4},
     593{10,5,3}, {16,4,3}, {193,0,0}, {135,0,0}, {19,16,9}, {39,0,0},
     594{10,8,7}, {10,9,4}, {153,0,0}, {7,6,5}, {73,0,0}, {34,0,0},
     595{11,9,6}, {71,0,0}, {11,4,2}, {14,7,3}, {163,0,0}, {11,6,1},
     596{153,0,0}, {28,0,0}, {15,7,6}, {77,0,0}, {67,0,0}, {10,5,2},
     597{12,8,1}, {10,6,4}, {13,0,0}, {146,0,0}, {13,4,3}, {25,0,0},
     598{23,22,16}, {12,9,7}, {237,0,0}, {13,7,6}, {85,0,0}, {130,0,0},
     599{14,13,3}, {88,0,0}, {7,5,2}, {11,6,1}, {35,0,0}, {10,4,3},
     600{93,0,0}, {9,6,4}, {13,6,3}, {86,0,0}, {19,0,0}, {9,2,1},
     601{273,0,0}, {14,12,9}, {7,6,1}, {30,0,0}, {9,5,2}, {201,0,0},
     602{215,0,0}, {6,4,3}, {105,0,0}, {10,7,5}, {165,0,0}, {105,0,0},
     603{19,13,6}, {31,0,0}, {127,0,0}, {10,4,2}, {81,0,0}, {19,10,4},
     604{45,0,0}, {211,0,0}, {19,10,3}, {200,0,0}, {295,0,0}, {9,8,5},
     605{9,0,0}, {12,6,5}, {297,0,0}, {68,0,0}, {11,6,5}, {133,0,0},
     606{251,0,0}, {13,8,4}, {223,0,0}, {6,5,2}, {7,4,2}, {307,0,0},
     607{9,2,1}, {101,0,0}, {39,0,0}, {14,10,4}, {217,0,0}, {14,9,1},
     608{6,5,1}, {16,0,0}, {14,3,2}, {11,0,0}, {119,0,0}, {11,3,2},
     609{11,6,5}, {11,8,4}, {249,0,0}, {5,0,0}, {13,3,1}, {37,0,0},
     610{3,0,0}, {14,0,0}, {93,0,0}, {10,8,7}, {33,0,0}, {88,0,0},
     611{7,5,4}, {38,0,0}, {55,0,0}, {15,4,2}, {11,0,0}, {12,11,4},
     612{21,0,0}, {107,0,0}, {11,9,8}, {33,0,0}, {10,7,2}, {18,7,3},
     613{147,0,0}, {5,4,2}, {153,0,0}, {15,0,0}, {11,6,5}, {28,0,0},
     614{11,7,4}, {6,3,1}, {31,0,0}, {8,4,3}, {15,5,3}, {66,0,0},
     615{23,16,9}, {11,9,3}, {171,0,0}, {11,6,1}, {209,0,0}, {4,3,1},
     616{197,0,0}, {13,0,0}, {19,14,6}, {14,0,0}, {79,0,0}, {13,6,2},
     617{299,0,0}, {15,8,2}, {169,0,0}, {177,0,0}, {23,10,2}, {267,0,0},
     618{215,0,0}, {15,10,1}, {75,0,0}, {16,4,2}, {37,0,0}, {12,7,1},
     619{8,3,2}, {17,0,0}, {12,11,8}, {15,8,5}, {15,0,0}, {4,3,1},
     620{13,12,4}, {92,0,0}, {5,4,3}, {41,0,0}, {23,0,0}, {7,4,1},
     621{183,0,0}, {16,7,1}, {165,0,0}, {150,0,0}, {9,6,4}, {9,0,0},
     622{231,0,0}, {16,10,4}, {207,0,0}, {9,6,5}, {5,0,0}, {180,0,0},
     623{4,3,2}, {58,0,0}, {147,0,0}, {8,6,2}, {343,0,0}, {8,7,2},
     624{11,6,1}, {44,0,0}, {13,8,6}, {5,0,0}, {347,0,0}, {18,16,8},
     625{135,0,0}, {9,8,3}, {85,0,0}, {90,0,0}, {13,11,1}, {258,0,0},
     626{351,0,0}, {10,6,4}, {19,0,0}, {7,6,1}, {309,0,0}, {18,0,0},
     627{13,10,3}, {158,0,0}, {19,0,0}, {12,10,1}, {45,0,0}, {7,6,1},
     628{233,0,0}, {98,0,0}, {11,6,5}, {3,0,0}, {83,0,0}, {16,14,9},
     629{6,5,3}, {9,7,4}, {22,19,9}, {168,0,0}, {19,17,4}, {120,0,0},
     630{14,5,2}, {17,15,6}, {7,0,0}, {10,8,6}, {185,0,0}, {93,0,0},
     631{15,14,7}, {29,0,0}, {375,0,0}, {10,8,3}, {13,0,0}, {17,16,2},
     632{329,0,0}, {68,0,0}, {13,9,6}, {92,0,0}, {12,10,3}, {7,6,3},
     633{17,10,3}, {5,2,1}, {9,6,1}, {30,0,0}, {9,7,3}, {253,0,0},
     634{143,0,0}, {7,4,1}, {9,4,1}, {12,10,4}, {53,0,0}, {25,0,0},
     635{9,7,1}, {217,0,0}, {15,13,9}, {14,9,2}, {75,0,0}, {8,7,2},
     636{21,0,0}, {7,0,0}, {14,3,2}, {15,0,0}, {159,0,0}, {12,10,8},
     637{29,0,0}, {10,3,1}, {21,0,0}, {333,0,0}, {11,8,2}, {52,0,0},
     638{119,0,0}, {16,9,7}, {123,0,0}, {15,11,2}, {17,0,0}, {9,0,0},
     639{11,6,4}, {38,0,0}, {255,0,0}, {12,10,7}, {189,0,0}, {4,3,1},
     640{17,10,7}, {49,0,0}, {13,5,2}, {149,0,0}, {15,0,0}, {14,7,5},
     641{10,9,2}, {8,6,5}, {61,0,0}, {54,0,0}, {11,5,1}, {144,0,0},
     642{47,0,0}, {11,10,7}, {105,0,0}, {2,0,0}, {105,0,0}, {136,0,0},
     643{11,4,1}, {253,0,0}, {111,0,0}, {13,10,5}, {159,0,0}, {10,7,1},
     644{7,5,3}, {29,0,0}, {19,10,3}, {119,0,0}, {207,0,0}, {17,15,4},
     645{35,0,0}, {14,0,0}, {349,0,0}, {6,3,2}, {21,10,6}, {1,0,0},
     646{75,0,0}, {9,5,2}, {145,0,0}, {11,7,6}, {301,0,0}, {378,0,0},
     647{13,3,1}, {352,0,0}, {12,7,4}, {12,8,1}, {149,0,0}, {6,5,4},
     648{12,9,8}, {11,0,0}, {15,7,5}, {78,0,0}, {99,0,0}, {17,16,12},
     649{173,0,0}, {8,7,1}, {13,9,8}, {147,0,0}, {19,18,10}, {127,0,0},
     650{183,0,0}, {12,4,1}, {31,0,0}, {11,8,6}, {173,0,0}, {12,0,0},
     651{7,5,3}, {113,0,0}, {207,0,0}, {18,15,5}, {1,0,0}, {13,7,6},
     652{21,0,0}, {35,0,0}, {12,7,2}, {117,0,0}, {123,0,0}, {12,10,2},
     653{143,0,0}, {14,4,1}, {15,9,7}, {204,0,0}, {7,5,1}, {91,0,0},
     654{4,2,1}, {8,6,3}, {183,0,0}, {12,10,7}, {77,0,0}, {36,0,0},
     655{14,9,6}, {221,0,0}, {7,6,5}, {16,14,13}, {31,0,0}, {16,15,7},
     656{365,0,0}, {403,0,0}, {10,3,2}, {11,4,3}, {31,0,0}, {10,9,4},
     657{177,0,0}, {16,6,1}, {22,6,5}, {417,0,0}, {15,13,12}, {217,0,0},
     658{207,0,0}, {7,5,4}, {10,7,1}, {11,6,1}, {45,0,0}, {24,0,0},
     659{12,11,9}, {77,0,0}, {21,20,13}, {9,6,5}, {189,0,0}, {8,3,2},
     660{13,12,10}, {260,0,0}, {16,9,7}, {168,0,0}, {131,0,0}, {7,6,3},
     661{305,0,0}, {10,9,6}, {13,9,4}, {143,0,0}, {12,9,3}, {18,0,0},
     662{15,8,5}, {20,9,6}, {103,0,0}, {15,4,2}, {201,0,0}, {36,0,0},
     663{9,5,2}, {31,0,0}, {11,7,2}, {6,2,1}, {7,0,0}, {13,6,4},
     664{9,8,7}, {19,0,0}, {17,10,6}, {15,0,0}, {9,3,1}, {178,0,0},
     665{8,7,6}, {12,6,5}, {177,0,0}, {230,0,0}, {24,9,3}, {222,0,0},
     666{3,0,0}, {16,13,12}, {121,0,0}, {10,4,2}, {161,0,0}, {39,0,0},
     667{17,15,13}, {62,0,0}, {223,0,0}, {15,12,2}, {65,0,0}, {12,6,3},
     668{101,0,0}, {59,0,0}, {5,4,3}, {17,0,0}, {5,3,2}, {13,8,3},
     669{10,9,7}, {12,8,2}, {5,4,3}, {75,0,0}, {19,17,8}, {55,0,0},
     670{99,0,0}, {10,7,4}, {115,0,0}, {9,8,6}, {385,0,0}, {186,0,0},
     671{15,6,3}, {9,4,1}, {12,10,5}, {10,8,1}, {135,0,0}, {5,2,1},
     672{317,0,0}, {7,0,0}, {19,6,1}, {294,0,0}, {35,0,0}, {13,12,6},
     673{119,0,0}, {98,0,0}, {93,0,0}, {68,0,0}, {21,15,3}, {108,0,0},
     674{75,0,0}, {12,6,5}, {411,0,0}, {12,7,2}, {13,7,2}, {21,0,0},
     675{15,10,8}, {412,0,0}, {439,0,0}, {10,7,6}, {41,0,0}, {13,9,6},
     676{8,5,2}, {10,0,0}, {15,7,2}, {141,0,0}, {159,0,0}, {13,12,10},
     677{291,0,0}, {10,9,1}, {105,0,0}, {24,0,0}, {11,2,1}, {198,0,0},
     678{27,0,0}, {6,3,1}, {439,0,0}, {10,3,1}, {49,0,0}, {168,0,0},
     679{13,11,9}, {463,0,0}, {10,9,3}, {13,9,8}, {15,8,3}, {18,16,8},
     680{15,14,11}, {7,0,0}, {19,9,8}, {12,6,3}, {7,4,3}, {15,14,5},
     681{8,6,3}, {10,9,7}, {361,0,0}, {230,0,0}, {15,9,6}, {24,0,0},
     682{407,0,0}, {16,7,2}, {189,0,0}, {62,0,0}, {189,0,0}, {112,0,0},
     683{22,21,10}, {91,0,0}, {79,0,0}, {12,10,5}, {23,0,0}, {7,6,1},
     684{57,0,0}, {139,0,0}, {24,15,6}, {14,0,0}, {83,0,0}, {16,9,1},
     685{35,0,0}, {9,7,4}, {117,0,0}, {65,0,0}, {21,9,6}, {21,0,0},
     686{195,0,0}, {23,11,10}, {327,0,0}, {17,14,3}, {417,0,0}, {13,0,0},
     687{15,8,6}, {107,0,0}, {19,10,6}, {18,15,3}, {59,0,0}, {12,10,4},
     688{9,7,5}, {283,0,0}, {13,9,6}, {62,0,0}, {427,0,0}, {14,7,3},
     689{8,7,4}, {15,8,3}, {105,0,0}, {27,0,0}, {7,3,1}, {103,0,0},
     690{551,0,0}, {10,6,1}, {6,4,1}, {11,6,4}, {129,0,0}, {9,0,0},
     691{9,4,2}, {277,0,0}, {31,0,0}, {13,12,5}, {141,0,0}, {12,7,3},
     692{357,0,0}, {7,2,1}, {11,9,7}, {227,0,0}, {131,0,0}, {7,6,3},
     693{23,0,0}, {20,17,3}, {13,4,1}, {90,0,0}, {15,3,2}, {241,0,0},
     694{75,0,0}, {13,6,1}, {307,0,0}, {8,7,3}, {245,0,0}, {66,0,0},
     695{15,11,2}, {365,0,0}, {18,16,11}, {11,10,1}, {19,0,0}, {8,6,1},
     696{189,0,0}, {133,0,0}, {12,7,2}, {114,0,0}, {27,0,0}, {6,5,1},
     697{15,5,2}, {17,14,5}, {133,0,0}, {476,0,0}, {11,9,3}, {16,0,0},
     698{375,0,0}, {15,8,6}, {25,0,0}, {17,11,6}, {77,0,0}, {87,0,0},
     699{5,3,2}, {134,0,0}, {171,0,0}, {13,8,4}, {75,0,0}, {8,3,1},
     700{233,0,0}, {196,0,0}, {9,8,7}, {173,0,0}, {15,14,12}, {13,6,5},
     701{281,0,0}, {9,8,2}, {405,0,0}, {114,0,0}, {15,9,6}, {171,0,0},
     702{287,0,0}, {8,4,2}, {43,0,0}, {4,2,1}, {513,0,0}, {273,0,0},
     703{11,10,6}, {118,0,0}, {243,0,0}, {14,7,1}, {203,0,0}, {9,5,2},
     704{257,0,0}, {302,0,0}, {27,25,9}, {393,0,0}, {91,0,0}, {12,10,6},
     705{413,0,0}, {15,14,9}, {18,16,1}, {255,0,0}, {12,9,7}, {234,0,0},
     706{167,0,0}, {16,13,10}, {27,0,0}, {15,6,2}, {433,0,0}, {105,0,0},
     707{25,10,2}, {151,0,0}, {427,0,0}, {13,9,8}, {49,0,0}, {10,6,4},
     708{153,0,0}, {4,0,0}, {17,7,5}, {54,0,0}, {203,0,0}, {16,15,1},
     709{16,14,7}, {13,6,1}, {25,0,0}, {14,0,0}, {15,5,3}, {187,0,0},
     710{15,13,10}, {13,10,5}, {97,0,0}, {11,10,9}, {19,10,4}, {589,0,0},
     711{31,30,2}, {289,0,0}, {9,6,4}, {11,8,6}, {21,0,0}, {7,4,1},
     712{7,4,2}, {77,0,0}, {5,3,2}, {119,0,0}, {7,0,0}, {9,5,2},
     713{345,0,0}, {17,10,8}, {333,0,0}, {17,0,0}, {16,9,7}, {168,0,0},
     714{15,13,4}, {11,10,1}, {217,0,0}, {18,11,10}, {189,0,0}, {216,0,0},
     715{12,7,5}, {229,0,0}, {231,0,0}, {12,9,3}, {223,0,0}, {10,9,1},
     716{153,0,0}, {470,0,0}, {23,16,6}, {99,0,0}, {10,4,3}, {9,8,4},
     717{12,10,1}, {14,9,6}, {201,0,0}, {38,0,0}, {15,14,2}, {198,0,0},
     718{399,0,0}, {14,11,5}, {75,0,0}, {11,10,1}, {77,0,0}, {16,12,8},
     719{20,17,15}, {326,0,0}, {39,0,0}, {14,12,9}, {495,0,0}, {8,3,2},
     720{333,0,0}, {476,0,0}, {15,14,2}, {164,0,0}, {19,0,0}, {12,4,2},
     721{8,6,3}, {13,12,3}, {12,11,5}, {129,0,0}, {12,9,3}, {52,0,0},
     722{10,8,3}, {17,16,2}, {337,0,0}, {12,9,3}, {397,0,0}, {277,0,0},
     723{21,11,3}, {73,0,0}, {11,6,1}, {7,5,4}, {95,0,0}, {11,3,2},
     724{617,0,0}, {392,0,0}, {8,3,2}, {75,0,0}, {315,0,0}, {15,6,4},
     725{125,0,0}, {6,5,2}, {15,9,7}, {348,0,0}, {15,6,1}, {553,0,0},
     726{6,3,2}, {10,9,7}, {553,0,0}, {14,10,4}, {237,0,0}, {39,0,0},
     727{17,14,6}, {371,0,0}, {255,0,0}, {8,4,1}, {131,0,0}, {14,6,1},
     728{117,0,0}, {98,0,0}, {5,3,2}, {56,0,0}, {655,0,0}, {9,5,2},
     729{239,0,0}, {11,8,4}, {1,0,0}, {134,0,0}, {15,9,5}, {88,0,0},
     730{10,5,3}, {10,9,4}, {181,0,0}, {15,11,2}, {609,0,0}, {52,0,0},
     731{19,18,10}, {100,0,0}, {7,6,3}, {15,8,2}, {183,0,0}, {18,7,6},
     732{10,9,2}, {130,0,0}, {11,5,1}, {12,0,0}, {219,0,0}, {13,10,7},
     733{11,0,0}, {19,9,4}, {129,0,0}, {3,0,0}, {17,15,5}, {300,0,0},
     734{17,13,9}, {14,6,5}, {97,0,0}, {13,8,3}, {601,0,0}, {55,0,0},
     735{8,3,1}, {92,0,0}, {127,0,0}, {12,11,2}, {81,0,0}, {15,10,8},
     736{13,2,1}, {47,0,0}, {14,13,6}, {194,0,0}, {383,0,0}, {25,14,11},
     737{125,0,0}, {20,19,16}, {429,0,0}, {282,0,0}, {10,9,6}, {342,0,0},
     738{5,3,2}, {15,9,4}, {33,0,0}, {9,4,2}, {49,0,0}, {15,0,0},
     739{11,6,2}, {28,0,0}, {103,0,0}, {18,17,8}, {27,0,0}, {11,6,5},
     740{33,0,0}, {17,0,0}, {11,10,6}, {387,0,0}, {363,0,0}, {15,10,9},
     741{83,0,0}, {7,6,4}, {357,0,0}, {13,12,4}, {14,13,7}, {322,0,0},
     742{395,0,0}, {16,5,1}, {595,0,0}, {13,10,3}, {421,0,0}, {195,0,0},
     743{11,3,2}, {13,0,0}, {16,12,3}, {14,3,1}, {315,0,0}, {26,10,5},
     744{297,0,0}, {52,0,0}, {9,4,2}, {314,0,0}, {243,0,0}, {16,14,9},
     745{185,0,0}, {12,5,3}, {13,5,2}, {575,0,0}, {12,9,3}, {39,0,0},
     746{311,0,0}, {13,5,2}, {181,0,0}, {20,18,14}, {49,0,0}, {25,0,0},
     747{11,4,1}, {77,0,0}, {17,11,10}, {15,14,8}, {21,0,0}, {17,10,5},
     748{69,0,0}, {49,0,0}, {11,10,2}, {32,0,0}, {411,0,0}, {21,16,3},
     749{11,7,4}, {22,10,3}, {85,0,0}, {140,0,0}, {9,8,6}, {252,0,0},
     750{279,0,0}, {9,5,2}, {307,0,0}, {17,10,4}, {13,12,9}, {94,0,0},
     751{13,11,4}, {49,0,0}, {17,11,10}, {16,12,5}, {25,0,0}, {6,5,2},
     752{12,5,1}, {80,0,0}, {8,3,2}, {246,0,0}, {11,5,2}, {11,10,2},
     753{599,0,0}, {18,12,10}, {189,0,0}, {278,0,0}, {10,9,3}, {399,0,0},
     754{299,0,0}, {13,10,6}, {277,0,0}, {13,10,6}, {69,0,0}, {220,0,0},
     755{13,10,3}, {229,0,0}, {18,11,10}, {16,15,1}, {27,0,0}, {18,9,3},
     756{473,0,0}, {373,0,0}, {18,17,7}, {60,0,0}, {207,0,0}, {13,9,8},
     757{22,20,13}, {25,18,7}, {225,0,0}, {404,0,0}, {21,6,2}, {46,0,0},
     758{6,2,1}, {17,12,6}, {75,0,0}, {4,2,1}, {365,0,0}, {445,0,0},
     759{11,7,1}, {44,0,0}, {10,8,5}, {12,5,2}, {63,0,0}, {17,4,2},
     760{189,0,0}, {557,0,0}, {19,12,2}, {252,0,0}, {99,0,0}, {10,8,5},
     761{65,0,0}, {14,9,3}, {9,0,0}, {119,0,0}, {8,5,2}, {339,0,0},
     762{95,0,0}, {12,9,7}, {7,0,0}, {13,10,2}, {77,0,0}, {127,0,0},
     763{21,10,7}, {319,0,0}, {667,0,0}, {17,10,3}, {501,0,0}, {18,12,9},
     764{9,8,5}, {17,0,0}, {20,9,2}, {341,0,0}, {731,0,0}, {7,6,5},
     765{647,0,0}, {10,4,2}, {121,0,0}, {20,0,0}, {21,19,13}, {574,0,0},
     766{399,0,0}, {15,10,7}, {85,0,0}, {16,8,3}, {169,0,0}, {15,0,0},
     767{12,7,5}, {568,0,0}, {10,7,1}, {18,2,1}, {3,0,0}, {14,3,2},
     768{13,7,3}, {643,0,0}, {14,11,1}, {548,0,0}, {783,0,0}, {14,11,1},
     769{317,0,0}, {7,6,4}, {153,0,0}, {87,0,0}, {15,13,1}, {231,0,0},
     770{11,5,3}, {18,13,7}, {771,0,0}, {30,20,11}, {15,6,3}, {103,0,0},
     771{13,4,3}, {182,0,0}, {211,0,0}, {17,6,1}, {27,0,0}, {13,12,10},
     772{15,14,10}, {17,0,0}, {13,11,5}, {69,0,0}, {11,5,1}, {18,6,1},
     773{603,0,0}, {10,4,2}, {741,0,0}, {668,0,0}, {17,15,3}, {147,0,0},
     774{227,0,0}, {15,10,9}, {37,0,0}, {16,6,1}, {173,0,0}, {427,0,0},
     775{7,5,1}, {287,0,0}, {231,0,0}, {20,15,10}, {18,9,1}, {14,12,5},
     776{16,5,1}, {310,0,0}, {18,13,1}, {434,0,0}, {579,0,0}, {18,13,8},
     777{45,0,0}, {12,8,3}, {16,9,5}, {53,0,0}, {19,15,10}, {16,0,0},
     778{17,6,5}, {17,10,1}, {37,0,0}, {17,10,9}, {21,13,7}, {99,0,0},
     779{17,9,6}, {176,0,0}, {271,0,0}, {18,17,13}, {459,0,0}, {21,17,10},
     780{6,5,2}, {202,0,0}, {5,4,3}, {90,0,0}, {755,0,0}, {15,7,2},
     781{363,0,0}, {8,4,2}, {129,0,0}, {20,0,0}, {11,6,2}, {135,0,0},
     782{15,8,7}, {14,13,2}, {10,4,3}, {24,13,10}, {19,14,11}, {31,0,0},
     783{15,8,6}, {758,0,0}, {16,11,5}, {16,5,1}, {359,0,0}, {23,18,17},
     784{501,0,0}, {29,0,0}, {15,6,3}, {201,0,0}, {459,0,0}, {12,10,7},
     785{225,0,0}, {22,17,13}, {24,22,5}, {161,0,0}, {14,11,3}, {52,0,0},
     786{19,17,6}, {21,14,12}, {93,0,0}, {13,10,3}, {201,0,0}, {178,0,0},
     787{15,12,5}, {250,0,0}, {7,6,4}, {17,13,6}, {221,0,0}, {13,11,8},
     788{17,14,9}, {113,0,0}, {17,14,10}, {300,0,0}, {39,0,0}, {18,13,3},
     789{261,0,0}, {15,14,8}, {753,0,0}, {8,4,3}, {11,10,5}, {94,0,0},
     790{15,13,1}, {10,4,2}, {14,11,10}, {8,6,2}, {461,0,0}, {418,0,0},
     791{19,14,6}, {403,0,0}, {267,0,0}, {10,9,2}, {259,0,0}, {20,4,3},
     792{869,0,0}, {173,0,0}, {19,18,2}, {369,0,0}, {255,0,0}, {22,12,9},
     793{567,0,0}, {20,11,7}, {457,0,0}, {482,0,0}, {6,3,2}, {775,0,0},
     794{19,17,6}, {6,4,3}, {99,0,0}, {15,14,8}, {6,5,2}, {165,0,0},
     795{8,3,2}, {13,12,10}, {25,21,17}, {17,14,9}, {105,0,0}, {17,15,14},
     796{10,3,2}, {250,0,0}, {25,6,5}, {327,0,0}, {279,0,0}, {13,6,5},
     797{371,0,0}, {15,9,4}, {117,0,0}, {486,0,0}, {10,9,3}, {217,0,0},
     798{635,0,0}, {30,27,17}, {457,0,0}, {16,6,2}, {57,0,0}, {439,0,0},
     799{23,21,6}, {214,0,0}, {20,13,6}, {20,16,1}, {819,0,0}, {15,11,8},
     800{593,0,0}, {190,0,0}, {17,14,3}, {114,0,0}, {21,18,3}, {10,5,2},
     801{12,9,5}, {8,6,3}, {69,0,0}, {312,0,0}, {22,5,2}, {502,0,0},
     802{843,0,0}, {15,10,3}, {747,0,0}, {6,5,2}, {101,0,0}, {123,0,0},
     803{19,16,9}, {521,0,0}, {171,0,0}, {16,7,2}, {12,6,5}, {22,21,20},
     804{545,0,0}, {163,0,0}, {23,18,1}, {479,0,0}, {495,0,0}, {13,6,5},
     805{11,0,0}, {17,5,2}, {18,8,1}, {684,0,0}, {7,5,1}, {9,0,0},
     806{18,11,3}, {22,20,13}, {273,0,0}, {4,3,2}, {381,0,0}, {51,0,0},
     807{18,13,7}, {518,0,0}, {9,5,1}, {14,12,3}, {243,0,0}, {21,17,2},
     808{53,0,0}, {836,0,0}, {21,10,2}, {66,0,0}, {12,10,7}, {13,9,8},
     809{339,0,0}, {16,11,5}, {901,0,0}, {180,0,0}, {16,13,3}, {49,0,0},
     810{6,3,2}, {15,4,1}, {16,13,6}, {18,15,12}, {885,0,0}, {39,0,0},
     811{11,9,4}, {688,0,0}, {16,15,7}, {13,10,6}, {13,0,0}, {25,23,12},
     812{149,0,0}, {260,0,0}, {11,9,1}, {53,0,0}, {11,0,0}, {12,4,2},
     813{9,7,5}, {11,8,1}, {121,0,0}, {261,0,0}, {10,5,2}, {199,0,0},
     814{20,4,3}, {17,9,2}, {13,9,4}, {12,8,7}, {253,0,0}, {174,0,0},
     815{15,4,2}, {370,0,0}, {9,6,1}, {16,10,9}, {669,0,0}, {20,10,9},
     816{833,0,0}, {353,0,0}, {17,13,2}, {29,0,0}, {371,0,0}, {9,8,5},
     817{8,7,1}, {19,8,7}, {12,11,10}, {873,0,0}, {26,11,2}, {12,9,1},
     818{10,7,2}, {13,6,1}, {235,0,0}, {26,24,19}, {733,0,0}, {778,0,0},
     819{12,11,1}, {344,0,0}, {931,0,0}, {16,6,4}, {945,0,0}, {21,19,14},
     820{18,13,11}, {67,0,0}, {20,15,10}, {462,0,0}, {14,5,1}, {10,9,6},
     821{18,11,10}, {16,9,7}, {477,0,0}, {105,0,0}, {11,3,2}, {468,0,0},
     822{23,16,15}, {16,15,6}, {327,0,0}, {23,10,4}, {357,0,0}, {25,0,0},
     823{17,16,7}, {31,0,0}, {7,5,2}, {16,7,6}, {277,0,0}, {14,13,6},
     824{413,0,0}, {103,0,0}, {15,10,1}, {231,0,0}, {747,0,0}, {5,2,1},
     825{113,0,0}, {20,10,7}, {15,9,6}, {11,0,0}, {27,22,18}, {91,0,0},
     826{51,0,0}, {18,13,12}, {603,0,0}, {10,7,3}, {9,0,0}, {121,0,0},
     827{15,14,6}, {17,0,0}, {16,11,2}, {23,15,6}, {279,0,0}, {16,12,6},
     828{89,0,0}, {371,0,0}, {17,15,2}, {771,0,0}, {99,0,0}, {7,6,3},
     829{21,0,0}, {10,7,5}, {801,0,0}, {26,0,0}, {25,19,14}, {175,0,0},
     830{10,7,2}, {20,5,4}, {12,11,1}, {22,5,1}, {165,0,0}, {841,0,0},
     831{25,19,17}, {238,0,0}, {11,8,6}, {22,21,4}, {33,0,0}, {8,7,6},
     832{14,9,2}, {113,0,0}, {13,11,5}, {311,0,0}, {891,0,0}, {20,16,14},
     833{555,0,0}, {23,14,8}, {133,0,0}, {546,0,0}, {6,3,2}, {103,0,0},
     834{15,0,0}, {10,7,3}, {307,0,0}, {14,10,1}, {15,12,2}, {367,0,0},
     835{13,10,6}, {169,0,0}, {22,21,11}, {12,10,8}, {441,0,0}, {17,12,7},
     836{917,0,0}, {205,0,0}, {26,23,13}, {54,0,0}, {459,0,0}, {17,15,4},
     837{19,15,4}, {5,4,2}, {9,7,6}, {42,0,0}, {21,15,7}, {330,0,0},
     838{20,7,3}, {20,7,2}, {81,0,0}, {19,14,1}, {349,0,0}, {165,0,0},
     839{40,35,9}, {274,0,0}, {475,0,0}, {11,10,3}, {93,0,0}, {12,7,4},
     840{13,12,2}, {386,0,0}, {7,6,2}, {881,0,0}, {143,0,0}, {9,8,4},
     841{71,0,0}, {19,18,3}, {16,11,6}, {155,0,0}, {7,2,1}, {735,0,0},
     842{16,8,7}, {9,7,4}, {45,0,0}, {7,6,4}, {12,11,3}, {3,0,0},
    843843{19,14,13}
    844844};
     
    870870
    871871   for (k3 = 3; k3 < n; k3++)
    872       for (k2 = 2; k2 < k3; k2++) 
     872      for (k2 = 2; k2 < k3; k2++)
    873873         for (k1 = 1; k1 < k2; k1++)
    874874            if (IterIrredTest(1+GF2X(k1,1)+GF2X(k2,1)+GF2X(k3,1)+GF2X(n,1))) {
     
    885885   if (n <= 0) Error("SparseIrred: n <= 0");
    886886
    887    if (NTL_OVERFLOW(n, 1, 0)) 
     887   if (NTL_OVERFLOW(n, 1, 0))
    888888      Error("overflow in BuildSparseIrred");
    889889
  • ntl/src/GF2XTest.c

    r1d43d18 r287cc8  
    77   int amt;
    88
    9    wd(int x) { amt = x; } 
     9   wd(int x) { amt = x; }
    1010};
    1111
     
    4444      }
    4545
    46       cout << WD(12,n); 
     46      cout << WD(12,n);
    4747
    4848      iter = 0;
  • ntl/src/GF2XTimeTest.c

    r1d43d18 r287cc8  
    3131   }
    3232
    33    z = z/n; 
     33   z = z/n;
    3434
    3535   return z;
     
    7979      }
    8080   }
    81    
     81
    8282
    8383   n = 16;
     
    140140   return 0;
    141141}
    142    
    143142
     143
  • ntl/src/GF2XVec.c

    r1d43d18 r287cc8  
    5252
    5353   free(v);
    54    v = 0; 
     54   v = 0;
    5555}
    5656
    5757
    58 GF2XVec& GF2XVec::operator=(const GF2XVec& a) 
     58GF2XVec& GF2XVec::operator=(const GF2XVec& a)
    5959{
    6060   if (this == &a)
     
    7070   return *this;
    7171}
    72    
     72
    7373GF2XVec::GF2XVec(const GF2XVec& a)
    7474{
  • ntl/src/G_LLL_FP.c

    r1d43d18 r287cc8  
    1717
    1818
     19
    1920static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1)
    2021// x = x - y*MU
     
    4445   if (MU == 0) return;
    4546
    46    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     47   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    4748      k = MakeOdd(MU);
    4849   else
     
    5455      conv(mu1, MU);
    5556
    56       for (i = 1; i <= n; i++) {
    57          mul(T, B(i), mu1);
    58          if (k > 0) LeftShift(T, T, k);
    59          sub(A(i), A(i), T);
     57      if (k > 0) {
     58
     59         for (i = 1; i <= n; i++) {
     60            mul(T, B(i), mu1);
     61            LeftShift(T, T, k);
     62            sub(A(i), A(i), T);
     63         }
     64
     65      }
     66      else {
     67
     68         for (i = 1; i <= n; i++) {
     69            MulSubFrom(A(i), B(i), mu1);
     70         }
     71
    6072      }
    6173   }
     
    7082
    7183
     84
    7285#define TR_BND (NTL_FDOUBLE_PRECISION/2.0)
    7386// Just to be safe!!
     
    120133
    121134
    122 static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1, 
     135static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1,
    123136                         double *a, double *b, long *in_a,
    124137                         double& max_a, double max_b, long& in_float)
     
    186199               in_a[i] = 0;
    187200            }
    188          
     201
    189202            sub(A(i), A(i), B(i));
    190203         }
     
    205218               in_a[i] = 0;
    206219            }
    207          
     220
    208221            add(A(i), A(i), B(i));
    209222         }
     
    215228
    216229   double b_bnd = fabs(TR_BND/mu) - 1;
    217    if (b_bnd < 0) b_bnd = 0; 
    218 
    219    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     230   if (b_bnd < 0) b_bnd = 0;
     231
     232   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    220233      k = MakeOdd(MU);
    221234   else
     
    243256            if (in_a[i] && a[i] < TR_BND && a[i] > -TR_BND &&
    244257                b[i] < b_bnd && b[i] > -b_bnd) {
    245    
     258
    246259               a[i] -= b[i]*mu;
    247260            }
     
    251264                  in_a[i] = 0;
    252265               }
    253                mul(T, B(i), mu1);
    254                sub(A(i), A(i), T);
     266               MulSubFrom(A(i), B(i), mu1);
    255267            }
    256268         }
     
    298310   if (MU == 0) return;
    299311
    300    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     312   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    301313      k = MakeOdd(MU);
    302314   else
     
    348360{
    349361   sz = min(m, n)/10;
    350    if (sz < 2) 
     362   if (sz < 2)
    351363      sz = 2;
    352364   else if (sz > 20)
     
    356368
    357369   long i;
    358    buf = NTL_NEW_OP doubleptr[sz]; 
     370   buf = NTL_NEW_OP doubleptr[sz];
    359371   if (!buf) Error("out of memory");
    360372   for (i = 0; i < sz; i++)
     
    443455   }
    444456
    445    i = 0; 
     457   i = 0;
    446458   while (i < sz && bl[i] != 0)
    447459      i++;
     
    488500         backoff = 2;
    489501      else if (backoff > cache.sz + 2)
    490          backoff = cache.sz + 2; 
     502         backoff = cache.sz + 2;
    491503
    492504      long ub = k-(backoff-1);
     
    495507         double *cptr = mu[i];
    496508         double *sptr = aux[i];
    497    
     509
    498510         for (j = n; j > i; j--) {
    499511            c = cptr[j];
    500512            s = sptr[j];
    501    
     513
    502514            a = c*pp[j-1] - s*pp[j];
    503515            b = s*pp[j-1] + c*pp[j];
    504    
     516
    505517            pp[j-1] = a;
    506518            pp[j] = b;
    507519         }
    508    
    509          pp[i] = pp[i]/mu[i][i]; 
     520
     521         pp[i] = pp[i]/mu[i][i];
    510522      }
    511523
     
    520532      double *cptr = mu[i];
    521533      double *sptr = aux[i];
    522  
     534
    523535      for (j = n; j > i; j--) {
    524536         c = cptr[j];
    525537         s = sptr[j];
    526  
     538
    527539         a = c*p[j-1] - s*p[j];
    528540         b = s*p[j-1] + c*p[j];
    529  
     541
    530542         p[j-1] = a;
    531543         p[j] = b;
    532544      }
    533  
     545
    534546      p[i] = p[i]/mu[i][i];
    535547   }
     
    553565         s = c*t;
    554566      }
    555    
     567
    556568      p[j-1] = c*a - s*b;
    557569      p[j] = c;
     
    594606   log_red--;
    595607
    596    
     608
    597609   //cerr << "G_LLL_FP: warning--relaxing reduction (" << log_red << ")\n";
    598610
     
    618630
    619631static
    620 long ll_G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep, 
    621            LLLCheckFct check, double **B1, double **mu, 
     632long ll_G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep,
     633           LLLCheckFct check, double **B1, double **mu,
    622634           double **aux,
    623635           long m, long init_k, long &quit, GivensCache_FP& cache)
     
    701713            }
    702714            else {
    703                Error( "G_LLL_FP: warning--infinite loop?\n");
     715               Error("G_LLL_FP: warning--infinite loop?\n");
    704716            }
    705717         }
    706718
    707719         Fc1 = 0;
    708    
     720
    709721         for (j = k-1; j >= 1; j--) {
    710722            t1 = fabs(mu[k][j]);
    711             if (t1 > half_plus_fudge) { 
     723            if (t1 > half_plus_fudge) {
    712724
    713725
    714726               if (!Fc1) {
    715                   if (j > trigger_index || 
     727                  if (j > trigger_index ||
    716728                      (j == trigger_index && small_trigger)) {
    717729
     
    731743                  RowTransformStart(B1[k], in_vec, in_float, n);
    732744               }
    733                  
     745
    734746
    735747               mu1 = mu[k][j];
     
    738750               else
    739751                  mu1 = floor(mu1+0.5);
    740    
     752
    741753               double *mu_k = mu[k];
    742754               double *mu_j = mu[j];
    743    
     755
    744756               if (mu1 == 1) {
    745757                  for (i = 1; i <= j-1; i++)
     
    754766                     mu_k[i] -= mu1*mu_j[i];
    755767               }
    756    
     768
    757769               mu_k[j] -= mu1;
    758    
     770
    759771               conv(MU, mu1);
    760772
     
    774786      } while (Fc1);
    775787
    776       if (check && (*check)(B(k))) 
     788      if (check && (*check)(B(k)))
    777789         quit = 1;
    778790
     
    803815      // test G_LLL reduction condition
    804816
    805       if (k > 1 && 
    806          sqrt(delta - mu[k][k-1]*mu[k][k-1])*fabs(mu[k-1][k-1]) > 
     817      if (k > 1 &&
     818         sqrt(delta - mu[k][k-1]*mu[k][k-1])*fabs(mu[k-1][k-1]) >
    807819         fabs(mu[k][k])) {
    808820         // swap rows k, k-1
     
    840852
    841853static
    842 long G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep, 
     854long G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep,
    843855           LLLCheckFct check)
    844856{
     
    892904      }
    893905
    894          
     906
    895907   GivensCache_FP cache(m, n);
    896908
     
    932944}
    933945
    934          
    935 
    936 long G_LLL_FP(mat_ZZ& B, double delta, long deep, LLLCheckFct check, 
     946
     947
     948long G_LLL_FP(mat_ZZ& B, double delta, long deep, LLLCheckFct check,
    937949           long verb)
    938950{
     
    945957}
    946958
    947 long G_LLL_FP(mat_ZZ& B, mat_ZZ& U, double delta, long deep, 
     959long G_LLL_FP(mat_ZZ& B, mat_ZZ& U, double delta, long deep,
    948960           LLLCheckFct check, long verb)
    949961{
     
    987999         for (j = 1; j <= k; j++)
    9881000            x = x + Log(j);
    989          
     1001
    9901002         x = x * (1/double(k));
    9911003
     
    10151027static vec_double G_BKZThresh;
    10161028
    1017 static 
     1029static
    10181030void ComputeG_BKZThresh(double *c, long beta)
    10191031{
     
    10331045
    10341046static
    1035 long G_BKZ_FP(mat_ZZ& BB, mat_ZZ* UU, double delta, 
     1047long G_BKZ_FP(mat_ZZ& BB, mat_ZZ* UU, double delta,
    10361048         long beta, long prune, LLLCheckFct check)
    10371049{
    10381050
    1039    
     1051
    10401052
    10411053   long m = BB.NumRows();
    10421054   long n = BB.NumCols();
    10431055   long m_orig = m;
    1044    
     1056
    10451057   long i, j;
    10461058   ZZ MU;
     
    11511163      }
    11521164
    1153          
     1165
    11541166   GivensCache_FP cache(m, n);
    11551167
     
    11821194      if (beta > m) beta = m;
    11831195
    1184       if (prune > 0) 
     1196      if (prune > 0)
    11851197         ComputeG_BKZConstant(beta, prune);
    11861198
    11871199      z = 0;
    11881200      jj = 0;
    1189    
     1201
    11901202      while (z < m-1) {
    11911203         jj++;
    11921204         kk = min(jj+beta-1, m);
    1193    
     1205
    11941206         if (jj == m) {
    11951207            jj = 1;
     
    12091221         if (prune > 0)
    12101222            ComputeG_BKZThresh(&c[jj], kk-jj+1);
    1211    
     1223
    12121224         cbar = c[jj];
    12131225         utildavec[jj] = uvec[jj] = 1;
    1214    
     1226
    12151227         yvec[jj] = vvec[jj] = 0;
    12161228         Deltavec[jj] = 0;
    1217    
    1218    
     1229
     1230
    12191231         s = t = jj;
    12201232         deltavec[jj] = 1;
    1221    
     1233
    12221234         for (i = jj+1; i <= kk+1; i++) {
    12231235            ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
     
    12281240
    12291241         long enum_cnt = 0;
    1230    
     1242
    12311243         while (t <= kk) {
    1232 
    1233             ctilda[t] = ctilda[t+1] +
     1244            ctilda[t] = ctilda[t+1] +
    12341245               (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*c[t];
    12351246
    12361247            ForceToMem(&ctilda[t]); // prevents an infinite loop
    1237    
     1248
    12381249            if (prune > 0 && t > jj) {
    12391250               eta = G_BKZThresh(t-jj);
     
    12411252            else
    12421253               eta = 0;
    1243    
     1254
    12441255            if (ctilda[t] < cbar - eta) {
    12451256               if (t > jj) {
     
    12561267                  utildavec[t] = vvec[t] = t1;
    12571268                  Deltavec[t] = 0;
    1258                   if (utildavec[t] > -yvec[t]) 
     1269                  if (utildavec[t] > -yvec[t])
    12591270                     deltavec[t] = -1;
    12601271                  else
     
    12781289
    12791290         NumIterations++;
    1280    
     1291
    12811292         h = min(kk+1, m);
    1282    
     1293
    12831294         if ((delta - 8*red_fudge)*c[jj] > cbar) {
    12841295
     
    12871298            // we treat the case that the new vector is b_s (jj < s <= kk)
    12881299            // as a special case that appears to occur most of the time.
    1289    
     1300
    12901301            s = 0;
    12911302            for (i = jj+1; i <= kk; i++) {
     
    12971308               }
    12981309            }
    1299    
     1310
    13001311            if (s == 0) Error("G_BKZ_FP: internal error");
    1301    
     1312
    13021313            if (s > 0) {
    13031314               // special case
    13041315
    13051316               NumTrivial++;
    1306    
     1317
    13071318               for (i = s; i > jj; i--) {
    13081319                  // swap i, i-1
     
    13111322                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13121323               }
    1313    
     1324
    13141325               // cerr << "special case\n";
    1315                new_m = ll_G_LLL_FP(B, U, delta, 0, check, 
     1326               new_m = ll_G_LLL_FP(B, U, delta, 0, check,
    13161327                                B1, mu, aux, h, jj, quit, cache);
    13171328               if (new_m != h) Error("G_BKZ_FP: internal error");
     
    13221333
    13231334               NumNonTrivial++;
    1324    
     1335
    13251336               for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
    13261337
     
    13361347                  if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
    13371348               }
    1338      
     1349
    13391350               for (i = m+1; i >= jj+1; i--) {
    13401351                  // swap i, i-1
     
    13431354                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13441355               }
    1345      
     1356
    13461357               for (i = 1; i <= n; i++) {
    13471358                  conv(B1[jj][i], B(jj, i));
     
    13501361
    13511362               if (IsZero(B(jj))) Error("G_BKZ_FP: internal error");
    1352      
     1363
    13531364               // remove linear dependencies
    1354    
     1365
    13551366               // cerr << "general case\n";
    1356                new_m = ll_G_LLL_FP(B, U, delta, 0, 0, B1, mu, aux, 
     1367               new_m = ll_G_LLL_FP(B, U, delta, 0, 0, B1, mu, aux,
    13571368                                  kk+1, jj, quit, cache);
    1358              
    1359                if (new_m != kk) Error("G_BKZ_FP: internal error"); 
     1369
     1370               if (new_m != kk) Error("G_BKZ_FP: internal error");
    13601371
    13611372               // remove zero vector
    1362      
     1373
    13631374               for (i = kk+2; i <= m+1; i++) {
    13641375                  // swap i, i-1
     
    13671378                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13681379               }
    1369      
     1380
    13701381               quit = 0;
    13711382               if (check) {
     
    13781389
    13791390               if (quit) break;
    1380    
     1391
    13811392               if (h > kk) {
    13821393                  // extend reduced basis
    1383    
    1384                   new_m = ll_G_LLL_FP(B, U, delta, 0, check, 
     1394
     1395                  new_m = ll_G_LLL_FP(B, U, delta, 0, check,
    13851396                                   B1, mu, aux, h, h, quit, cache);
    1386    
     1397
    13871398                  if (new_m != h) Error("G_BKZ_FP: internal error");
    13881399                  if (quit) break;
    13891400               }
    13901401            }
    1391    
     1402
    13921403            z = 0;
    13931404         }
     
    13991410
    14001411            if (!clean) {
    1401                new_m = ll_G_LLL_FP(B, U, delta, 0, check, B1, mu, aux, 
     1412               new_m = ll_G_LLL_FP(B, U, delta, 0, check, B1, mu, aux,
    14021413                                   h, h, quit, cache);
    14031414               if (new_m != h) Error("G_BKZ_FP: internal error");
    14041415               if (quit) break;
    14051416            }
    1406    
     1417
    14071418            z++;
    14081419         }
     
    14661477}
    14671478
    1468 long G_BKZ_FP(mat_ZZ& BB, mat_ZZ& UU, double delta, 
     1479long G_BKZ_FP(mat_ZZ& BB, mat_ZZ& UU, double delta,
    14691480         long beta, long prune, LLLCheckFct check, long verb)
    14701481{
     
    14781489}
    14791490
    1480 long G_BKZ_FP(mat_ZZ& BB, double delta, 
     1491long G_BKZ_FP(mat_ZZ& BB, double delta,
    14811492         long beta, long prune, LLLCheckFct check, long verb)
    14821493{
  • ntl/src/G_LLL_QP.c

    r1d43d18 r287cc8  
    2424
    2525
    26 
    2726static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1)
    2827// x = x - y*MU
     
    5251   if (MU == 0) return;
    5352
    54    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     53   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    5554      k = MakeOdd(MU);
    5655   else
     
    6261      conv(mu1, MU);
    6362
    64       for (i = 1; i <= n; i++) {
    65          mul(T, B(i), mu1);
    66          if (k > 0) LeftShift(T, T, k);
    67          sub(A(i), A(i), T);
     63      if (k > 0) {
     64
     65         for (i = 1; i <= n; i++) {
     66            mul(T, B(i), mu1);
     67            LeftShift(T, T, k);
     68            sub(A(i), A(i), T);
     69         }
     70
     71      }
     72      else {
     73
     74         for (i = 1; i <= n; i++) {
     75            MulSubFrom(A(i), B(i), mu1);
     76         }
     77
    6878      }
    6979   }
     
    7787}
    7888
     89
     90
     91
    7992#define TR_BND (NTL_FDOUBLE_PRECISION/2.0)
    8093// Just to be safe!!
     
    128141
    129142
    130    
    131 
    132 
    133 
    134 static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1, 
    135                          quad_float *a, quad_float *b, long *in_a, 
     143
     144
     145
     146
     147static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1,
     148                         quad_float *a, quad_float *b, long *in_a,
    136149                         double& max_a, double max_b, long& in_float)
    137150// x = x - y*MU
     
    232245
    233246
    234    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     247   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    235248      k = MakeOdd(MU);
    236249   else
     
    258271            if (in_a[i] && a[i].hi < TR_BND && a[i].hi > -TR_BND &&
    259272                b[i].hi < b_bnd && b[i].hi > -b_bnd) {
    260  
     273
    261274               a[i].hi -= b[i].hi*mu;
    262275            }
     
    266279                  in_a[i] = 0;
    267280               }
    268                mul(T, B(i), mu1);
    269                sub(A(i), A(i), T);
     281               MulSubFrom(A(i), B(i), mu1);
    270282           }
    271283         }
     
    312324   if (MU == 0) return;
    313325
    314    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     326   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    315327      k = MakeOdd(MU);
    316328   else
     
    359371{
    360372   sz = min(m, n)/10;
    361    if (sz < 2) 
     373   if (sz < 2)
    362374      sz = 2;
    363375   else if (sz > 20)
     
    367379
    368380   long i;
    369    buf = NTL_NEW_OP quad_floatptr[sz]; 
     381   buf = NTL_NEW_OP quad_floatptr[sz];
    370382   if (!buf) Error("out of memory");
    371383   for (i = 0; i < sz; i++)
     
    454466   }
    455467
    456    i = 0; 
     468   i = 0;
    457469   while (i < sz && bl[i] != 0)
    458470      i++;
     
    499511         backoff = 2;
    500512      else if (backoff > cache.sz + 2)
    501          backoff = cache.sz + 2; 
     513         backoff = cache.sz + 2;
    502514
    503515      long ub = k-(backoff-1);
     
    506518         quad_float *cptr = mu[i];
    507519         quad_float *sptr = aux[i];
    508    
     520
    509521         for (j = n; j > i; j--) {
    510522            c = cptr[j];
    511523            s = sptr[j];
    512    
     524
    513525            a = c*pp[j-1] - s*pp[j];
    514526            b = s*pp[j-1] + c*pp[j];
    515    
     527
    516528            pp[j-1] = a;
    517529            pp[j] = b;
    518530         }
    519    
    520          pp[i] = pp[i]/mu[i][i]; 
     531
     532         pp[i] = pp[i]/mu[i][i];
    521533      }
    522534
     
    531543      quad_float *cptr = mu[i];
    532544      quad_float *sptr = aux[i];
    533  
     545
    534546      for (j = n; j > i; j--) {
    535547         c = cptr[j];
    536548         s = sptr[j];
    537  
     549
    538550         a = c*p[j-1] - s*p[j];
    539551         b = s*p[j-1] + c*p[j];
    540  
     552
    541553         p[j-1] = a;
    542554         p[j] = b;
    543555      }
    544  
     556
    545557      p[i] = p[i]/mu[i][i];
    546558   }
     
    564576         s = c*t;
    565577      }
    566    
     578
    567579      p[j-1] = c*a - s*b;
    568580      p[j] = c;
     
    595607   // to help ensure stability in G_BKZ_QP1
    596608
    597    log_red = NTL_DOUBLE_PRECISION-2; 
     609   log_red = NTL_DOUBLE_PRECISION-2;
    598610
    599611   red_fudge = 1;
     
    617629
    618630static
    619 long ll_G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep, 
    620            LLLCheckFct check, quad_float **B1, quad_float **mu, 
     631long ll_G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep,
     632           LLLCheckFct check, quad_float **B1, quad_float **mu,
    621633           quad_float **aux,
    622634           long m, long init_k, long &quit, GivensCache_QP& cache)
     
    689701
    690702         Fc1 = 0;
    691    
     703
    692704         for (j = k-1; j >= 1; j--) {
    693705            t1 = fabs(mu[k][j]);
     
    715727
    716728
    717    
     729
    718730               mu1 = mu[k][j];
    719731               if (mu1 >= 0)
     
    721733               else
    722734                  mu1 = floor(mu1+half);
    723    
    724    
     735
     736
    725737               quad_float *mu_k = mu[k];
    726738               quad_float *mu_j = mu[j];
    727  
     739
    728740               if (mu1 == 1) {
    729741                  for (i = 1; i <= j-1; i++)
     
    740752
    741753               // cout << j << " " << mu[k][j] << " " << mu1 << "\n";
    742  
     754
    743755               mu_k[j] -= mu1;
    744756
    745757               conv(MU, mu1);
    746758
    747    
     759
    748760               RowTransform(B(k), B(j), MU, B1[k], B1[j], in_vec,
    749761                            max_b[k], max_b[j], in_float);
     
    761773      } while (Fc1);
    762774
    763       if (check && (*check)(B(k))) 
     775      if (check && (*check)(B(k)))
    764776         quit = 1;
    765777
     
    784796      if (deep > 0) {
    785797         // deep insertions
    786    
     798
    787799         Error("sorry...deep insertions not implemented");
    788800      } // end deep insertions
     
    819831
    820832static
    821 long G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep, 
     833long G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep,
    822834           LLLCheckFct check)
    823835{
     
    877889   GivensCache_QP cache(m, n);
    878890
    879    new_m = 
     891   new_m =
    880892      ll_G_LLL_QP(B, U, delta, deep, check, B1, mu, aux, m, 1, quit, cache);
    881893
     
    918930}
    919931
    920          
     932
    921933
    922934long G_LLL_QP(mat_ZZ& B, double delta, long deep, LLLCheckFct check,
     
    931943}
    932944
    933 long G_LLL_QP(mat_ZZ& B, mat_ZZ& U, double delta, long deep, 
     945long G_LLL_QP(mat_ZZ& B, mat_ZZ& U, double delta, long deep,
    934946           LLLCheckFct check, long verb)
    935947{
     
    949961void ComputeG_BKZConstant(long beta, long p)
    950962{
    951    const quad_float c_PI = 
     963   const quad_float c_PI =
    952964      to_quad_float("3.141592653589793238462643383279502884197");
    953    const quad_float LogPI = 
     965   const quad_float LogPI =
    954966      to_quad_float("1.144729885849400174143427351353058711647");
    955967
     
    975987         for (j = 1; j <= k; j++)
    976988            x = x + Log(j);
    977          
     989
    978990         x = x * (1/to_quad_float(k));
    979991
     
    10031015static vec_quad_float G_BKZThresh;
    10041016
    1005 static 
     1017static
    10061018void ComputeG_BKZThresh(quad_float *c, long beta)
    10071019{
     
    10221034
    10231035static
    1024 long G_BKZ_QP(mat_ZZ& BB, mat_ZZ* UU, quad_float delta, 
     1036long G_BKZ_QP(mat_ZZ& BB, mat_ZZ* UU, quad_float delta,
    10251037         long beta, long prune, LLLCheckFct check)
    10261038{
     
    10291041   long n = BB.NumCols();
    10301042   long m_orig = m;
    1031    
     1043
    10321044   long i, j;
    10331045   ZZ MU;
     
    11361148         CheckFinite(&B1[i][j]);
    11371149      }
    1138          
     1150
    11391151
    11401152   GivensCache_QP cache(m, n);
     
    11741186      z = 0;
    11751187      jj = 0;
    1176    
     1188
    11771189      while (z < m-1) {
    11781190         jj++;
    11791191         kk = min(jj+beta-1, m);
    1180    
     1192
    11811193         if (jj == m) {
    11821194            jj = 1;
     
    11971209            ComputeG_BKZThresh(&c[jj], kk-jj+1);
    11981210
    1199    
     1211
    12001212         cbar = c[jj];
    12011213         utildavec[jj] = uvec[jj] = 1;
    1202    
     1214
    12031215         yvec[jj] = vvec[jj] = 0;
    12041216         Deltavec[jj] = 0;
    1205    
    1206    
     1217
     1218
    12071219         s = t = jj;
    12081220         deltavec[jj] = 1;
    1209    
     1221
    12101222         for (i = jj+1; i <= kk+1; i++) {
    12111223            ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
     
    12161228
    12171229         long enum_cnt = 0;
    1218    
     1230
    12191231         while (t <= kk) {
    12201232
    1221             ctilda[t] = ctilda[t+1] + 
     1233            ctilda[t] = ctilda[t+1] +
    12221234               (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*c[t];
    1223    
     1235
    12241236            if (prune > 0 && t > jj) {
    12251237               eta = G_BKZThresh(t-jj);
     
    12461258                  utildavec[t] = vvec[t] = t1;
    12471259                  Deltavec[t] = 0;
    1248                   if (utildavec[t] > -yvec[t]) 
     1260                  if (utildavec[t] > -yvec[t])
    12491261                     deltavec[t] = -1;
    12501262                  else
     
    12701282
    12711283         h = min(kk+1, m);
    1272    
     1284
    12731285         if ((delta-8*red_fudge)*c[jj] > cbar) {
    12741286
     
    12771289            // we treat the case that the new vector is b_s (jj < s <= kk)
    12781290            // as a special case that appears to occur most of the time.
    1279    
     1291
    12801292            s = 0;
    12811293            for (i = jj+1; i <= kk; i++) {
     
    12871299               }
    12881300            }
    1289    
     1301
    12901302            if (s == 0) Error("G_BKZ_QP: internal error");
    1291    
     1303
    12921304            if (s > 0) {
    12931305               // special case
    12941306
    12951307               NumTrivial++;
    1296    
     1308
    12971309               for (i = s; i > jj; i--) {
    12981310                  // swap i, i-1
     
    13011313                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13021314               }
    1303    
     1315
    13041316               // cerr << "special case\n";
    13051317               new_m = ll_G_LLL_QP(B, U, delta, 0, check,
     
    13131325               NumNonTrivial++;
    13141326
    1315    
     1327
    13161328               for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
    13171329
     
    13271339                  if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
    13281340               }
    1329      
     1341
    13301342               for (i = m+1; i >= jj+1; i--) {
    13311343                  // swap i, i-1
     
    13341346                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13351347               }
    1336      
     1348
    13371349               for (i = 1; i <= n; i++) {
    13381350                  conv(B1[jj][i], B(jj, i));
    13391351                  CheckFinite(&B1[jj][i]);
    13401352               }
    1341      
    1342                if (IsZero(B(jj))) Error("G_BKZ_QP: internal error"); 
    1343      
     1353
     1354               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error");
     1355
    13441356               // remove linear dependencies
    1345    
     1357
    13461358               // cerr << "general case\n";
    13471359               new_m = ll_G_LLL_QP(B, U, delta, 0, 0, B1, mu, aux,
    13481360                                  kk+1, jj, quit, cache);
    1349              
    1350                if (new_m != kk) Error("G_BKZ_QP: internal error"); 
     1361
     1362               if (new_m != kk) Error("G_BKZ_QP: internal error");
    13511363
    13521364               // remove zero vector
    1353      
     1365
    13541366               for (i = kk+2; i <= m+1; i++) {
    13551367                  // swap i, i-1
     
    13581370                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    13591371               }
    1360      
     1372
    13611373               quit = 0;
    13621374               if (check) {
     
    13691381
    13701382               if (quit) break;
    1371    
     1383
    13721384               if (h > kk) {
    13731385                  // extend reduced basis
    1374    
     1386
    13751387                  new_m = ll_G_LLL_QP(B, U, delta, 0, check,
    13761388                                   B1, mu, aux, h, h, quit, cache);
    1377    
     1389
    13781390                  if (new_m != h) Error("G_BKZ_QP: internal error");
    13791391                  if (quit) break;
    13801392               }
    13811393            }
    1382    
     1394
    13831395            z = 0;
    13841396         }
     
    13921404            if (!clean) {
    13931405               new_m =
    1394                   ll_G_LLL_QP(B, U, delta, 0, check, B1, mu, aux, 
     1406                  ll_G_LLL_QP(B, U, delta, 0, check, B1, mu, aux,
    13951407                              h, h, quit, cache);
    13961408               if (new_m != h) Error("G_BKZ_QP: internal error");
    13971409               if (quit) break;
    13981410            }
    1399    
     1411
    14001412            z++;
    14011413         }
     
    14601472}
    14611473
    1462 long G_BKZ_QP(mat_ZZ& BB, mat_ZZ& UU, double delta, 
     1474long G_BKZ_QP(mat_ZZ& BB, mat_ZZ& UU, double delta,
    14631475         long beta, long prune, LLLCheckFct check, long verb)
    14641476{
     
    14661478   NumSwaps = 0;
    14671479
    1468 
    14691480   if (delta < 0.50 || delta >= 1) Error("G_BKZ_QP: bad delta");
    14701481   if (beta < 2) Error("G_BKZ_QP: bad block size");
     
    14731484}
    14741485
    1475 long G_BKZ_QP(mat_ZZ& BB, double delta, 
     1486long G_BKZ_QP(mat_ZZ& BB, double delta,
    14761487         long beta, long prune, LLLCheckFct check, long verb)
    14771488{
     
    14881499
    14891500static
    1490 long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ* UU, quad_float delta, 
     1501long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ* UU, quad_float delta,
    14911502         long beta, long prune, LLLCheckFct check)
    14921503{
     
    14951506   long n = BB.NumCols();
    14961507   long m_orig = m;
    1497    
     1508
    14981509   long i, j;
    14991510   ZZ MU;
     
    16411652      z = 0;
    16421653      jj = 0;
    1643    
     1654
    16441655      while (z < m-1) {
    16451656         jj++;
    16461657         kk = min(jj+beta-1, m);
    1647    
     1658
    16481659         if (jj == m) {
    16491660            jj = 1;
     
    16641675            ComputeG_BKZThresh(&c[jj], kk-jj+1);
    16651676
    1666    
     1677
    16671678         cbar = to_double(c[jj]);
    16681679         utildavec[jj] = uvec[jj] = 1;
    1669    
     1680
    16701681         yvec[jj] = vvec[jj] = 0;
    16711682         Deltavec[jj] = 0;
    1672    
    1673    
     1683
     1684
    16741685         s = t = jj;
    16751686         deltavec[jj] = 1;
    1676    
     1687
    16771688         for (i = jj+1; i <= kk+1; i++) {
    16781689            ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
     
    16831694
    16841695         long enum_cnt = 0;
    1685    
     1696
    16861697         while (t <= kk) {
    1687 
    1688             ctilda[t] = ctilda[t+1] +
     1698            ctilda[t] = ctilda[t+1] +
    16891699               (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*to_double(c[t]);
    16901700
    16911701            ForceToMem(&ctilda[t]); // prevents an infinite loop
    1692    
     1702
    16931703            if (prune > 0 && t > jj) {
    16941704               eta = to_double(G_BKZThresh(t-jj));
     
    17171727                  utildavec[t] = vvec[t] = t1;
    17181728                  Deltavec[t] = 0;
    1719                   if (utildavec[t] > -yvec[t]) 
     1729                  if (utildavec[t] > -yvec[t])
    17201730                     deltavec[t] = -1;
    17211731                  else
     
    17431753
    17441754         quad_float t1;
    1745    
     1755
    17461756         if ((delta-8*red_fudge)*c[jj] > cbar*(1+64/NTL_FDOUBLE_PRECISION)) {
    17471757
     
    17501760            // we treat the case that the new vector is b_s (jj < s <= kk)
    17511761            // as a special case that appears to occur most of the time.
    1752    
     1762
    17531763            s = 0;
    17541764            for (i = jj+1; i <= kk; i++) {
     
    17601770               }
    17611771            }
    1762    
     1772
    17631773            if (s == 0) Error("G_BKZ_QP: internal error");
    1764    
     1774
    17651775            if (s > 0) {
    17661776               // special case
    17671777
    17681778               NumTrivial++;
    1769    
     1779
    17701780               for (i = s; i > jj; i--) {
    17711781                  // swap i, i-1
     
    17741784                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    17751785               }
    1776    
     1786
    17771787               // cerr << "special case\n";
    17781788               new_m = ll_G_LLL_QP(B, U, delta, 0, check,
     
    17861796               NumNonTrivial++;
    17871797
    1788    
     1798
    17891799               for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
    17901800
     
    18001810                  if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
    18011811               }
    1802      
     1812
    18031813               for (i = m+1; i >= jj+1; i--) {
    18041814                  // swap i, i-1
     
    18071817                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    18081818               }
    1809      
     1819
    18101820               for (i = 1; i <= n; i++) {
    18111821                  conv(B1[jj][i], B(jj, i));
    18121822                  CheckFinite(&B1[jj][i]);
    18131823               }
    1814      
    1815                if (IsZero(B(jj))) Error("G_BKZ_QP: internal error"); 
    1816      
     1824
     1825               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error");
     1826
    18171827               // remove linear dependencies
    1818    
     1828
    18191829               // cerr << "general case\n";
    18201830               new_m = ll_G_LLL_QP(B, U, delta, 0, 0, B1, mu, aux,
    18211831                                  kk+1, jj, quit, cache);
    1822              
    1823                if (new_m != kk) Error("G_BKZ_QP: internal error"); 
     1832
     1833               if (new_m != kk) Error("G_BKZ_QP: internal error");
    18241834
    18251835               // remove zero vector
    1826      
     1836
    18271837               for (i = kk+2; i <= m+1; i++) {
    18281838                  // swap i, i-1
     
    18311841                  tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
    18321842               }
    1833      
     1843
    18341844               quit = 0;
    18351845               if (check) {
     
    18421852
    18431853               if (quit) break;
    1844    
     1854
    18451855               if (h > kk) {
    18461856                  // extend reduced basis
    1847    
     1857
    18481858                  new_m = ll_G_LLL_QP(B, U, delta, 0, check,
    18491859                                   B1, mu, aux, h, h, quit, cache);
    1850    
     1860
    18511861                  if (new_m != h) Error("G_BKZ_QP: internal error");
    18521862                  if (quit) break;
    18531863               }
    18541864            }
    1855    
     1865
    18561866            z = 0;
    18571867         }
     
    18701880               if (quit) break;
    18711881            }
    1872    
     1882
    18731883            z++;
    18741884         }
     
    19331943}
    19341944
    1935 long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ& UU, double delta, 
     1945long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ& UU, double delta,
    19361946         long beta, long prune, LLLCheckFct check, long verb)
    19371947{
     
    19451955}
    19461956
    1947 long G_BKZ_QP1(mat_ZZ& BB, double delta, 
     1957long G_BKZ_QP1(mat_ZZ& BB, double delta,
    19481958         long beta, long prune, LLLCheckFct check, long verb)
    19491959{
  • ntl/src/G_LLL_RR.c

    r1d43d18 r287cc8  
    3737   if (MU == 0) return;
    3838
    39    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     39   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    4040      k = MakeOdd(MU);
    4141   else
     
    8989   if (MU == 0) return;
    9090
    91    if (NumTwos(MU) >= NTL_ZZ_NBITS) 
     91   if (NumTwos(MU) >= NTL_ZZ_NBITS)
    9292      k = MakeOdd(MU);
    9393   else
     
    138138{
    139139   sz = min(m, n)/10;
    140    if (sz < 2) 
     140   if (sz < 2)
    141141      sz = 2;
    142142   else if (sz > 20)
     
    227227   }
    228228
    229    i = 0; 
     229   i = 0;
    230230   while (i < sz && bl[i] != 0)
    231231      i++;
     
    273273         backoff = 2;
    274274      else if (backoff > cache.sz + 2)
    275          backoff = cache.sz + 2; 
     275         backoff = cache.sz + 2;
    276276
    277277      long ub = k-(backoff-1);
     
    280280         vec_RR& cptr = mu(i);
    281281         vec_RR& sptr = aux(i);
    282    
     282
    283283         for (j = n; j > i; j--) {
    284284            c = cptr(j);
    285285            s = sptr(j);
    286    
     286
    287287            // a = c*pp(j-1) - s*pp(j);
    288288            mul(T1, c, pp(j-1));
     
    294294            mul(T2, c, pp(j));
    295295            add(b, T1, T2);
    296    
     296
    297297            pp(j-1) = a;
    298298            pp(j) = b;
    299299         }
    300    
     300
    301301         div(pp(i), pp(i), mu(i,i));
    302302      }
     
    312312      vec_RR& cptr = mu(i);
    313313      vec_RR& sptr = aux(i);
    314  
     314
    315315      for (j = n; j > i; j--) {
    316316         c = cptr(j);
    317317         s = sptr(j);
    318  
     318
    319319         // a = c*p(j-1) - s*p(j);
    320320         mul(T1, c, p(j-1));
     
    326326         mul(T2, c, p(j));
    327327         add(b, T1, T2);
    328  
     328
    329329         p(j-1) = a;
    330330         p(j) = b;
    331331      }
    332  
     332
    333333      div(p(i), p(i), mu(i,i));
    334334   }
     
    350350            div(T1, a, b);
    351351            negate(t, T1);
    352    
     352
    353353            // s = 1/sqrt(1 + t*t);
    354354            sqr(T1, t);
     
    356356            SqrRoot(T1, T1);
    357357            inv(s, T1);
    358            
     358
    359359            // c = s*t;
    360360            mul(c, s, t);
     
    364364            div(T1, b, a);
    365365            negate(t, T1);
    366    
     366
    367367            // c = 1/sqrt(1 + t*t);
    368368            sqr(T1, t);