Hello John, This appears to be a bug in PARI's nffactor(). As you noted, PARI's factor() returns the factorisation instantaneously, and the same is true for factornf(). However, Sage does not call either of these functions, but nffactor(). Normally nffactor(nfinit(g), f) should be practically equivalent to factornf(f, g), but there seems to be a bug in nffactor().
In GP 2.5.5 as distributed with Sage, gp > nffactor(nfinit(y^2 - 22), Mod(1, y^2 - 22)*x^2 + Mod(926246528884912528275985458927067632*y - 4344481316563541186659879867597013188, y^2 - 22)) *** at top-level: nffactor(nfinit(y^2- *** ^-------------------- *** nffactor: the PARI stack overflows ! current stack size: 67108864 (64.000 Mbytes) The same happens with the latest development version. It does not seem to be an actual out-of-memory problem, since (according to GDB or "\g 6" in GP) the error happens at the same point no matter how much stack size you give it. I think it is actually a precision issue, since increasing the working precision solves the problem (in both 2.5.5 and development 2.8.0): gp > \p 100 realprecision = 115 significant digits (100 digits displayed) gp > nffactor(nfinit(y^2 - 22), Mod(1, y^2 - 22)*x^2 + Mod(926246528884912528275985458927067632*y - 4344481316563541186659879867597013188, y^2 - 22)) %1 = [x + Mod(-314226370217524044*y + 1473852319020386314, y^2 - 22) 1] [x + Mod(314226370217524044*y - 1473852319020386314, y^2 - 22) 1] Peter John Cremona wrote: > On 16 June 2014 14:25, John Cremona <john.crem...@gmail.com> wrote: >> sage: K.<a> = QuadraticField(22) >> sage: D = -926246528884912528275985458927067632*a + >> 4344481316563541186659879867597013188 >> sage: D.is_square() >> (boom) >> MemoryError: Unable to allocate 256000000000 bytes for the PARI stack >> (instead, allocated 204800000000 bytes) >> >> Sage Version 6.3.beta3 >> >> Any ideas? Other arithmetic with this works fine, and in fact: >> >> sage: eps = 197-42*a >> sage: rootD = eps^8 * (14+3*a)^2 >> sage: rootD^2 == D >> True >> >> so the problem is in a call to Pari to factor the polynomial x^2-D. >> > > Using the same pari/gp version (2.5.5) I have no problem doing the > same factorization diectly in gp: > > ? nf = bnfinit(t^2-22); > ? a = Mod(t,t^2-22); > ? D = -926246528884912528275985458927067632*a + > 4344481316563541186659879867597013188; > ? factor(x^2-D) > %4 = > [x + Mod(-314226370217524044*t + 1473852319020386314, t^2 - 22) 1] > > [x + Mod(314226370217524044*t - 1473852319020386314, t^2 - 22) 1] > > > >> John -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
