Revision history [back]

I want to investigate how sage is computing the multiplicative order of a unit in Z_n. I tried multiplicative_order?? at the sage command line, which gives:

def multiplicative_order(x):
    r"""
    Return the multiplicative order of ``x``, if ``x`` is a unit, or
    raise ``ArithmeticError`` otherwise.

    EXAMPLES::

        sage: a = mod(5,11)
        sage: multiplicative_order(a)
        5
        sage: multiplicative_order(mod(2,11))
        10
        sage: multiplicative_order(mod(2,12))
        Traceback (most recent call last):
        ...
        ArithmeticError: multiplicative order of 2 not defined since it is not a unit modulo 12
    """
    return x.multiplicative_order()
File:      /private/var/tmp/sage-9.6-current/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage/misc/functional.py
Type:      function

but this is not very helpful, since I don't know where to look for x.multiplicative_order() which is returned. I also found that this should be helpful:

sage: search_src('multiplicative_order')

But this raises a warning:

Warning: the Sage documentation is not available

Can anyone give me a hint what I can do? My system is macOS 12.4 and Sagemath 9.6, the >>no development<< version from the 3-manifolds project as linked here: https://doc.sagemath.org/html/en/installation/index.html

And, by the way, what I am _really_ interested in is: what is the fastest algorithm for computing the order of a unit in Z_n. I guess, if the factorisation of n is not known, there is no fast way, only the naive? But I even didn't find actual literature going into this. There are a lot of articles/books about how it is done if phi(n) is known. But what if it is not? What complexity has this problem? I thought that looking at the actual sagemath source code could help ;-)