Ask Your Question
1

How to find source code, search_src rises Warning

asked 2022-09-29 13:16:11 +0100

dantetante gravatar image

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/inst...

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

edit retag flag offensive close merge delete

Comments

either clone the git repo and use git grep or search the source in github or gitlab : https://github.com/sagemath/sage

FrédéricC gravatar imageFrédéricC ( 2022-09-29 13:59:13 +0100 )edit
3

you can also create an object x of the appropriate type and then use x.multiplicative_order??

FrédéricC gravatar imageFrédéricC ( 2022-09-29 14:00:26 +0100 )edit

I think that x.multiplicative_order?? is the easiest way. It may not help much, though: the source code is essentially return sage.rings.integer.Integer(self.__pari__().znorder()). In other words, it's using Pari/GP (https://pari.math.u-bordeaux.fr) and their function znorder to determine the answer.

John Palmieri gravatar imageJohn Palmieri ( 2022-09-29 19:47:36 +0100 )edit

Thanks @dantetante, I did not know the command search_src('multiplicative_order') this cmd is working for me with SageMath 9.7 installed from source.

ortollj gravatar imageortollj ( 2022-09-30 07:35:03 +0100 )edit

@John: many thanks! But, how did you get to the string return sage.rings.integer.Integer(self.__pari__().znorder())? In my case, if I type x.multiplicative_order??, it sends me to /private.../structure/element.pyx, and in this .pyx file I don't find the above string which sends me to look at pari, which is, by the way, exactly what I was looking for. So this leaves only the question open why I get a warning when using multiplicative_order??, because when using x.multiplicative_order?? I don't get one ...

dantetante gravatar imagedantetante ( 2022-09-30 11:49:25 +0100 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2022-10-06 17:46:38 +0100

dan_fulea gravatar image

updated 2022-10-06 17:48:31 +0100

Let us do the search explicitly. The multiplicative_order function cited in the question, applied on some object x delegates the work to the method with the same name of the object x, if any. In our case, this is - using a sample ring -

N = 202200002022
Z = IntegerModRing(N)
x = Z(101)
print(x.multiplicative_order())

We get

5882352

and the question is why. So let us ask for

sage: ??x.multiplicative_order

with the object x being the unit above, and we get the source and the location, here truncated info:

Source:   
    def multiplicative_order(self):
        """...
        """
        try:
            return sage.rings.integer.Integer(self.__pari__().znorder())
        except PariError:
            raise ArithmeticError("multiplicative order of %s not defined since it is not a unit modulo %s"%(
                self, self.__modulus.sageInteger))
File:      /usr/lib/python3.10/site-packages/sage/rings/finite_rings/integer_mod.pyx

So the code delegates the work to pari, and effectuates basicly

sage: x.__pari__()
Mod(101, 202200002022)
sage: x.__pari__().znorder()
5882352
sage: type(_)
<class 'cypari2.gen.Gen'>

and the obtained number is converted to a specific class, so that sage can handle it in the sequel.

So the algorithm used is inside pari/gp, the corresponding call in there would be:

[dan@k9 ~]$ gp
                            GP/PARI CALCULATOR Version 2.13.4 (released)
                    amd64 running linux (x86-64/GMP-6.2.1 kernel) 64-bit version
                          compiled: Apr  5 2022, gcc version 11.2.0 (GCC)
                                     threading engine: pthread
                           (readline v8.1 enabled, extended help enabled)

                               Copyright (C) 2000-2020 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY 
WHATSOEVER.

Type ? for help, \q to quit.
Type ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000, nbthreads = 8
? x = Mod(101, 202200002022)
%1 = Mod(101, 202200002022)
? znorder(x)
%2 = 5882352
?
edit flag offensive delete link more

Comments

ok, so znorder was there but I didn't see it ;-) what I did then: clone the pari folder from github, grep for string znorder, look for a c-file in the list that grep foud, this was in ./src/basemath/arith1.c, opened this file and searched for >>znorder<< and found this:

    GEN
    znorder(GEN x, GEN o)
    {
      pari_sp av = avma;
      GEN b, a;

   ...
      {
        GEN fa = Z_factor(b), P = gel(fa,1), E = gel(fa,2);
       ...

so it seems that -- without going into looking what >>gel<< is -- znorder is based on factoring; what I also found is this interesting link https://math.stackexchange.com/questi... where in the cited Exercise 11.4 (Shoup) my main question is answered: There's no fast algo for computing orders!

dantetante gravatar imagedantetante ( 2022-10-08 13:53:14 +0100 )edit

For those also interested in following this question: Shoup is available here https://shoup.net/ntb/ an the paper of Wang (I searched quite some time) is available here: https://epdf.tips/selected-papers-of-...

dantetante gravatar imagedantetante ( 2022-10-08 13:59:45 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-09-29 13:16:11 +0100

Seen: 52 times

Last updated: Oct 06