_nth_root_naive fails for integer mod

[kliem]

sage -t --long --random-seed=3 src/sage/rings/finite_rings/integer_mod.pyx
**********************************************************************
File "src/sage/rings/finite_rings/integer_mod.pyx", line 1525, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract._nth_root_naive
Failed example:
    for n in range(2,100): # long time
        K = Integers(n)
        elist = list(range(1,min(2*n+2,100)))
        for e in random_sublist(elist, 5/len(elist)):
            for a in random_sublist(range(1,n), min((n+2)//2,10)/(n-1)):
                b = K(a)
                try:
                    L = b.nth_root(e, all=True)
                    if L:
                        c = b.nth_root(e)
                except Exception:
                    L = [-1]
                M = b._nth_root_naive(e)
                if sorted(L) != M:
                    print("mod(%s, %s).nth_root(%s,all=True), mod(%s, %s)._nth_root_naive(%s)" % (a,n,e,a,n,e))
                if L and (c not in L):
                    print("mod(%s, %s).nth_root(%s), mod(%s, %s).nth_root(%s,all=True)" % (a,n,e,a,n,e))
Expected nothing
Got:
    mod(43, 75).nth_root(75), mod(43, 75).nth_root(75,all=True)

Component: algebra

Keywords: ring, mod, root

Author: Dave Morris

Branch/Commit: 226fe84

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32084

[DaveWitteMorris]

comment:1

The problem seems to be that mod(a, n).nth_root(k) sometimes returns a value that is not actually a kth root of mod(a, n):

sage: for n in range(100):
....:     for k in range(2*n):
....:         kth_powers = set(x^k % n for x in range(n))
....:         bad = set( (a, mod(a, n).nth_root(k), mod(a, n).nth_root(k)^k) for a in kth_powers
....:             if mod(a, n).nth_root(k)^k % n != a)
....:         if bad:
....:             print(n, k, bad)
50 50 {(49, 49, 1), (24, 24, 26)}
50 75 {(7, 7, 43), (43, 43, 7), (32, 32, 18), (18, 18, 32)}
75 50 {(49, 74, 1), (24, 24, 51)}
75 75 {(7, 7, 43), (18, 18, 57), (68, 68, 32), (57, 57, 18), (32, 32, 68), (43, 43, 7)}
98 98 {(79, 79, 67), (30, 30, 18), (67, 67, 79), (18, 18, 30)}

In the above examples, the erroneous kth root of a is always a itself, but there are larger examples where this is not the case. For example:

sage: n = 147
sage: a = 67
sage: k = 98
sage: mod(a, n).nth_root(k)
116
sage: (116^k) % n
79

[DaveWitteMorris]

Branch: public/32084

[DaveWitteMorris]

comment:3

When n is a prime power, mod(a,n).nth_root(k) returned self in certain cases where self happened to be a (p - 1)th root of unity, but it needs to return a kth root of self. This PR should fix the problem.

---

New commits:

e593b0a

trac 32084 fix nth root

[DaveWitteMorris]

Commit: e593b0a

[DaveWitteMorris]

Author: Dave Morris

[kliem]

Work Issues: #29979 -- rebase one ticket on the other (#29979 marks this as a bug)

[DaveWitteMorris]

Changed branch from public/32084 to public/32084r1

[DaveWitteMorris]

Changed work issues from #29979 -- rebase one ticket on the other (#29979 marks this as a bug) to none

[DaveWitteMorris]

Changed commit from e593b0a to 6158236

[DaveWitteMorris]

Dependencies: #29979

[DaveWitteMorris]

comment:6

Rebased on #29979, and removed "known bug" tag. Only the last 2 commits are from this ticket ('trac 32084 fix nth root' and 'remove "known bug" tag').

---

New commits:

a03aebb	make some files of rings fuzz ready
e92d0a6	some changes to make rings fuzz ready
8d93480	make rings ready for fuzzed doctests
f008269	add ticket numbers to `not tested`
540413e	fix various remaining doctests in rings
2a3eebb	a few more doctests
5c027a7	get a random nonzero element
bf9dee1	trac 32084 fix nth root
6158236	remove "known bug" tag

[kliem]

comment:7

The first value in the line above is quasi K(modp.lift(), but here we pick K(modp). Why?

[sagetrac-git]

Changed commit from 6158236 to 779691a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

779691a

use explicit lift()

[DaveWitteMorris]

comment:9

Thanks for the comment. Using lift() may be a bit safer, because we know exactly what K(modp.lift()) will do (lift modp to an integer, and then pass to Z/(p^k Z) in the obvious way), but it may not be so obvious what the constructor K(modp) will do. So I made the change. We are in the situation where every lift of modp to an element of Z/(p^k Z) is an nth root, so it does not matter how we get the lift.

[tscrim]

comment:10

Can we reverse the dependency with #29979? I think this has a much higher chance of getting reviewed first.

[kliem]

comment:11

The work issue was really meant as a note that one of the tickets needs to be rebased. I think the order should be whichever ticket is ready to be merged first.

Btw, it would be great to add one of the failing examples as a doctest.

[DaveWitteMorris]

Changed commit from 779691a to e593b0a

[DaveWitteMorris]

New commits:

e593b0a

trac 32084 fix nth root

[DaveWitteMorris]

Work Issues: #29979 -- rebase one ticket on the other (#29979 marks this as a bug)

[DaveWitteMorris]

Changed branch from public/32084r1 to public/32084

[DaveWitteMorris]

Changed branch from public/32084 to public/32084r2

[DaveWitteMorris]

Changed commit from e593b0a to 226fe84

[DaveWitteMorris]

comment:14

Sorry for the confusion. I think I put this back the way it was (including the work issue), except that I rebased on 9.4b4 and added a doctest.

---

New commits:

0994f0f	trac 32084 fix nth root
226fe84	trac 32084 fix nth root

[DaveWitteMorris]

Changed dependencies from #29979 to none

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:16

Thank you. LGTM.

[tscrim]

Changed work issues from #29979 -- rebase one ticket on the other (#29979 marks this as a bug) to none

[DaveWitteMorris]

comment:17

Thanks!

[kliem]

comment:18

I moved the work issue now to #29979. (I hoped that this is what a reviewer would do when setting it on positive review, I caught on to this so things are fine.)

[tscrim]

comment:19

Replying to @kliem:

I moved the work issue now to #29979. (I hoped that this is what a reviewer would do when setting it on positive review, I caught on to this so things are fine.)

Sorry, I should have done that.

[vbraun]

Changed branch from public/32084r2 to 226fe84