r"""
###################################################################
#       Copyright (C) 2011 chris wuthrich
#  Distributed under the terms of the GNU General Public License ###################################################################

This file contains a few useful functions that are needed to compute a simple $p$-descent on an elliptic curve over a number field when the kernel of the isogeny contains a point. This file was written to do experiments for the article

Jean Gillibert, Christian Wuthrich, The class group pairing and $p$-descent on elliptic curves, 2011.

Let $\varphi \colon E \to E'$ be an isogeny between elliptic curves over a number field $K$ and suppose that the dual isogeny $\hat\varphi$ contains a point $P \in E'(K)$ in the kernel. Let $p$ be the degree of the isogeny. We will suppose that $p$ is a odd prime. 

The main output of the functions implemented in this file is the dimensions as F_p-vector spaces of the phi and phihat Selmer groups. Some conditions need to be satisfied for the computations to be correct.

EXAMPLES. The basic use is the following ::

    sage: E2 = EllipticCurve("4730k1")
    sage: P = E2.lift_x(257)
    sage: P.order()
    7
    sage: Selmer_group_dimensions(P)
    (2, 0)

    sage: E2 = EllipticCurve("570l2")
    sage: P = E2.lift_x(390)
    sage: P.order()
    5
    sage: Selmer_group_dimensions(P)
    (3, 1)

To have more information about the computations one can set an optional argument ``verbose`` ::

    sage: Selmer_group_dimensions(P,verbose=True)
    sets S1 and S2 :  [2, 3, 5] [19]
    Basis of H1 :  [2, 3, 5]
    local term :  1
    classgroup :  0
    localisation map :  []
    (3, 1)

Here an example over a cubic field ::

    sage: K.<t> = NumberField(x^3 + x^2 -2*x-1)
    sage: E2 = EllipticCurve("11a1").base_extend(K)
    sage: P = E2.lift_x(5)
    sage: Selmer_group_dimensions(P,verbose=True)
    sets S1 and S2 :  [Fractional ideal (11)] []
    roots of unity :  []
    +fundamental units :  [11, t + 1, t^2 - 1]
    Basis of H1 :  [11, t + 1, t^2 - 1]
    local term :  0
    classgroup :  0
    (3, 0)

A quintic example::

    sage: K.<t> = NumberField(x^5 + x^4 - 24*x^3 - 17*x^2 + 41*x - 13)
    sage: E2 = EllipticCurve("11a1").base_extend(K)
    sage: P = E2.lift_x(5)
    sage: Selmer_group_dimensions(P,verbose=True)
    sets S1 and S2 :  [Fractional ideal (11, t - 1), Fractional ideal (11, t + 4), Fractional ideal (11, t + 5), Fractional ideal (11, t - 5), Fractional ideal (11, t - 2)] []
    roots of unity :  []
    +fundamental units :  [t - 1, 6/29*t^4 + 14/29*t^3 - 135/29*t^2 - 282/29*t + 73/29, 14/29*t^4 + 23/29*t^3 - 315/29*t^2 - 455/29*t + 209/29, 11/29*t^4 + 16/29*t^3 - 262/29*t^2 - 285/29*t + 332/29, 8/29*t^4 + 9/29*t^3 - 180/29*t^2 - 173/29*t + 107/29, 10/29*t^4 + 4/29*t^3 - 225/29*t^2 - 35/29*t + 54/29, 2/29*t^4 - 5/29*t^3 - 45/29*t^2 + 109/29*t - 53/29, 31/29*t^4 + 53/29*t^3 - 712/29*t^2 - 1022/29*t + 614/29, 3/29*t^4 + 7/29*t^3 - 82/29*t^2 - 83/29*t + 80/29]
    Basis of H1 :  [t - 1, 6/29*t^4 + 14/29*t^3 - 135/29*t^2 - 282/29*t + 73/29, 14/29*t^4 + 23/29*t^3 - 315/29*t^2 - 455/29*t + 209/29, 11/29*t^4 + 16/29*t^3 - 262/29*t^2 - 285/29*t + 332/29, 8/29*t^4 + 9/29*t^3 - 180/29*t^2 - 173/29*t + 107/29, 10/29*t^4 + 4/29*t^3 - 225/29*t^2 - 35/29*t + 54/29, 2/29*t^4 - 5/29*t^3 - 45/29*t^2 + 109/29*t - 53/29, 31/29*t^4 + 53/29*t^3 - 712/29*t^2 - 1022/29*t + 614/29, 3/29*t^4 + 7/29*t^3 - 82/29*t^2 - 83/29*t + 80/29]
    local term :  0
    classgroup :  0
    (9, 0)

A more complicated cubic example of conductor 313::

    sage: m = 313
    sage: Km = CyclotomicField(m)
    sage: zm = Km.0
    sage: a = primitive_root(m)
    sage: t = sum( zm^(  power_mod(a,3 *n,m) ) for n in [0..(euler_phi(m)//3 -1)] )
    sage: f = t.minpoly()
    sage: K.<t> = NumberField(f)
    sage: K.class_number()
    7

    sage: E2 = EllipticCurve("294b2")
    sage: E2 = E2.base_extend(K)
    sage: P = E2.lift_x(6)
    sage: Selmer_group_dimensions(P,verbose=True)
    sets S1 and S2 :  [Fractional ideal (2), Fractional ideal (3)] [Fractional ideal (7, t), Fractional ideal (7, t + 3), Fractional ideal (7, t - 2)]
    roots of unity :  []
    +fundamental units :  [2, 3, t - 5, t - 6]
    Fractional ideal class (5, t - 2)  gives a generator  8*t^2 + 53*t - 513
    Basis of H1 :  [2, 3, t - 5, t - 6, 8*t^2 + 53*t - 513]
    local term :  3
    classgroup :  1
    localisation map :  [5 5 5]
    [1 1 1]
    [6 5 3]
    [2 4 1]
    [4 1 2]
    (3, 2)

This file contains further functions that may be useful, such as neron_scaling.

"""

