relevant method name for Zmod(n)(p/q).lift()

[Vincent Delecroix]

Hello,

In #21745 the behavior of (p/q) % n is proposed for a change. However
the current behavior (that is looking at the operation p * q^-1 modulo
n) is something useful that we want to keep. I would like to add a
method to rational numbers with this behavior, in other words
something equivalent to

def my_method(self, n):
return (self.numerator() * self.denominator().inverse_mod(n)) % n

or

def my_method_bis(self, n):
return Zmod(n)(self).lift()

Of course it is possible to optimize the implementation but I am
currently looking for a relevant name. Any suggestion?

Cheers,
Vincent

[John Cremona]

I see that despite the title of that ticket, this is (at present)
about r%n when r =p/q is rational.

Questions:

1. What is the proposed behaviour when q is not invertible modulo n?
Or more generally, if q*x=p (mod n) has no solutions, or more than
one solution (mod n)?

2. Is the output going to be an element of Z/nZ, or of Z (as your
sample code suggests)?

John

On 23 October 2016 at 15:14, Vincent Delecroix

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[vdelecroix]

Le dimanche 23 octobre 2016 16:20:25 UTC+2, John Cremona a écrit :

I see that despite the title of that ticket, this is (at present)
about r%n when r =p/q is rational.

The ticket also cares about the case where n is rational. Moreover my proposed branch makes % part of the coercion system (when one of the argument is rational). So standard coercion rules apply.

However, concerning this thread, my question is about r%n with r=p/q being rational.

Questions:

1. What is the proposed behaviour when q is not invertible modulo n?
Or more generally, if  q*x=p (mod n) has no solutions, or more than
one solution (mod n)?

The very same behavior as with the two implementation I proposed. In other words, raise the same errors as inverse_mod does when it complains.

Concerning the non-uniqueness, it is just a matter of having an extra argument to inverse_mod on integers and using it here. Do you think it might be useful?
 

2. Is the output going to be an element of Z/nZ, or of Z (as your
sample code suggests)?

I was thinking about Z since for Z/nZ the direct conversion just works Zmod(n)(r).

Vincent

[John Cremona]

On 23 October 2016 at 15:28, vdelecroix <20100.d...@gmail.com> wrote:
> Le dimanche 23 octobre 2016 16:20:25 UTC+2, John Cremona a écrit :
>>
>> I see that despite the title of that ticket, this is (at present)
>> about r%n when r =p/q is rational.
>
>
> The ticket also cares about the case where n is rational. Moreover my
> proposed branch makes % part of the coercion system (when one of the
> argument is rational). So standard coercion rules apply.

OK

>
> However, concerning this thread, my question is about r%n with r=p/q being
> rational.
>
>> Questions:
>>
>> 1. What is the proposed behaviour when q is not invertible modulo n?
>> Or more generally, if q*x=p (mod n) has no solutions, or more than
>> one solution (mod n)?
>
>
> The very same behavior as with the two implementation I proposed. In other
> words, raise the same errors as inverse_mod does when it complains.

OK and this should be documented somehow, though I'm not sure how to
document the behaviour of operators.

>
> Concerning the non-uniqueness, it is just a matter of having an extra
> argument to inverse_mod on integers and using it here. Do you think it might
> be useful?

No, anyone wanting all solutions would be able to get them a different way.

>
>>
>> 2. Is the output going to be an element of Z/nZ, or of Z (as your
>> sample code suggests)?
>
>
> I was thinking about Z since for Z/nZ the direct conversion just works
> Zmod(n)(r).

That's reasonable, and what people would expect with an operator such as %.

thanks for the answers. As for you question, do we need a name to
shadow the operator %? If we do, then "mod"?

[Vincent Delecroix]

I thought about it. The main problem is that `mod` already contains
specification and implementation at the level of commutative rings and
fields

Return a representative for ``self`` modulo the ideal I (or the
ideal generated by the elements of I if I is not an ideal.)

And we have

sage: (2/3).mod(5)
0
sage: (1/2).mod(2)
0

which is true, meaningless and incompatible with what I want...

Vincent

[Vincent Delecroix]

John, there seems to be a confusion in your answer.

The current behavior of (p/q) % n is to return Zmod(n)(p/q).lift(). We
want to change it to be something else as proposed in [1], [2] and
[3]. What I want is to preserve a way of doing efficiently the old
behavior...

[1] https://groups.google.com/forum/#!topic/sage-devel/PfMop0nyiL0
[2] https://trac.sagemath.org/ticket/21745
[3] https://trac.sagemath.org/ticket/15260

[Vincent Delecroix]

PARI/GP is using Mod the way we want it

? Mod(2/3,5)
%1 = Mod(4, 5)
? Mod(2/3,6)
*** Mod: impossible inverse in Fl_inv: Mod(3, 6).

And Maple as well

> 2/3 mod 5;
4
> 2/3 mod 6;
Error, the modular inverse does not exist

This is a good reason to change the behavior of mod in Sage...

[Vincent Delecroix]

On 23 October 2016 at 18:06, Vincent Delecroix

and we have mod_ui in Sage

sage: (2/3).mod_ui(5)
4
sage: (2/3).mod_ui(6)
Traceback (most recent call last):
...
ArithmeticError: The inverse of 3 modulo 6 is not defined.

(that of course overflow when its argument is too large)

I opened #21748 for doing that.

[John Cremona]

On 23 October 2016 at 16:45, Vincent Delecroix

<20100.d...@gmail.com> wrote:
> John, there seems to be a confusion in your answer.

Right -- thanks for clarifying. The current behaviour is what I would
expect when coercing (or at least converting) into Zmod(n) but we are
implementing something else for r%n to be consistent to what people
expect when r is real. OK.

One solution is surely to not have another method on QQ at all, but
let users use the existing Zmod(n)(r) and lift if they need an element
of ZZ?

>
> The current behavior of (p/q) % n is to return Zmod(n)(p/q).lift(). We
> want to change it to be something else as proposed in [1], [2] and
> [3]. What I want is to preserve a way of doing efficiently the old
> behavior...
>
> [1] https://groups.google.com/forum/#!topic/sage-devel/PfMop0nyiL0
> [2] https://trac.sagemath.org/ticket/21745
> [3] https://trac.sagemath.org/ticket/15260
>

[Vincent Delecroix]

On 23 October 2016 at 18:13, John Cremona <john.c...@gmail.com> wrote:

> On 23 October 2016 at 16:45, Vincent Delecroix
> <20100.d...@gmail.com> wrote:
>> John, there seems to be a confusion in your answer.
>
> Right -- thanks for clarifying. The current behaviour is what I would
> expect when coercing (or at least converting) into Zmod(n) but we are
> implementing something else for r%n to be consistent to what people
> expect when r is real. OK.

Yes. This is the point. Sage started to fork Python behaviour when
implementing the operator %. We want to reverse it for compatibility
and consistency.

Note that Sage behavior is also wrong with respect to the tilde ~.
Sage uses it as unary inverse but in Python it stands for
bitcomplement. Jeroen opened a thread about that some months ago.

> One solution is surely to not have another method on QQ at all, but
> let users use the existing Zmod(n)(r) and lift if they need an element
> of ZZ?

That is indeed a solution! But I find it not very user friendly and
bad from the point of view of performance. Moreover, to implement
correctly the conversion Zmod(n)(r) in #21745 I had to copy a lot of
times the same line

((r.numerator() % n) * (r.denominator().inverse_mod(r))) % n

I wanted to get rid of it by having a proper method on rationals.