Improve efficiency of multiplicative_order() for number field elements

[JohnCremona]

The attached patch vastly improves the efficiency of the multiplicative_order() function for number field elements. Before, this example:

 sage: x = polygen(QQ)
            sage: K.<a>=NumberField(x^40 - x^20 + 4)
            sage: u = 1/4*a^30 + 1/4*a^10 + 1/2
            sage: u.multiplicative_order()
            6
            sage: a.multiplicative_order()
            +Infinity

would have required raising a to the power 2**40 (I'm serious). Now it just works (fast).

Component: number theory

Keywords: number field multiplicative order

Issue created by migration from https://trac.sagemath.org/ticket/5518

[JohnCremona]

comment:1

Attachment: multiplicative_order.patch.gz

[sagetrac-fwclarke]

comment:2

This is excellent. A great speed up, and it gives the right answer!

I would suggest adding the doctest

sage: K.<a, b> = NumberField([x^2 + x + 1, x^2 - 3])
sage: z = (a - 1)*b/3
sage: z.multiplicative_order()
12

because sage-3.4 says the order is +infinity.

[JohnCremona]

comment:3

Attachment: trac_5518.patch.gz

I added a small patch with the additional doctest as suggested.

[sagetrac-mabshoff]

comment:4

Merged both patches in Sage 3.4.1.alpha0.

Cheers,

Michael