# this function is needed to distinguish places above p where we have to restrict or relax the conditions.

def neron_scaling(phi,v):
    r"""
    Given an isogeny between elliptic curves over a number field and a place v,
    this gives back the valuation of the constant a such that
    phi*(omega') = a*omega
    where omegas are Neron differentials.
    
    INPUT:
    
    - `phi` - an isogeny between elliptic curves over a number field
    
    - `v` - a finite place of this field
    
    OUTPUT: an integer
    
    Note: This only makes sense if v is above p= degree of phi.
    
    
    EXAMPLES::

        sage: E = EllipticCurve("20a1")
        sage: P= E.lift_x(0)
        sage: P.order()
        3
        sage: neron_scaling(phihat,3)
        1
        sage: neron_scaling(phi,3)
        0
     
        sage: E = EllipticCurve("11a1")
        sage: E = E.change_weierstrass_model([5,1,0,0])
        sage: E2 = EllipticCurve("11a2").change_weierstrass_model([1/25,0,1,0])
        sage: P = E.torsion_points()[2]
        sage: phi = E.isogeny(P, codomain=E2)
        sage: neron_scaling(phi,5)
        0
        sage: neron_scaling(phi.dual(),5)
        1
            
    """
    E = phi.domain()
    E2 = phi.codomain()
    Emin = E.local_data(v).minimal_model()
    E2min = E2.local_data(v).minimal_model()
    u = E.isomorphism_to(Emin).u
    u2 = E2.isomorphism_to(E2min).u
    a1 = phi.formal()[1]
    return valuation(a1,v) - valuation(u,v) + valuation(u2,v)

# these are the functions that find the places of K where the conditions have to be relaxed or restricted.

