Module generic

The m-th power of a, where m is a non-negative
integer and a is a Python object on which 
multiplication is defined.  The exponentiation
is done using the standard binary powering algorithm.

EXAMPLES:
    sage: power(2,5)
    32
    sage: power(RealField()('2.5'),4)
    39.0625000000000
    sage: power(0,0)
    Traceback (most recent call last):
    ...
    ArithmeticError: 0^0 is undefined.
    sage: power(2,-3)
    1/8

Returns n*a [or a**n], where n is any integer and a is a Python
object on which a group operaton such as addition or
multiplication is defined.  Uses the standard binary algorithm.

EXAMPLES:
    sage: multiple(2,5)
    32
    sage: multiple(RealField()('2.5'),4)
    39.0625000000000
    sage: multiple(2,-3)
    1/8
    sage: multiple(2,100,'+') == 100*2
    True
    sage: multiple(2,100) == 2**100
    True
    sage: multiple(2,-100,) == 2**-100
    True
    sage: R.<x>=ZZ[]
    sage: multiple(x,100)
    x^100
    sage: multiple(x,100,'+')
    100*x
    sage: multiple(x,-10)
    1/x^10

Idempotence is detected making this fast:    
    sage: multiple(1,10^1000)
    1

    sage: E=EllipticCurve('389a1')
    sage: P=E(-1,1)
    sage: multiple(P,10,'+')
    (645656132358737542773209599489/22817025904944891235367494656 : 525532176124281192881231818644174845702936831/3446581505217248068297884384990762467229696 : 1)
    sage: multiple(P,-10,'+')
    (645656132358737542773209599489/22817025904944891235367494656 : -528978757629498440949529703029165608170166527/3446581505217248068297884384990762467229696 : 1)

Totally generic discrete baby-step giant-step function.

Solves n*a=b (or a^n=b) with lb<=n<=ub where bounds==(lb,ub),
raising an error if no such n exists.

a and b must be elements of some group with given identity,
inverse of x given by inverse(x), and group operation on x,y by
op(x,y).

If operation is '*' or '+' then the other
arguments are provided automatically; otherwise they must be
provided by the caller.

INPUT:
    a    -- group element
    b    -- group element
    bounds -- a 2-tuple of integers (lower,upper) with 0<=lower<=upper
    operation -- string: '*', '+', 'other'
    identity -- the identity element of the group
    inverse()  -- function of 1 argument x returning inverse of x
    op() -- function of 2 arguments x,y returning x*y in group

OUTPUT: 
    Returns an integer $n$ such that $a^n = b$ (or $n*a = b$).
    If no such $n$ exists, this function raises a ValueError exception.

NOTE: This is a generalization of discrete logarithm.  One
    situation where this version is useful is to find the order of
    an element in a group where we only have bounds on the group
    order (see the elliptic curve example below).

ALGORITHM: Baby step giant step.  Time and space are soft
    O(sqrt(n)) where n is the difference between upper and lower
    bounds.

