Opened 11 years ago

Closed 10 years ago

#10464 closed enhancement (fixed)

m-th power residue symbol

Reported by: katestange Owned by: davidloeffler
Priority: minor Milestone: sage-4.7.2
Component: number fields Keywords: cubic residue
Cc: katestange Merged in: sage-4.7.2.alpha3
Authors: Katherine Stange Reviewers: Francis Clarke, David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by leif)

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


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

Attachments (4)

trac_10464_residue_symbol.patch (5.0 KB) - added by katestange 11 years ago.
trac_10464_residue_symbol.2.patch (8.5 KB) - added by katestange 10 years ago.
trac_10464_residue_symbol.3.patch (4.8 KB) - added by katestange 10 years ago.
trac_10464_residue_symbol.4.patch (6.4 KB) - added by katestange 10 years ago.

Download all attachments as: .zip

Change History (16)

Changed 11 years ago by katestange

comment:1 Changed 11 years ago by katestange

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by katestange

  • Cc katestange added

comment:3 Changed 11 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to docstring formatting

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.

comment:4 Changed 11 years ago by fwclarke

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]).

Changed 10 years ago by katestange

comment:5 Changed 10 years ago by katestange

  • Status changed from needs_work to needs_review

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

comment:6 Changed 10 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues changed from docstring formatting to patch corrupted?

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

Changed 10 years ago by katestange

comment:7 Changed 10 years ago by katestange

  • Status changed from needs_work to needs_review

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'.)

comment:8 Changed 10 years ago by fwclarke

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.

Changed 10 years ago by katestange

comment:9 Changed 10 years ago by katestange

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

comment:10 Changed 10 years ago by fwclarke

  • Reviewers set to Francis Clarke
  • Status changed from needs_review to positive_review
  • Work issues patch corrupted? deleted

All looks good now. Positive review.

comment:11 Changed 10 years ago by leif

  • Description modified (diff)
  • Reviewers changed from Francis Clarke to Francis Clarke, David Loeffler

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], hence in this case [attachment:trac_10464_residue_symbol.4.patch].)

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

comment:12 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.