search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

m-th power residue symbol #10464

Closed katestange closed 13 years ago

katestange commented 13 years ago

implement m-th power residue symbol (generalising Legendre/Kronecker symbol)

Apply only attachment: trac_10464_residue_symbol.4.patch to the Sage library.

CC: @katestange

Component: number fields

Keywords: cubic residue

Author: Katherine Stange

Reviewer: Francis Clarke, David Loeffler

Merged: sage-4.7.2.alpha3

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

katestange commented 13 years ago
comment:1

Attachment: trac_10464_residue_symbol.patch.gz

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago
comment:3

I like the look of this, but the formatting of the docstrings isn't quite right -- the text "Quadratic Residue (7 is not a square modulo 11)" shouldn't be inside the code block. You should remove the double colon after EXAMPLES, unindent the description lines and put a double colon at the end of each one. Other than that very trivial fix this looks absolutely fine.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Work Issues: docstring formatting

5ef57b06-33a8-4a32-80d2-0f5ab07e80d9 commented 13 years ago
comment:4

I think there are a couple of things which will make the ideal residue_symbol function a little faster:

  1. There should be no need to have the default check=True when recursively applying the function to the prime factors of the ideal since all the checks will have already been performed.
  2. The final loop can be avoided by calculating a discrete log in the residue field.

Thus I think the last few lines of the definition should read something like:

        if not self.is_prime():
            return prod(Q.residue_symbol(e, m, check=False)**i for Q, i in self.factor())
        k = self.residue_field()
        r = k(e)**((k.order() - 1)/m)
        resroot = primroot**(rootorder/m)
        from sage.groups.generic import discrete_log
        j = discrete_log(k(resroot), k(r), ord=m)
        return resroot**j

One other little thing. I think it is safer to write self.smallest_integer() rather than ZZ(self.gens()[0]).

katestange commented 13 years ago
comment:5

Attachment: trac_10464_residue_symbol.2.patch.gz

Thanks all for the comments and suggestions; they were very helpful. I've uploaded a new version of the patch that has taken into account all of them. (I couldn't figure out how to replace the file with one of the same name as suggested in the development walkthrough guide.)

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago
comment:6

There is something messed up with this patch: each new method is defined twice over.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Changed work issues from docstring formatting to patch corrupted?

katestange commented 13 years ago

Attachment: trac_10464_residue_symbol.3.patch.gz

katestange commented 13 years ago
comment:7

Sorry! I must have cloned the wrong branch at some point, but I should have noticed in the diff -- newbie mistake. Anyway, it's now been fixed. (I also see now how to replace the old patch, but at this point I think that would be more confusing, so this is labelled '3'.)

5ef57b06-33a8-4a32-80d2-0f5ab07e80d9 commented 13 years ago
comment:8

It's all fine now. I'd give it a positive review but for one thing. The docstring for sage.rings.number_field.number_field_element.NumberFieldElement.residue_symbol says 

        - ``P`` - proper ideal of the number field (or an extension)

I think that there needs to be a doctest illustrating the case where P is an ideal in an extension.

katestange commented 13 years ago

Attachment: trac_10464_residue_symbol.4.patch.gz

katestange commented 13 years ago
comment:9

Thanks for pointing that out. I've fleshed out the documentation somewhat, and in the process found a small bug which has been fixed (the faster routine kronecker_symbol was called on some inappropriate cases).

5ef57b06-33a8-4a32-80d2-0f5ab07e80d9 commented 13 years ago
comment:10

All looks good now. Positive review.

5ef57b06-33a8-4a32-80d2-0f5ab07e80d9 commented 13 years ago

Changed work issues from patch corrupted? to none

5ef57b06-33a8-4a32-80d2-0f5ab07e80d9 commented 13 years ago

Reviewer: Francis Clarke

83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago
comment:11

Please put into the ticket's description which patches to apply [in which order, i.e., in the order they should be applied, and perhaps to which repository].

(The trac wiki syntax for referring to attached files is [attachment: here_comes_the_filename](https://github.com/sagemath/sage/files/ticket10464/here_comes_the_filename.gz), hence in this case [attachment: trac_10464_residue_symbol.4.patch](https://github.com/sagemath/sage-prod/files/10651605/trac_10464_residue_symbol.4.patch.gz).)

Also, using the comment field of attachments isn't bad.

83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago

Changed reviewer from Francis Clarke to Francis Clarke, David Loeffler

83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago

Description changed:

--- 
+++ 
@@ -1 +1,6 @@
 implement m-th power residue symbol (generalising Legendre/Kronecker symbol)
+
+---
+
+Apply only [attachment: trac_10464_residue_symbol.4.patch](https://github.com/sagemath/sage-prod/files/10651605/trac_10464_residue_symbol.4.patch.gz) to the Sage library.
+
83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago

Merged: sage-4.7.2.alpha3