Re: idealred returns ideal with different norm

[Peter-Lawrence.Montgomery@cwi.nl]

Karim Belabas wrote:

> [Peter-Lawrence Montgomery writes:]
> >        idealred is returning an ideal with different norm than its input.
> >        Is this the way it is supposed to behave?
> 
> I think so. Idealred returns an ideal in the same ideal _class_ as the
> input, which gives a much more efficient reduction (since the norm is
> usually diminished...). This function is really used to find relations in
> the class group, not simply to reduce the size of the ideal components. If
> you want to keep the same ideal and just reduce the corresponding lattice,
> use the standard qflll* functions.
> 
> From the manual (entry for idealred): 
  > "[...] Note  that  this is not the same as the LLL reduction of the
  > lattice x since ideal operations are involved. The result is the Hermite
  > normal form of the LLL-reduced ideal, which is usually, but not always, a
  > reduced ideal. x may also  be  a 2-component vector, the  first  being as
  > above,  and the second containing a matrix of Archimedean information. In
  > that case, this matrix is suitably updated."
> 
> This says (in an admittedly very cryptic style) that by using as input what
> PARI calls (wrongly) an "idele", i.e 2-component vector containing [the
> ideal, a vector with r1+r2 scalar components (embeddings)], the second
> component will keep track of the principal ideals that are lost in the main
> component (see Henri Cohen's book for details).

       I want to do Hermite normal form reduction
(but apparently not LLL reduction) after each step in the exponentiation.
idealpowprime in base4.c seems to call element_pow once,
but the output of element_pow has enormous coefficients in my application.
See example below.


> Side notes:
> > c5 = 200
> > fX = c5*X^5 + 102*X^4 + 315*X^3 - 11*X^2 - 262*X + 5
> > fXM = subst(fX*c5^4, X, XM/c5)     /* fXM is monic in XM */
> 
> fXM = polredabs(fXM) would be a good idea at this point.
> 
          Perhaps.  The rest of my application needs to convert 
linear forms in X to expressions in the new independent variable.
This operation occurs a few million times, partially in
a non-PARI multiple-precision library.


> > [...]
> > ideal2fac = idealfactor(nf, idealprincipal(nf, 2)) /* Factor ideal (2) */
> 
> simpler: ideal2fac = idealprimedec(nf, 2) /* Factor ideal (2) */

       Yes.




/*
         A monic polynomial with (otherwise) big coefficients is passed 
to nfinit.  We raise a prime ideal of norm 2 to a power around 500, 
expecting a matrix with all entries below 2^500.  
Instead the Pari stack overflows if I use idealpow with last
argument 0 (no reduction, default).  
If I pass last argument 1 (reduction), it reduces the ideal in the class group.
How do I tell idealpow to do Hermite reduction after each squaring?

        Peter Montgomery
        pmontgom@cwi.nl
        November 9, 1998
*/

default(echo, 1)
addprimes([114213131, 159042667330786467437827277776717, 1202333827516060678058558372660515622601521935155689851311497005413921721241966950335449737182333223224093240612098941])   /* Last entry is composite. */

c5 = 5748302248738405200
/* fX is the polynomial used to factor RSA130 by NFS in 1996 */
fX = c5*X^5 + 9882261917482286102*X^4 - 13392499389128176685*X^3 + 16875252458877684989*X^2 + 3759900174855208738*X - 46769930553931905995

fXM = subst(fX*c5^4, X, XM/c5)   /* fXM is monic in XM */
nf = nfinit(fXM);

ideal2fac = idealprimedec(nf, 2)   /* Factor (2) ideal */
fac2a = ideal2fac[1]
fac2b = ideal2fac[2]
fac8  = ideal2fac[3]
     /* fac2a and fac2b have norm 2.  fac8 has norm 8.  All have exponent 1 */
idealnorm(nf, fac2a)
idealnorm(nf, fac2b)
idealnorm(nf, fac8)

/*      
      If we successively compute fac2a^8192 using 13 squarings, all is fine.  
      But if we compute fac2a^512 directly, the PARI stack overflows.
      This is with parisize = 10 million (default) in 64-bit mode on MIPS.
      Using 50 million for parisize does not help.

      How do I tell idealpow to do Hermite reduction after each squaring?
      Passing an extra argument (1) to call idealred does reduction
      in the class group, which is not what we want here.
*/
a2 = idealpow(nf, fac2a, 2)
a4 = idealpow(nf, a2, 2)
a8 = idealpow(nf, a4, 2)
a16 = idealpow(nf, a8, 2)
a32 = idealpow(nf, a16, 2)
a64 = idealpow(nf, a32, 2)
a128 = idealpow(nf, a64, 2)
a256 = idealpow(nf, a128, 2)
a512 = idealpow(nf, a256, 2)
a1024 = idealpow(nf, a512, 2)
a2048 = idealpow(nf, a1024, 2)
a4096 = idealpow(nf, a2048, 2)
a8192 = idealpow(nf, a4096, 2)

factor(idealnorm(nf, a8192), 0)    /* 2^8192 */
a8192 = 0; a4096 = 0; a2048 = 0;   /* Release big objects */

idealpow(nf, fac2a, 128)
idealpow(nf, fac2a, 256)
idealpow(nf, fac2a, 512)
quit;