Trac #15446: GP interface confused by stack overflow when enlarging results vector

From Georgi Guninski on sage-support
(https://groups.google.com/forum/#!topic/sage-support/A_GilhiUAwM):
{{{
sage: gp("{T(n)=n+1}")
sage: for n in [ 1 .. 2**20]:
    a=gp.T(n)
    print n

#wait some time..
...
65535
65536
------------------------------------------------------------------------
---
TypeError

TypeError: Error executing code in GP:
CODE:
        sage[131074]=65537;
PARI/GP ERROR:
  ***   at top-level: sage[131074]=65537
  ***                     ^--------------
  ***   array index (131074) out of allowed range [1-131073].
}}}
after this trying:
{{{
sage: gp.T(1)
}}}
again raises exception.

After the above computation, the log file `.sage/gp-expect.log` ends
with
{{{
? sage[131070]=65535;
sage[131070]=65535;
? sage[131071]=T(sage[131070]);
sage[131071]=T(sage[131070]);
? sage=concat(sage, vector(131072,k,0));
sage=concat(sage, vector(131072,k,0));
  ***   at top-level: sage=concat(sage,vec
  ***                 ^--------------------
  ***   the PARI stack overflows !
  current stack size: 10000000 (9.537 Mbytes)
  [hint] you can increase GP stack with allocatemem()

? allocatemem()
allocatemem()
  ***   Warning: new stack size = 20000000 (19.073 Mbytes).
? sage=concat(sage, vector(131072,k,0));
sage=concat(sage, vector(131072,k,0));
? sage[131072]=65536;
sage[131072]=65536;
? sage[131073]=T(sage[131072]);
sage[131073]=T(sage[131072]);
? sage[131074]=65537;
sage[131074]=65537;
  ***   at top-level: sage[131074]=65537
  ***                     ^--------------
  ***   array index (131074) out of allowed range [1-131073].
?
}}}
It appears that the vector `sage` wasn't doubled correctly; probably it
got messed up by the failed `concat()`.

This could be related to #11017/#11018.

URL: http://trac.sagemath.org/15446
Reported by: pbruin
Ticket author(s): Peter Bruin
Reviewer(s): Alejandro Argaez
Trac #15667: Time anomaly in finding orders of points on an elliptic curve over a finite field

See https://groups.google.com/forum/#!searchin/sage-
support/anomaly|sort:relevance|spell:true/sage-support/PzrQ6kUzSJg/m99x
--9TS-oJ

The upshot is that when computing the order of a point on an elliptic
curve whose cardinality has not yet been computed, there are cases where
that cardinality could be computed very quickly first, which would be
much faster than using BSGS methods for the order.  Specifically, this
is the case for curves with j-invariants 0 and 1728 over any finite
field.

From the mailing list contribution by Victor Miller:

Consider the following:
{{{
def NextProgression(n,a,q):
    p = next_prime(n)
    while (p%q) != a:
        p = next_prime(p+1)
    return p
}}}
{{{
def Test(n,compute=False):
    p = NextProgression(n,2,3)
    print "found prime=",p
    F.<u> = GF(p^2)
    print "Found field"
    E = EllipticCurve(F,[0,1])
    if compute:
        NN = E.order()
        print "Found Elliptic Curve of order ",NN
    P = E.random_point()
    Q = E.random_point()
    print "Found points"
    nP = P.order()
    print "Found order of P"
    nQ = Q.order()
    print "Found order of Q"
    N = lcm(nP,nQ)
    return E,P,Q,N
}}}
{{{
time E,P,Q,n = Test(2^25)

found prime= 33554501
Found field
Found points
Found order of P
Found order of Q
Time: CPU 10.52 s, Wall: 10.77 s
}}}

compared with
{{{
time E,P,Q,n = Test(2^25,compute=True)

found prime= 33554501
Found field
Found Elliptic Curve of order  1125904604468004
Found points
Found order of P
Found order of Q
Time: CPU 0.17 s, Wall: 0.18 s
}}}

URL: http://trac.sagemath.org/15667
Reported by: cremona
Ticket author(s): John Cremona
Reviewer(s): Jean-Pierre Flori
Trac #15552: enumerate_totallyreal_fields_prim does not return polynomial as elements of a polynomial ring

The function `enumerate_totallyreal_fields_prim` is supposed to return,
according to its description,
{{{
   OUTPUT:

   the list of fields with entries "[d,f]", where "d" is the
   discriminant and "f" is a defining polynomial, sorted by
   discriminant.
}}}
Let us look at an output:
{{{
sage: E = enumerate_totallyreal_fields_prim(2, 10); E
[[5, x^2 - x - 1], [8, x^2 - 2]]
sage: E[0][1].parent()
Interface to the PARI C library
}}}
We notice from here that the polynomial does not actually belong to the
polynomial ring of `QQ`. In fact, there is no nice way to directly get
the polynomial, as in an element of `PolynomialRing(QQ)` from `E[0][1]`,
which can be then used to construct the number field.

The only way to do this is this lengthy and tedious procedure:
{{{
sage: Ecoef = [QQ(_) for _ in E[0][1].list()]
sage: x = polygen(QQ)
sage: Epol = sum(x**i * _ for i,_ in enumerate(Ecoef))
sage: Epol, Epol.parent()
(x^2 - x - 1, Univariate Polynomial Ring in x over Rational Field)
}}}

The output of the function itself should give back elements of the
polynomial ring, instead of giving us elements which are simply output
of pari.

----

Additionally,

1. the first entry of each list should belong to Sage's `Integer` ring
instead of being just a python `int`.
2. the functions `enumerate_totallyreal_fields_all` and
`enumerate_totallyreal_fields_rel` should get the same fix.

URL: http://trac.sagemath.org/15552
Reported by: ppurka
Ticket author(s): Punarbasu Purkayastha
Reviewer(s): Francis Clarke
Trac #15822: Tropical semiring cannot exponentiate infinity

Just found this while experimenting with my own semirings:

{{{
sage: T = TropicalSemiring(QQ)
sage: T.infinity() ** 2
------------------------------------------------------------------------
---
TypeError                                 Traceback (most recent call
last)
<ipython-input-28-b94a4a077331> in <module>()
----> 1 T.infinity() ** Integer(2)

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/rings/semirings/tropical_semiring.so in
sage.rings.semirings.tropical_semiring.TropicalSemiringElement.__pow__
(sage/rings/semirings/tropical_semiring.c:4218)()

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/structure/element.so in
sage.structure.element.RingElement.__mul__
(sage/structure/element.c:14520)()

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/structure/coerce.so in
sage.structure.coerce.CoercionModel_cache_maps.bin_op
(sage/structure/coerce.c:8150)()

TypeError: unsupported operand parent(s) for '*': 'Integer Ring' and
'<type 'NoneType'>'
}}}

Here is a way to solve this
(sage/rings/semirings/tropical_semiring.pyx):

{{{
    def __pow__(base, exp, dummy):
        """
        Return ``self`` to ``exp``.

        EXAMPLES::

            sage: T = TropicalSemiring(QQ)
            sage: elt = T(2)
            sage: elt**3
            6
            sage: elt**-2
            -4
            sage: elt**(3/7)
            6/7
            sage: elt**0
            0

            sage: elt = T.infinity()
            sage: elt**0
            0
            sage: elt**(1/2)
            +infinity
            sage: elt*33
            +infinity
        """
        cdef TropicalSemiringElement self, x
        self = base
        if self._val is None:
            if exp > 0:
                return self
            elif exp == 0:
                return self.parent().one()
            raise ZeroDivisionError("Tropical division by infinity")
        x = self._new()
        x._val = exp*self._val
        return x
}}}

Is this good? (I cannot upload branches from here -- "fatal: remote
error: access denied or repository not exported: /sage.git")

URL: http://trac.sagemath.org/15822
Reported by: darij
Ticket author(s): Darij Grinberg
Reviewer(s): Travis Scrimshaw
Trac #15841: sage.combinat.finite_state_machine: incorrect indent in docstring

There was an indentation error in the docstring of class
{{{sage.combinat.finite_state_machine.FiniteStateMachine}}}
starting at {{{TESTS::}}}.

URL: http://trac.sagemath.org/15841
Reported by: cheuberg
Ticket author(s): Clemens Heuberger
Reviewer(s): Daniel Krenn