def forward_split(P):
    r"""
    Given a torsion point P on an elliptic curve over a number field,
    assuming our assumptions hold, this 
    computes the set of forward split places (above p or not). These are
    the split multiplicative places such that c'_v = p * c_v
    
    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: a set of places
    
    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: forward_split(P)
        [11]
        
        sage: K = CyclotomicField(19)
        sage: EK = E.base_extend(K)
        sage: P = EK(P)
        sage: forward_split(P)
        [Fractional ideal (11, zeta19^3 + zeta19^2 + 2*zeta19 - 1), Fractional ideal (11, zeta19^3 + 2*zeta19^2 - 3*zeta19 - 1), Fractional ideal (11, zeta19^3 + 3*zeta19^2 - 2*zeta19 - 1), Fractional ideal (11, zeta19^3 + 3*zeta19^2 - 5*zeta19 - 1), Fractional ideal (11, zeta19^3 + 5*zeta19^2 - 3*zeta19 - 1), Fractional ideal (11, zeta19^3 - 2*zeta19^2 - zeta19 - 1)]

    """
    E2 = P.curve()
    vs = [v for v in E2.discriminant().support() if E2.local_data(v).has_split_multiplicative_reduction()]
    phihat = E2.isogeny(P)
    E = phihat.codomain()
    return [v for v in vs if E.tamagawa_number(v) < E2.tamagawa_number(v)]

def backward_split(P):
    r"""
    Given a torsion point P on an elliptic curve over a number field,
    assuming our assumptions hold, this 
    computes the set of backward split places. They must all be outside p.
    These are
    the split multiplicative places such that c'_v = 1/p * c_v

    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: a set of places

    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: backward_split(P)
        []
        sage: K = CyclotomicField(5)
        sage: EK = E.base_extend(K)
        sage: Q = EK.torsion_points()[7]
        sage: Q
        (3*zeta5^3 + 7*zeta5^2 + 5*zeta5 : 14*zeta5^3 + 7*zeta5^2 - 6*zeta5 - 11 : 1)
        sage: backward_split(Q)
        [Fractional ideal (zeta5^3 + 2*zeta5^2 + 1)]
 
    """
    E2 = P.curve()
    vs = [v for v in E2.discriminant().support() if E2.local_data(v).has_split_multiplicative_reduction()]
    phihat = E2.isogeny(P)
    E = phihat.codomain()
    return [v for v in vs if E.tamagawa_number(v) > E2.tamagawa_number(v)]

def nonsplit(P):
    r"""
    Given a torsion point P on an elliptic curve over a number field,
    assuming our assumptions hold, this 
    computes the set of non-split places

    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: a set of places

    EXAMPLES::
    
        sage: E = EllipticCurve("2310t1")
        sage: P = [ P for P in E.torsion_points() if P.order() == 3][0]
        sage: P
        (14 : -175 : 1)
        sage: nonsplit(P)
        [5, 11]
        sage: E = EllipticCurve("2310l1")
        sage: P = [ P for P in E.torsion_points() if P.order() == 3][0]
        sage: nonsplit(P)
        [2, 11]
        sage: E = EllipticCurve("2310g1")
        sage: P = [ P for P in E.torsion_points() if P.order() == 3][0]
        sage: nonsplit(P)
        [2, 5, 11]

        sage: K = QuadraticField(-3,"w")
        sage: EK = E.base_extend(K)
        sage: P = EK(P)
        sage: nonsplit(P)
        []

    """
    E2 = P.curve()
    return [v for v in E2.discriminant().support() if E2.local_data(v).has_nonsplit_multiplicative_reduction()]

def forward_p(P):
    r"""
    Given a torsion point P on an elliptic curve over a number field,
    assuming our assumptions hold, this 
    computes the set of forward places above p. These are the places 
    for which the isogeny with kernel P has Neron scaling 0.

    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: a set of places
    
    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: forward_p(P)
        [5]
        sage: backward_p(P)
        []

        sage: E = EllipticCurve("126a3")
        sage: P = E.lift_x(1)
        sage: P.order()
        3
        sage: forward_p(P)
        []
        sage: backward_p(P)
        [3]

    """
    p = P.order()
    phihat = P.curve().isogeny(P)
    if P.curve().base_ring() != QQ: 
        vs = P.curve().base_ring().primes_above(p)
        return [v for v in vs if neron_scaling(phihat,v) == 0]
    else:
         return [v for v in [p] if neron_scaling(phihat,v) == 0]

