stein_watkins.py

r"""
The Stein-Watkins table of elliptic curves

Sage gives access to the Stein-Watkins table of elliptic curves,
via an optional package that you must install. This is a huge
database of elliptic curves. You can download the database as a
2.6GB Sage package from http://modular.ucsd.edu/sagedb/, which you
install with the command

::

    sage -i stein-watkins-ecdb.spkg

You can also download a small version, without having to explicitly
download anything from a website, using the command

::

    sage -i stein-watkins-ecdb-mini

This database covers a wide range of conductors, but unlike
CremonaDatabase(), this database need not list all curves of a
given conductor. It lists the curves whose coefficients aren't "too
large" (see [Stein-Watkins, Ants 5]).


-  The command ``SteinWatkinsAllData(n)`` returns an
   iterator over the curves in the `n^{th}` Stein-Watkins table,
   which contains elliptic curves of conductor between `n10^5`
   and `(n+1)10^5`. Here `n` can be between
   `0` and `999`, inclusive.

-  The command ``SteinWatkinsPrimeData(n)`` returns an
   iterator over the curves in the `n^{th}` Stein-Watkins table,
   which contains prime conductor elliptic curves of conductor between
   `n10^6` and `(n+1)10^6`. Here `n` varies
   between `0` and `99`, inclusive.


EXAMPLES: We obtain the first table of elliptic curves.

::

    sage: d = SteinWatkinsAllData(0)
    sage: d
    Stein-Watkins Database a.0 Iterator

We type ``d.next()`` to get each isogeny class of
curves from ``d``::

    sage: C = d.next()                                   # optional - database_stein_watkins
    sage: C                                              # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 11
    sage: d.next()                                       # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 14
    sage: d.next()                                       # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 15

An isogeny class has a number of attributes that give data about
the isogeny class, such as the rank, equations of curves,
conductor, leading coefficient of `L`-function, etc.

::

    sage: C.data                                         # optional - database_stein_watkins
    ['11', '[11]', '0', '0.253842', '25', '+*1']
    sage: C.curves                                       # optional - database_stein_watkins
    [[[0, -1, 1, 0, 0], '(1)', '1', '5'],
     [[0, -1, 1, -10, -20], '(5)', '1', '5'],
     [[0, -1, 1, -7820, -263580], '(1)', '1', '1']]
    sage: C.conductor                                    # optional - database_stein_watkins
    11
    sage: C.leading_coefficient                          # optional - database_stein_watkins
    '0.253842'
    sage: C.modular_degree                               # optional - database_stein_watkins
    '+*1'
    sage: C.rank                                         # optional - database_stein_watkins
    0
    sage: C.isogeny_number                               # optional - database_stein_watkins
    '25'

If we were to continue typing ``d.next()`` we would
iterate over all curves in the Stein-Watkins database up to
conductor `10^5`. We could also type ``for C in d:
...``

To access the data file starting at `10^5` do the
following::

    sage: d = SteinWatkinsAllData(1)                    # optional - database_stein_watkins
    sage: C = d.next()                                  # optional - database_stein_watkins
    sage: C                                             # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 100002
    sage: C.curves                                      # optional - database_stein_watkins
    [[[1, 1, 0, 112, 0], '(8,1,2,1)', 'X', '2'],
     [[1, 1, 0, -448, -560], '[4,2,1,2]', 'X', '2']]

Next we access the prime-conductor data::

    sage: d = SteinWatkinsPrimeData(0)                 # optional - database_stein_watkins
    sage: C = d.next()                                 # optional - database_stein_watkins
    sage: C                                            # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 11

Each call ``d.next()`` gives another elliptic curve of
prime conductor::

    sage: C = d.next()                                 # optional - database_stein_watkins
    sage: C                                            # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 17
    sage: C.curves                                     # optional - database_stein_watkins
    [[[1, -1, 1, -1, 0], '[1]', '1', '4'],
     [[1, -1, 1, -6, -4], '[2]', '1', '2x'],
     [[1, -1, 1, -1, -14], '(4)', '1', '4'],
     [[1, -1, 1, -91, -310], '[1]', '1', '2']]
    sage: C = d.next()                                 # optional - database_stein_watkins
    sage: C                                            # optional - database_stein_watkins
    Stein-Watkins isogeny class of conductor 19
"""

