{{{id=1|
def euclidean_division(a,b):
    q_star=a/b
    q=Re_q+i*Im_q
    r=a-q*b
    return q,r
///
}}}

{{{id=2|
def euclidean_division_Zi(a,b):
    Qi=(a+b).parent()
    i=Qi.gen()
    q_star=a/b
    Re_q_star,Im_q_star=q_star.list()
    ....
    r=a-q*b
    return q,r
///
}}}

{{{id=3|
def gcd(a,b):
    while b != 0:
        q,r=euclidean_division(a,b)
        a,b=b,r
    return a
///
}}}

{{{id=4|
def gcd_Zi(a,b):
    ....
    return a
///
}}}

{{{id=5|
def valuation(a,pi):
    val=0
    a,r=euclidean_division(a,pi)
    while r == 0:
        val+=1
        a,r=euclidean_division(a,pi)
    return val 
///
}}}

{{{id=6|
def valuation_Zi(a,pi):
    ....
    return val 
///
}}}

{{{id=7|
def solve_a2_equal_m1(p):
    if p % 4 != 1:
        raise ValueError
    g=2
    while mod(g,p).multiplicative_order() != p-1:
        g=next_prime(g)
    g=mod(g,p)
    ....
    # a^2 +1 is a multiple of p
    return a
///
}}}

{{{id=8|
def prime_factors_of_prime(p):
    if p == 2:
        return [1+i]
    elif p % 4 == 3:
        return [p]
    else:
        a=solve_a2_equal_m1(p)
        pi=gcd_Zi(...)
        return [pi,p/pi]
///
}}}

{{{id=9|
def factor(a,prime_factors_a):
    fact=[]
    for q in prime_factors_a:
        val=valuation(a,q)
        if val != 0:
            fact.append([q,valuation(a,q)])
    return fact 
///
}}}

{{{id=10|
def factor_Zi(a,factorization_of_norm):
    fact=[]
    for qe in factorization_of_norm:
        q,e=qe
        ....        
    return fact 
///
}}}

{{{id=11|
Qx.<x>=QQ['x']
Qi.<i>=NumberField(x^2+1)
euclidean_division_Zi(10+30*i,1+3*i)
valuation_Zi(2,1+i)
solve_a2_equal_m1(13)
gcd_Zi(13,8+i)
prime_factors_of_prime(13)
factor_Zi(6*i+34,factor((6*i+34).norm()))
(1+i)^3*(10-7*i)*i^3
///
}}}