def backward_p(P):
    r"""
    Given a torsion point P on an elliptic curve over a number field,
    assuming our assumptions hold, this 
    computes the set of backward places above p. These are the places 
    for which the dual isogeny to the one with kernel P has Neron scaling 0.

    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: a set of places
    
    EXAMPLES::

        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: forward_p(P)
        [5]
        sage: backward_p(P)
        []

        sage: E = EllipticCurve("126a3")
        sage: P = E.lift_x(1)
        sage: P.order()
        3
        sage: forward_p(P)
        []
        sage: backward_p(P)
        [3]

    """
    E2 = P.curve()
    K = E2.base_ring()
    p = P.order()
    if K == QQ:
        vs = [p]
    else:
        vs = K.primes_above(p)
    phihat = E2.isogeny(P)
    res = []
    for v in vs:
        a = neron_scaling(phihat,v)
        if K == QQ:
            e = 1
        else:
            e = v.ramification_index()
        if a == e:
            res.append(v)
    return res

# This functions checks if all the conditions are satisfied

def do_the_hyp_hold(P):
    r"""
    Given a torsion point on an elliptic curve over a number field, this checks if the conditions
    in our paper are satisfied.
    
    INPUT: a torsion point on an elliptic curve over a number field
    
    OUTPUT: boolean
    
    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: do_the_hyp_hold(P)
        True 

        sage: E = EllipticCurve("27a4")
        sage: P = E.lift_x(3)
        sage: do_the_hyp_hold(P)
        False
        sage: E.kodaira_symbol(3)
        IV

    """
    E2 = P.curve()
    K = E2.base_ring()
    p = ZZ(P.order())
    ks = [KodairaSymbol("IV*"), KodairaSymbol("IV")]
    if not p.is_prime(): return False
    if p == 2 : return False
    E = E2.isogeny(P).codomain()
    if p == 3:
        if any( E.local_data(v).kodaira_symbol() in ks for v in E.discriminant().support() ): return False
    if p == 3:
        if any( E2.local_data(v).kodaira_symbol() in ks for v in E2.discriminant().support() ): return False
    if K != QQ:
        if K.primes_above(p) != forward_p(P) + backward_p(P): return False    
    return True

# The global cohomology group

