(F::FqFiniteField)(coeffs::Array{T,1}) where {T<:Union{Integer,fmpz}} = begin
    g = gen(F)
    x = zero(F)
    for (i, c) in enumerate(coeffs)
        x += c * g^(i-1)
    end
    x
end

(F::FqNmodFiniteField)(coeffs::Array{T,1}) where {T<:Union{Integer,fmpz}} = begin
    g = gen(F)
    x = zero(F)
    for (i, c) in enumerate(coeffs)
        x += c * g^(i-1)
    end
    x
end

sqrt(a::FinFieldElem) = root(a, 2)

# http://trac.sagemath.org/ticket/7931
# http://sagenb.org/src/rings/finite_rings/element_base.pyx
root(a::FinFieldElem, n::Integer) = root(a, fmpz(n))
root(a::FinFieldElem, n::fmpz) = begin
    if iszero(a)
        n <= 0 && throw(DomainError())
        return a
    end

    K = parent(a)
    q = order(K)

    if n < 0
        a = inv(a)
        n = -n
    elseif n == 0
        a == 1 || throw(DomainError())
        return a
    end

    if isone(a)
        GCD = gcd(n, q-1)
        GCD == 1 && return a

        g = gen(K) # TODO: The generator is guaranteed to be a multiplicative generator only if the field is generated by a Conway polynomial.
        q1overn = (q-1) ÷ GCD
        nthroot = g^q1overn
        return nthroot
    end

    m = n % (q-1)
    m == 0 && error("$(a) has no $(n)th root in $(K)")

    # GCD = α*m + β*(q-1), so 1/m = α/GCD (mod q-1)
    GCD, α, β = gcdx(m, q-1)
    GCD == 1 && return a^α

    m = GCD
    q1overn = (q-1) ÷ m
    a^q1overn != 1 && error("$(a) has no $(n)th root in $(K)")

    b = a^α
    F = [(fmpz(p), e) for (p, e) in factor(BigInt(m))]

    g = gen(K) # TODO: The generator is guaranteed to be a multiplicative generator only if the field is generated by a Conway polynomial.
    for (r, v) in F
        k, h = remove(q-1, r)
        z = h * invmod(-h, r^v)::typeof(h)
        x = (1 + z) ÷ (r^v)
        if k == 1
            b = b^x
        else
            t = log(b^h, g^(r^v * h), r^(k-v))
            b = b^x * g^(-z*t)
        end
    end
    b
end

sqrts(a::FinFieldElem) = roots(a, 2)

# http://trac.sagemath.org/ticket/7931
# http://sagenb.org/src/rings/finite_rings/element_base.pyx
roots(a::FinFieldElem, n::Integer) = roots(a, fmpz(n))
roots(a::T, n::fmpz) where {T<:FinFieldElem} = begin
    if iszero(a)
        n <= 0 && throw(DomainError())
        return [a]
    end

    K = parent(a)
    q = order(K)

    if n < 0
        a = inv(a)
        n = -n
    elseif n == 0
        a == 1 || throw(DomainError())
        e = elements(K)
        e[e .!= 0]
    end

    if isone(a)
        GCD = gcd(n, q-1)
        GCD == 1 && return [a]

        g = gen(K) # TODO: The generator is guaranteed to be a multiplicative generator only if the field is generated by a Conway polynomial.
        q1overn = (q-1) ÷ GCD
        nthroot = g^q1overn
        return [nthroot^i for i in 0:(GCD-1)]
    end

    m = n % (q-1)
    m == 0 && return T[]

    # GCD = α*m + β*(q-1), so 1/m = α/GCD (mod q-1)
    GCD, α, β = gcdx(m, q-1)
    GCD == 1 && return [a^α]

    m = GCD
    q1overn = (q-1) ÷ m
    a^q1overn != 1 && return T[]

    b = a^α
    F = [(fmpz(p), e) for (p, e) in factor(BigInt(m))]

    g = gen(K) # TODO: The generator is guaranteed to be a multiplicative generator only if the field is generated by a Conway polynomial.
    for (r, v) in F
        k, h = remove(q-1, r)
        z = h * invmod(-h, r^v)::typeof(h)
        x = (1 + z) ÷ (r^v)
        if k == 1
            b = b^x
        else
            t = log(b^h, g^(r^v * h), r^(k-v))
            b = b^x * g^(-z*t)
        end
    end

    nthroot = g^q1overn
    L = [b]
    for _ in 1:(m-1)
        b *= nthroot
        push!(L, b)
    end
    L
end

elements(F::Union{FqFiniteField,FqNmodFiniteField}) = begin
    p = characteristic(F)
    k = degree(F)

    e = typeof(zero(F))[]
    @forcartesian c [p for _ in 1:k] begin
        push!(e, F(c .- 1))
    end
    e
end

rand(F::Union{FqFiniteField,FqNmodFiniteField}) = begin
    p = characteristic(F)
    k = degree(F)

    F([rand(0:(p-1)) for _ in 1:k])
end
