Overflow error in `set_random_seed(1);a=(Integers(13)(2))**randint(2,2**4000-1)`

[Georgi Guninski]

```
set_random_seed(1);a=(Integers(13)(2))**randint(2,2**4000-1)

OverflowError Traceback (most recent call last)
OverflowError: Python int too large to convert to C long

The above exception was the direct cause of the following exception:

SystemError
```

I think the result should be computed correctly in time O(4000) via
fast doubling without knowledge of the factorization.

pari/gp computes it fast.

[Dima Pasechnik]

Integers(13)(2) is 2 mod 13. Computing Integers(13)(2)**r starts by
computing r % 12 - much faster than doubling alone (after such a reduction one
can do doubling, as is done by GMP, used in the implementation).
And that's how it's implemented in Sage, too.

The error you see is different - it's due to an incorrect conversion
attempt in __pow__()
in rings/finite_rings/integer_mod.pyx

this works:
sage: set_random_seed(1);a=(Integers(13)(2))**(randint(2,2**4000-1) % 12); a
4

Thanks for the report. I've opened
https://github.com/sagemath/sage/issues/36080

[Georgi Guninski]

hi Dima, I am familiar with reduction modulo Euler totient,
but it could be expensive to compute and in addition my testcase
omits it on purpose :)
btw, in the github issue the link to google groups appears
broken.

[Georgi Guninski]

btw, why this code works?

sage: a=Integers(13)(2);X=2**14000-19;a**X==a**(X%12)
True

[Dima Pasechnik]

cause X has a different type here, so it does not hit the buggy line.


>
> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8UUVh1%2BsJLXt62HufSq4ZqyqRNKE7YyYhr05-1Qk_fPQ%40mail.gmail.com.