def basis_of_H1_mu_p(K,S,p, verbose=False):
    r"""
    This gives back a list of elements in K, such that their image in K*/p
    generates H^1(OK\S,mu_p). S is a finite set of primes in K. 
    
    INPUT: 
    
    - `K` - a number field
    
    - `S` - a finite set of primes of K
    
    - `p` - an odd prime number
    
    - `verbose` - boolean (optional, default False)
    
    OUTPUT: a list of elements in K*

    EXAMPLES::
        
        sage: K.<t> = NumberField(x^2+23)
        sage: basis_of_H1_mu_p(K,[],3)
        [-1/2*t - 3/2]
        
        sage: basis_of_H1_mu_p(QQ,[2,3,5],7)
        [2, 3, 5]
        
    """
    res = []
    
    if K != QQ :
        # mu_p(K)
        muK = K.roots_of_unity()
        if len(muK) % p == 0:
            ze = [ze for ze in muK if ze.multiplicative_order() == p][0]
            res.append(ze)
        if verbose:
            print "roots of unity : ", res 
        # fundamental units
        res += [et for et in K.S_units(S) if et.multiplicative_order() == oo ]
        if verbose:
            print "+fundamental units : ", res
        # class group
        A = K.S_class_group(S)
        for aa in A.gens():
            if aa.order() % p == 0:
                bb = aa ** (aa.order()//p)
                bb = bb.ideal()
                bb = bb ** p
                res += [bb.gens_reduced()[0]]
                if verbose:
                    print aa , " gives a generator ", res[-1]
        # check
        for y in res:
            notinS = [v for v in y.support() if v not in S]
            # if verbose:
            #    print y, " has valuations ", [ valuation(y,v) for v in notinS ], " at ", notinS
            assert all( valuation(y,v) % p == 0  for v in notinS )
            
            
    else : #K == Q
        res = []
        if p == 2:
            res += [-1]
        res += S
        
    return res
    
# the two localisation maps that are needed to impose restricted conditions at places    
    
def _loc_outside_p(x,gv,p):
    r"""
    Given zn x in K* a primitive element of kv* at a place v outside p, 
    this gives the image in H^1(O_v,mu_p) as an element in F_p.
    
    Note: This function is only for internal use.
    
    INPUT:
    
    - `x` - an element of a number field
    
    - `gv` - a multiplicative generator of the residue field at a place outside p
    
    - `p` - a prime number
    
    OUTPUT: an element of the finite field with p elements
    
    EXAMPLES::
        
        sage: K.<t> = NumberField(x^2+3)
        sage: v = K.ideal(101)
        sage: kv = v.residue_field()
        sage: gv = kv(kv.multiplicative_generator())
        sage: _loc_outside_p(12*t-94,gv,5)
        3
         
        sage: v = 7
        sage: kv = ZZ.residue_field(v)
        sage: gv = kv(kv.multiplicative_generator())
        sage: _loc_outside_p(12345, gv, 3)  
        1
        
        sage: K = CyclotomicField(103)
        sage: v = K.primes_above(103)[0]
        sage: kv = v.residue_field()
        sage: gv = kv(kv.multiplicative_generator())
        sage: _loc_outside_p(K.0^7+K.0*88-111, gv, 17)
        3
        
    """
    kv = gv.parent()
    qv = kv.cardinality()
    if (qv-1) % p != 0 : return GF(p)(0)
    # v = kv.ideal()
    lo = kv(x).log(gv)
    return GF(p)(lo)
  

def _loc_at_p(x,tv,v,p):
    r"""
    Given an x in K* with trivial valuation at a place v above p, 
    this gives the image in H^1(O_v,mu_p) as an element in F_p.
    tv is a fixed uniformiser at v.
    
    This is only implemented when e_v < p-1
  
    Note: This function is only for internal use.
    
    INPUT:
    
    - `x` - an element of a number field
    
    - `tv` - a uniformizer at 
    
    - `v` - a place
    
    - `p` - a prime number
    
    OUTPUT: a list of element of the finite field with p elements
    
    EXAMPLES::

        sage: _loc_at_p( 312311, 7, 7, 7 )
        [5]

        sage: K = CyclotomicField(11)
        sage: z = K.0
        sage: v  = K.primes_above(3)[0]
        sage: tv = K.uniformizer(v)
        sage: p = 3
        sage: _loc_at_p( 123123*z^2+ 12311, tv,v,p)
        [2, 0, 1, 0, 0]

    """
    if v not in ZZ:
        ev = v.ramification_index()
        assert ev < p-1
        kv = v.residue_field()
        V = kv.vector_space()
        fv = v.residue_class_degree()
        # nv = ev*fv
        qv = p ** fv
        assert valuation(x,v) == 0
        y = x ** (qv-1) - 1
        
        mbe = v ** (p-1)
        y = (-y).mod(mbe)
        # compute logarithm
        lo = sum( (y ** i).mod(mbe)/i for i in range(1,p+1) ) 
        lo = lo/tv
        
        # make integral modulo mbe
        de = lo.denominator()
        if de % p != 0 :
            lo = de.inverse_mod(p) * (lo*de)
            lo = lo.mod(mbe)
        else: # there are primes other than v in the den ideal of lo
            ff = lo.denominator_ideal().factor()
            dee = prod( v.number_field().uniformizer(w[0]) ** w[1] for w in ff )
            assert valuation(dee, v) == 0, "I was too lazy to implement this case, unless I ever encountered it."
            deeinv = dee.inverse_mod(mbe)
            lo = deeinv * (dee * lo)
            lo = lo.mod(mbe)
            
        res = []
        for j in srange(ev):
            lot = lo.mod(v)
            lo = lo - lot
            lo = lo/tv
            kvt = kv(lot)
            if V.dimension() > 1:
                kvt = V(kvt)
                kvt = kvt.list()
            else:
                kvt = [kvt]
            res += kvt
        return res   
    else: # if K == QQ
        assert valuation(x,v) == 0
        assert p != 2 
        xw = x ** (p-1)
        return [ GF(p)( (xw-1)/tv ) ]

# finally the main function

def phi_Selmer_group(P, verbose = False):
    r"""
    Given a torsion point P on an elliptic curve over a number field, this 
    returns the the Selmer group for phi.
    Here the kernel of the dual of phi is generated by P.
    
    INPUT:
    
    - `P` - a torsion point on an elliptic curve over a number field
    
    - `verbose` - boolean (default = False)
    
    OUTPUT: a list of elements in K*
    
    The Selmer group is generated by this list as a F_p-vector space
    in K*/p.
    
    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: phi_Selmer_group(P)
        [11]
        
        sage: Selmer_group_dimensions(P,verbose=True)
        sets S1 and S2 :  [11] []
        Basis of H1 :  [11]
        local term :  0
        classgroup :  0
        [11]
        
        sage: K = QuadraticField(-23, "a")
        sage: EK = E.base_extend(K)
        sage: P = EK.lift_x(5)
        sage: phi_Selmer_group(P,verbose=True)
        sets S1 and S2 :  [Fractional ideal (11)] []
        roots of unity :  []
        +fundamental units :  [11]
        Basis of H1 :  [11]
        local term :  0
        classgroup :  0
        [11]

        sage: K = QuadraticField(23, "a")
        sage: EK = E.base_extend(K)
        sage: P = EK.lift_x(5)
        sage: phi_Selmer_group(P,verbose=True)
        sets S1 and S2 :  [Fractional ideal (2*a + 9), Fractional ideal (2*a - 9)] []
        roots of unity :  []
        +fundamental units :  [2*a + 9, 2*a - 9, 5*a - 24]
        Basis of H1 :  [2*a + 9, 2*a - 9, 5*a - 24]                                                
        local term :  0                                                                            
        classgroup :  0                                                                            
        [2*a + 9, 2*a - 9, 5*a - 24]                                                               
    """
    
    if not do_the_hyp_hold(P):
        raise ValueError, "One of the hypotheses does not hold"
    
    p = P.order()
    E2 = P.curve()
    K = E2.base_ring()
    
    s1s = forward_split(P)
    s2s = backward_split(P)
    s2n = nonsplit(P)
    s2p = backward_p(P)
    
    # set of places where we relax the condition 
    S1 = s1s 
    # set of places where we restrict the conditions
    S2 = s2s + s2p + s2n
    if verbose:
        print "sets S1 and S2 : ", S1 ,S2

    B = basis_of_H1_mu_p(K,S1,p, verbose=verbose)
    A = K.class_group()
    clp = len([a for a in A.elementary_divisors() if a%p == 0])
    if K != QQ:
        c = len(s2s) + sum(w.ramification_index() * w.residue_class_degree() for w in s2p)
    else:
        c = len(S2)
            
    if verbose:
        print "Basis of H1 : ", B
        print "local term : ", c
        print "classgroup : ", clp
        
    if c == 0:
        return B
    elif len(B) == 0:
        return []
    else:
        if K != QQ:
            gs = dict([[w, w.residue_field()(w.residue_field().multiplicative_generator())] for w in s2s])
        else:
            gs = dict([[w, GF(w).multiplicative_generator()] for w in s2s])
        if K != QQ:
            tp = dict([[w, [tv for tv in w.gens() if valuation(tv,w) == 1][0] ] for w in s2p ] )
        else:
            tp = dict([[w, w ] for w in s2p ] )
        
        M = matrix(GF(p), [[ _loc_outside_p(xx, gs[w], p) for w in s2s] + flatten( [ _loc_at_p(xx,tp[w],w,p) for w in s2p ] ) for xx in B])
        if verbose:
            print "localisation map : " , M
        Selphi = M.kernel()
        if verbose:
            print "Selmer group basis : " , Selphi.basis()
        return [ prod(B[j] ** ve[j] for j in range(len(ve))) for ve in Selphi.basis() ]
        

def Selmer_group_dimensions(P, verbose = False):
    r"""
    Given a torsion point P on an elliptic curve over a number field, this 
    returns the dimensions of the Selmer group for phi and its dual.
    Here the kernel of the dual of phi is generated by P.
    
    INPUT:
    
    - `P` - a torsion point on an elliptic curve over a number field
    
    - `verbose` - boolean (default = False)
    
    OUTPUT: a pair of integers
    
    EXAMPLES::
    
        sage: E = EllipticCurve("11a1")
        sage: P = E.lift_x(5)
        sage: Selmer_group_dimensions(P)
        (1, 0)
        
        sage: Selmer_group_dimensions(P,verbose=True)
        sets S1 and S2 :  [11] []
        Basis of H1 :  [11]
        local term :  0
        classgroup :  0
        (1, 0)
        
        sage: K = QuadraticField(-23, "a")
        sage: EK = E.base_extend(K)
        sage: P = EK.lift_x(5)
        sage: Selmer_group_dimensions(P,verbose=True)
        sets S1 and S2 :  [Fractional ideal (11)] []
        roots of unity :  []
        +fundamental units :  [11]
        Basis of H1 :  [11]
        local term :  0
        classgroup :  0
        (1, 0)

        sage: K = QuadraticField(23, "a")
        sage: EK = E.base_extend(K)
        sage: P = EK.lift_x(5)
        sage: Selmer_group_dimensions(P,verbose=True)
        sets S1 and S2 :  [Fractional ideal (2*a + 9), Fractional ideal (2*a - 9)] []
        roots of unity :  []
        +fundamental units :  [2*a + 9, 2*a - 9, 5*a - 24]
        Basis of H1 :  [2*a + 9, 2*a - 9, 5*a - 24]
        local term :  0
        classgroup :  0
        (3, 0)

    """
    
    if not do_the_hyp_hold(P):
        raise ValueError, "One of the hypotheses does not hold"
    
    p = P.order()
    E2 = P.curve()
    K = E2.base_ring()
    
    s1s = forward_split(P)
    s2s = backward_split(P)
    s2n = nonsplit(P)
    s2p = backward_p(P)
    
    # set of places where we relax the condition 
    S1 = s1s 
    # set of places where we restrict the conditions
    S2 = s2s + s2p + s2n
    if verbose:
        print "sets S1 and S2 : ", S1 ,S2

    B = basis_of_H1_mu_p(K,S1,p, verbose=verbose)
    A = K.class_group()
    clp = len([a for a in A.elementary_divisors() if a%p == 0])
    if K != QQ:
        c = len(s2s) + sum(w.ramification_index() * w.residue_class_degree() for w in s2p)
    else:
        c = len(S2)
            
    if verbose:
        print "Basis of H1 : ", B
        print "local term : ", c
        print "classgroup : ", clp
        
    if c == 0:
        return len(B), clp
    elif len(B) == 0:
        return 0, len(S2) + clp
    else:
        if K != QQ:
            gs = dict([[w, w.residue_field()(w.residue_field().multiplicative_generator())] for w in s2s])
        else:
            gs = dict([[w, GF(w).multiplicative_generator()] for w in s2s])
        if K != QQ:
            tp = dict([[w, [tv for tv in w.gens() if valuation(tv,w) == 1][0] ] for w in s2p ] )
        else:
            tp = dict([[w, w ] for w in s2p ] )
        
        M = matrix(GF(p), [[ _loc_outside_p(xx, gs[w], p) for w in s2s] + flatten( [ _loc_at_p(xx,tp[w],w,p) for w in s2p ] ) for xx in B])
        if verbose:
            print "localisation map : " , M
        dimselphi =  M.kernel().dimension()
        
        dimselphihat = c + clp + dimselphi - len(B)
        return dimselphi, dimselphihat