EXAMPLES:
    sage: b = Mod(2,37);  a = b^20
    sage: bsgs(b, a, (0,36))
    20

    sage: p=next_prime(10^20)
    sage: a=Mod(2,p); b=a^(10^25)
    sage: bsgs(a, b, (10^25-10^6,10^25+10^6)) == 10^25
    True

    sage: K = GF(3^6,'b')
    sage: a = K.gen()
    sage: b = a^210
    sage: bsgs(a, b, (0,K.order()-1))
    210

    sage: K.<z>=CyclotomicField(230)
    sage: w=z^500
    sage: bsgs(z,w,(0,229))
    40

    An additive example in an elliptic curve group:
    sage: F.<a>=GF(37^5,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: P=E.lift_x(a); P
    (a : 9*a^4 + 22*a^3 + 23*a^2 + 30 : 1)

    This will return a multiple of the order of P:
    sage: bsgs(P,P.parent()(0),Hasse_bounds(F.order()),operation='+')
    69327408

AUTHOR:
    -- John Cremona (2008-03-15) 

Totally generic discrete log function.

a and base must be elements of some group with identity given by
identity, inverse of x by inverse(x), and group operation on x,y
by op(x,y).

If operation is '*' or '+' then the other
arguments are provided automatically; otherwise they must be
provided by the caller.

WARNING: If x has a log method, it is likely to be vastly faster
than using this function.  E.g., if x is an integer modulo n, use
its log method instead!

INPUT:
    a    -- group element
    base -- group element (the base)
    ord  -- integer (multiple of order of base, or None)
    operation -- string: '*', '+', 'other'
    identity -- the group's identity
    inverse()  -- function of 1 argument x returning inverse of x
    op() -- function of 2 arguments x,y returning x*y in group

OUTPUT: 
    Returns an integer $n$ such that $b^n = a$ (or $n*b = a$),
    assuming that ord is a multiple of the order of the base $b$.
    If ord is not specified an attempt is made to compute it.

    If no such $n$ exists, this function raises a ValueError exception.

ALGORITHM: Baby step giant step.

EXAMPLES:
    sage: b = Mod(2,37);  a = b^20
    sage: discrete_log(a, b)
    20
    sage: b = Mod(2,997);  a = b^20
    sage: discrete_log(a, b)
    20        

    sage: K = GF(3^6,'b')
    sage: b = K.gen()
    sage: a = b^210
    sage: discrete_log(a, b, K.order()-1)
    210

    sage: b = Mod(1,37);  x = Mod(2,37)
    sage: discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of 2 found to base 1
    sage: b = Mod(1,997);  x = Mod(2,997)
    sage: discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of 2 found to base 1

    See trac\#2356:
    sage: F.<w> = GF(121)
    sage: v = w^120
    sage: v.log(w)
    0

    sage: K.<z>=CyclotomicField(230)
    sage: w=z^50
    sage: discrete_log(w,z)
    50

    An example where the order is infinite: note that we must give
    an upper bound here:
    sage: K.<a> = QuadraticField(23)
    sage: eps = 5*a-24        # a fundamental unit
    sage: eps.multiplicative_order()
    +Infinity
    sage: eta = eps^100
    sage: discrete_log(eta,eps,1000)
    100
   
    In this case we cannot detect negative powers:
    sage: eta = eps^(-3)
    sage: discrete_log(eta,eps,100)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of -11515*a - 55224 found to base 5*a - 24

    But we can invert the base (and negate the result) instead:
    sage: - discrete_log(eta^-1,eps,100)
    -3

    An additive example: elliptic curve DLOG:
    sage: F=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: F.<a>=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: P=E(25*a + 16 , 15*a + 7 )
    sage: P.order()
    672
    sage: Q=39*P; Q
    (36*a + 32 : 5*a + 12 : 1)
    sage: discrete_log(Q,P,P.order(),'+')
    39

AUTHOR:
    -- William Stein and David Joyner (2005-01-05)
    -- John Cremona (2008-02-29) rewrite using dict() and make generic

Totally generic discrete log function.

a and base must be elements of some group with identity given by
identity, inverse of x by inverse(x), and group operation on x,y
by op(x,y).

If operation is '*' or '+' then the other
arguments are provided automatically; otherwise they must be
provided by the caller.

WARNING: If x has a log method, it is likely to be vastly faster
than using this function.  E.g., if x is an integer modulo n, use
its log method instead!

INPUT:
    a    -- group element
    base -- group element (the base)
    ord  -- integer (multiple of order of base, or None)
    operation -- string: '*', '+', 'other'
    identity -- the group's identity
    inverse()  -- function of 1 argument x returning inverse of x
    op() -- function of 2 arguments x,y returning x*y in group

OUTPUT: 
    Returns an integer $n$ such that $b^n = a$ (or $n*b = a$),
    assuming that ord is a multiple of the order of the base $b$.
    If ord is not specified an attempt is made to compute it.

    If no such $n$ exists, this function raises a ValueError exception.

ALGORITHM: Baby step giant step.

EXAMPLES:
    sage: b = Mod(2,37);  a = b^20
    sage: old_discrete_log(a, b)
    20
    sage: b = Mod(2,997);  a = b^20
    sage: old_discrete_log(a, b)
    20        

    sage: K = GF(3^6,'b')
    sage: b = K.gen()
    sage: a = b^210
    sage: old_discrete_log(a, b, K.order()-1)
    210

    sage: b = Mod(1,37);  x = Mod(2,37)
    sage: old_discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: Log of 2 to the base 1 does not exist.
    sage: b = Mod(1,997);  x = Mod(2,997)
    sage: old_discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: Log of 2 to the base 1 does not exist.        

    See trac\#2356:
    sage: F.<w> = GF(121)
    sage: v = w^120
    sage: v.log(w)
    0

    sage: K.<z>=CyclotomicField(230)
    sage: w=z^50
    sage: old_discrete_log(w,z)
    50

    An example where the order is infinite: note that we must give
    an upper bound here:
    sage: K.<a> = QuadraticField(23)
    sage: eps = 5*a-24        # a fundamental unit
    sage: eps.multiplicative_order()
    +Infinity
    sage: eta = eps^100
    sage: old_discrete_log(eta,eps,1000)
    100
   
    In this case we cannot detect negative powers:
    sage: eta = eps^(-3)
    sage: old_discrete_log(eta,eps,100)
    Traceback (most recent call last):
    ...
    ValueError: Log of -11515*a - 55224 to the base 5*a - 24 does not exist.

    But we can invert the base (and negate the result) instead:
    sage: - old_discrete_log(eta^-1,eps,100)
    -3

    An additive example: elliptic curve DLOG:
    sage: F=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: F.<a>=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: P=E(25*a + 16 , 15*a + 7 )
    sage: P.order()
    672
    sage: Q=39*P; Q
    (36*a + 32 : 5*a + 12 : 1)
    sage: old_discrete_log(Q,P,P.order(),'+')
    39

AUTHOR:
    -- William Stein and David Joyner (2005-01-05)
    -- John Cremona (2008-02-29) rewrite using dict() and make generic

Totally generic discrete log function.

a and base must be elements of some group with identity given by
identity, inverse of x by inverse(x), and group operation on x,y
by op(x,y).

If operation is '*' or '+' then the other
arguments are provided automatically; otherwise they must be
provided by the caller.

WARNING: If x has a log method, it is likely to be vastly faster
than using this function.  E.g., if x is an integer modulo n, use
its log method instead!

INPUT:
    a    -- group element
    base -- group element (the base)
    ord  -- integer (multiple of order of base, or None)
    operation -- string: '*', '+', 'other'
    identity -- the group's identity
    inverse()  -- function of 1 argument x returning inverse of x
    op() -- function of 2 arguments x,y returning x*y in group

OUTPUT: 
    Returns an integer $n$ such that $b^n = a$ (or $n*b = a$),
    assuming that ord is a multiple of the order of the base $b$.
    If ord is not specified an attempt is made to compute it.

    If no such $n$ exists, this function raises a ValueError exception.

ALGORITHM: Baby step giant step.

EXAMPLES:
    sage: b = Mod(2,37);  a = b^20
    sage: discrete_log(a, b)
    20
    sage: b = Mod(2,997);  a = b^20
    sage: discrete_log(a, b)
    20        

    sage: K = GF(3^6,'b')
    sage: b = K.gen()
    sage: a = b^210
    sage: discrete_log(a, b, K.order()-1)
    210

    sage: b = Mod(1,37);  x = Mod(2,37)
    sage: discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of 2 found to base 1
    sage: b = Mod(1,997);  x = Mod(2,997)
    sage: discrete_log(x, b)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of 2 found to base 1

    See trac\#2356:
    sage: F.<w> = GF(121)
    sage: v = w^120
    sage: v.log(w)
    0

    sage: K.<z>=CyclotomicField(230)
    sage: w=z^50
    sage: discrete_log(w,z)
    50

    An example where the order is infinite: note that we must give
    an upper bound here:
    sage: K.<a> = QuadraticField(23)
    sage: eps = 5*a-24        # a fundamental unit
    sage: eps.multiplicative_order()
    +Infinity
    sage: eta = eps^100
    sage: discrete_log(eta,eps,1000)
    100
   
    In this case we cannot detect negative powers:
    sage: eta = eps^(-3)
    sage: discrete_log(eta,eps,100)
    Traceback (most recent call last):
    ...
    ValueError: No discrete log of -11515*a - 55224 found to base 5*a - 24

    But we can invert the base (and negate the result) instead:
    sage: - discrete_log(eta^-1,eps,100)
    -3

    An additive example: elliptic curve DLOG:
    sage: F=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: F.<a>=GF(37^2,'a')
    sage: E=EllipticCurve(F,[1,1])
    sage: P=E(25*a + 16 , 15*a + 7 )
    sage: P.order()
    672
    sage: Q=39*P; Q
    (36*a + 32 : 5*a + 12 : 1)
    sage: discrete_log(Q,P,P.order(),'+')
    39

AUTHOR:
    -- William Stein and David Joyner (2005-01-05)
    -- John Cremona (2008-02-29) rewrite using dict() and make generic

Function which solves the equation a*P=m*Q or P^a=Q^m.

Additive version: returns (a,m) with minimal m>0 such that
a*P==m*Q.  Special case: if <P> and <Q> intersect only in {0} then
(a,m)=(0,Q.additive_order()).

Multiplicative version: returns (a,m) with minimal m>0 such that
P^a==Q^m.  Special case: if <P> and <Q> intersect only in {1} then
(a,m)=(0,Q.multiplicative_order()).

Works in general finite abelian groups:  uses bsgs()

EXAMPLE:

An additive example (in an elliptic curve group):
    sage: F.<a>=GF(3^6,'a')
    sage: E=EllipticCurve([a^5 + 2*a^3 + 2*a^2 + 2*a, a^4 + a^3 + 2*a + 1])
    sage: P=E(a^5 + a^4 + a^3 + a^2 + a + 2 , 0)
    sage: Q=E(2*a^3 + 2*a^2 + 2*a , a^3 + 2*a^2 + 1)
    sage: linear_relation(P,Q,'+')
    (1, 2)
    sage: P == 2*Q
    True

An multiplcative example (in a finite field's multiplicative group):
    sage: F.<a>=GF(3^6,'a')
    sage: a.multiplicative_order().factor()
    2^3 * 7 * 13
    sage: b=a^7
    sage: c=a^13
    sage: linear_relation(b,c,'*')
    (13, 7)
    sage: b^13==c^7
    True

Generic function to find order of P given a multiple of the order

    INPUT:

        P -- a Sage object which is a group element

        m -- a Sage integer which is a multiple of the order of P,
        i.e. we require that m*P=0 (or P^m=1).

        plist -- a list of the prime factors of m, or None in
        which case this function will need to factor m.

        operation -- string: '+' (default ) or
                             '*' or other.

                     If other, the following must be supplied:

                     identity: the identity element for the group;

                     inverse(): a function of one argument giving
                     the inverse of a group element;

                     op(): a function of 2 arguments defining
                     the group binary operation.
                     
    NOTE: It is more efficient for the caller to factor m and cache the
    factors for subsequent calls.

    EXAMPLES:
        sage: k.<a> = GF(5^5)
        sage: b = a^4
        sage: order_from_multiple(b,5^5-1,operation='*')
        781
        sage: E = EllipticCurve(k,[2,4])
        sage: P = E(3*a^4 + 3*a , 2*a + 1 )
        sage: M = E.cardinality(); M
        3227
        sage: plist = M.prime_factors()
        sage: order_from_multiple(P, M, plist, operation='+')
        3227
        sage: Q = E(0,2)
        sage: order_from_multiple(Q, M, plist, operation='+')
        7

        sage: K.<z>=CyclotomicField(230)
        sage: w=z^50
        sage: order_from_multiple(w,230,operation='*')
        23

Generic function to find order of P given bounds on group order.

upper and lower bounds for a multiple of the order (e.g. bounds on the
order of the group of which P is an element)

    INPUT:

        P      -- a Sage object which is a group element

        bounds -- a 2-tuple (lb,ub) such that m*P=0 (or P^m=1) for
                  some m with lb<=m<=ub

        d      -- (optional) a positive integer; only m which are
        multiples of this will be considered.

        operation -- string: '+' (default ) or
                             '*' or other.

                     If other, the following must be supplied:

                     identity: the identity element for the group;

                     inverse(): a function of one argument giving
                     the inverse of a group element;

                     op(): a function of 2 arguments defining
                     the group binary operation.
                     
                     
    NOTE: Typically lb and ub will be bounds on the group order,
    and from previous calculation we know that the group order is
    divisible by d.

    EXAMPLES:
        sage: k.<a> = GF(5^5)
        sage: b = a^4
        sage: order_from_bounds(b,(5^4,5^5),operation='*')
        781
        sage: E = EllipticCurve(k,[2,4])
        sage: P = E(3*a^4 + 3*a , 2*a + 1 )
        sage: bounds = Hasse_bounds(5^5)
        sage: Q = E(0,2)
        sage: order_from_bounds(Q, bounds, operation='+')
        7
        sage: order_from_bounds(P, bounds, 7, operation='+')
        3227

        sage: K.<z>=CyclotomicField(230)
        sage: w=z^50
        sage: order_from_bounds(w,(200,250),operation='*')
        23

Returns a group element whose order is the lcm of the given elements

INPUT:
    P1 -- a pair (g1,n1) where g1 is a group element of order n1
    P2 -- a pair (g2,n2) where g2 is a group element of order n2
    operation -- string: '+' (default ) or
                         '*' or other.

                     If other, the following must be supplied:

                     identity: the identity element for the group;

                     inverse(): a function of one argument giving
                     the inverse of a group element;

                     op(): a function of 2 arguments defining
                     the group binary operation.
                     

OUTPUT:
     A pair (g3,n3) where g3 has order n3=lcm(n1,n2)
    
EXAMPLES:
    sage: F.<a>=GF(3^6,'a')
    sage: b = a^7
    sage: c = a^13
    sage: ob = (3^6-1)//7
    sage: oc = (3^6-1)//13
    sage: merge_points((b,ob),(c,oc),operation='*')
    (a^4 + 2*a^3 + 2*a^2, 728)
    sage: d,od = merge_points((b,ob),(c,oc),operation='*')
    sage: od == d.multiplicative_order()
    True
    sage: od == lcm(ob,oc)
    True

    sage: E=EllipticCurve([a^5 + 2*a^3 + 2*a^2 + 2*a, a^4 + a^3 + 2*a + 1])
    sage: P=E(2*a^5 + 2*a^4 + a^3 + 2 , a^4 + a^3 + a^2 + 2*a + 2)
    sage: P.order()
    7
    sage: Q=E(2*a^5 + 2*a^4 + 1 , a^5 + 2*a^3 + 2*a + 2 )
    sage: Q.order()
    4
    sage: R,m = merge_points((P,7),(Q,4), operation='+')
    sage: R.order() == m
    True
    sage: m == lcm(7,4)
    True

multiplication_names

Value:

('multiplication', 'times', 'product', '*')