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 ;-)