"""
This sage script implements Algorithm 2. It is a fast algorithm to compute a unit in a cyclic cubic field K, which allows in some cases to certify rapidly that the p-adic regulator of K is not divisible by p.
"""

"""
This function takes as parameter a polynomial f whose number field K is cyclic cubic. The output is a unit u, which is not necesserily of infinite order. If ord(u) is infinite and p is a prime which doesn't divide the p-adic regulator of K, then u is used to rapidly certify it.   
"""
def fast_units(f):
    K.<a>=NumberField(f)
    OK=K.ring_of_integers()
    m=K.disc().sqrt()    # m is the conductor of K because it is cyclic cubic 
    # the following 5 lines compute gm, an ideal such that gm^3=(m)
    gm=OK     
    for p in m.prime_factors():
       pfact=(p*OK).factor() 
       gp=prod([pe[0]^(pe[1]//3) for pe in pfact]) 
       #                 # gp prime ideal such that gp^3=(p) 
       gm=gm*gp
    if not gm.is_principal(): # is_principal uses LLL and \
                              # is not certified to find a generator\
                              #  even if gm is principal
        return K(1),K(1)
    omega=gm.gens_reduced()[0] # (omega)=gm 
    sigma=K.automorphisms()[1] # sigma is a non-trivial automorphism of K
    eps=sigma(omega)/omega     # a unit of K, according to Remmark 3.10
    return eps,sigma(eps)