#*****************************************************************************
#
#       Sage: Copyright (C) 2005 William Stein <[email protected]>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************

import bz2, os

import sage.databases.db   # very important that this be fully qualified

class SteinWatkinsIsogenyClass:
    def __init__(self, conductor):
        self.conductor = conductor

    def __repr__(self):
        return "Stein-Watkins isogeny class of conductor %s"%self.conductor

    def __len__(self):
        try:
            return len(self.curves)
        except AttributeError:
            return 0

    def __iter__(self):
        try:
            for E in self.curves:
                yield E
        except AttributeError:
            return


def _lines(s):
    while True:
        i = s.find("\n")
        if i == -1:
            yield ""
            return
        line = s[:i]
        s = s[i+1:]
        yield line


class SteinWatkinsAllData:
    """
    Class for iterating through one of the Stein-Watkins database files
    for all conductors.
    """
    def __init__(self, num):
        num = int(num)
        self.num = num
        if num < 0:
            raise RuntimeError, "num (=%s) must be a nonnegative integer"%num
        name = str(num)
        name = '0'*(3-len(name)) + name
        self._file = "%s/data/stein-watkins-ecdb/a.%s.bz2"%(os.environ["SAGE_ROOT"],name)
        self._iter = self.__iter__()

    def __repr__(self):
        return "Stein-Watkins Database a.%s Iterator"%self.num

    def __iter__(self):
        try:
            file = bz2.BZ2File(self._file, 'r')
        except IOError:
            raise IOError, "The Stein-Watkins data file %s must be installed."%self._file
        C = None
        for L in file:
            if len(L) == 0:
                continue
            if L[0] != '[': # new curve
                if C != None:
                    yield C
                x = L.split()
                N = int(x[0])
                C = SteinWatkinsIsogenyClass(N)
                C.rank = int(x[2])
                C.leading_coefficient = x[3]
                C.isogeny_number = x[4]
                C.modular_degree = x[5]
                C.curves = []
                C.data = x
            else:
                w = L.split()
                C.curves.append([eval(w[0]), w[1], w[2], w[3]])
        yield C

    def next(self):
        return self._iter.next()

    def __getitem__(self, N):
        """
        Return the curves of conductor N in this table. (Very slow!)
        Return all data about curves between the given levels in this
        database file.
        """
        X = []
        if isinstance(N, slice):
            min_level, max_level, step = N.indices(len(list(self)))
            for C in self:
                M = C.conductor
                if M >= min_level and M <= max_level:
                    X.append(C)
                elif M > max_level:
                    return X
        else:
            for C in self:
                M = C.conductor
                if M == N:
                    X.append(C)
                elif M > N:
                    return X
            return X

    def iter_levels(self):
        """
        Iterate through the curve classes, but grouped into lists by
        level.
        """
        iter = self.__iter__()
        C = []
        N = 0
        while True:
            try:
                E = iter.next()
            except StopIteration:
                if C != []:
                    yield C
                raise StopIteration
            if E.conductor != N:
                if C != []:
                    yield C
                C = [E]
                N = E.conductor
            else:
                C.append(E)
        yield C


class SteinWatkinsPrimeData(SteinWatkinsAllData):
    def __init__(self, num):
        num = int(num)
        self.num = num
        if num < 0:
            raise RuntimeError, "num (=%s) must be a nonnegative integer"%num
        name = str(num)
        name = '0'*(2-len(name)) + name
        self._file = "%s/data/stein-watkins-ecdb/p.%s.bz2"%(os.environ["SAGE_ROOT"], name)
        self._iter = self.__iter__()

    def __repr__(self):
        return "Stein-Watkins Prime Conductor Database p.%s Iterator"%self.num


def ecdb_num_curves(max_level=200000):
    i = 0
    N = 1
    d = SteinWatkinsAllData(i)
    v = [int(0) for _ in xrange(max_level+1)]
    while True:
        try:
            C = d.next()
        except StopIteration:
            i += 1
            d = SteinWatkinsAllData(i)
            continue
        N = C.conductor
        if N > max_level:
            break
        v[N] += len(C.curves)
    return v