Peter-Lawrence . Montgomery on Tue, 10 Nov 1998 00:58:47 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: idealred returns ideal with different norm |
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;