Opened 9 years ago

Closed 9 years ago

#11138 closed enhancement (fixed)

Make Jacobi symbol

Reported by: kcrisman Owned by: was
Priority: minor Milestone: sage-4.7.1
Component: number theory Keywords: beginner
Cc: Merged in: sage-4.7.1.alpha4
Authors: Taylor Dupuy Reviewers: François Bissey, Karl-Dieter Crisman
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

We have Kronecker symbol and Legendre symbol, but not Jacobi symbol. It is a method for integers, I think, but not a global one. It would be nice to have, at the very least for pedagogical purposes so that one doesn't have to explain why it's called Kronecker but we haven't introduced that... anyway, this would require a little checking for appropriate input, but otherwise should be easy to make jacobi_symbol.


Apply only 11138_rebased.patch

Attachments (6)

trac11138.patch (1.1 KB) - added by tdupu 9 years ago.
a jacobi symbol function for sage/rings/arith.py
trac11138.2.patch (1.1 KB) - added by tdupu 9 years ago.
trac11138.3.patch (1.3 KB) - added by tdupu 9 years ago.
trac11138.4.patch (1.3 KB) - added by tdupu 9 years ago.
trac11138.4-with-commit-message.patch (1.5 KB) - added by kcrisman 9 years ago.
11138_rebased.patch (1.6 KB) - added by jdemeyer 9 years ago.
Patch rebased to sage-4.7.1.alpha3

Download all attachments as: .zip

Change History (18)

Changed 9 years ago by tdupu

a jacobi symbol function for sage/rings/arith.py

comment:1 follow-up: Changed 9 years ago by tdupu

There is a test class that is not passing (10|777)==-1 (if I'm reading the errors right). I'm not sure what is wrong because when I make the same program in a notebook it seems to work. This is my first patch.

comment:2 in reply to: ↑ 1 Changed 9 years ago by fbissey

Replying to tdupu:

There is a test class that is not passing (10|777)==-1 (if I'm reading the errors right). I'm not sure what is wrong because when I make the same program in a notebook it seems to work. This is my first patch.

Could you paste the exact output? Another thing: it would be good if your input matched your documentation. Your function takes a and b and the documentation talks about x and n.

comment:3 Changed 9 years ago by kcrisman

  • Authors set to Taylor Dupuy
  • Reviewers set to François Bissey, Karl-Dieter Crisman
  • Status changed from new to needs_work

Thanks for your efforts, Taylor!

There are some things that should be done for this patch to pass muster.

  • You definitely need more doctests. There are lots of models in this same file as models. I would use the model of legendre_symbol, since it tests for catching illegal input.
  • Your formatting is off. Check the docs for kronecker_symbol to see 'exactly' how things like examples and input should be formatted.
  • I'm not sure why you don't just pass to kronecker_symbol, which is optimized, after catching the invalid input.
  • Math should be in single ticks.
    n = p1^e1 * ... * pr^er then (a|n) = (a|p1)^e1 ... (a|pr)^er where (a|pj)
    
    versus
    `n = p1^e1 * ... * pr^er` then `(a|n) = (a|p1)^e1 ... (a|pr)^er` where `(a|pj)`
    
    for the formatting in documentation. You may also need to do p_1^{e_1} in order for it to look right - try ./sage -docbuild reference html to see what happens.

Again, thanks for helping make Sage even better!

Changed 9 years ago by tdupu

comment:4 Changed 9 years ago by tdupu

Here is the copy and paste requested

        sage: l=factor(777)
        sage: prod([legendre_symbol(10,l[i][0])^(l[i][1]) for i in range(len(l))])
        -1

when I run jacobi_symbol(10,777) it returns zero:

sage: jacobi_symbol(10,777)
0

Let me know if my formatting isn't correct. I didn't change to the Kronecker Symbol.

comment:5 Changed 9 years ago by kcrisman

        INPUT: 

should be

    INPUT: 

I think. You'll also want to make sure the description looks more like

The jacobi symbol asf;lkjas owepiuf 
opiwu ;laksjdf;lkj sa ;daskfj
wer;kj;lajksdf;lkj

than

The jacobi symbol asf;lkjas owepiuf opiwu ;laksjdf;lkj sa ;daskfj wer;kj;lajksdf;lkj

which is hard to view in the command line.

There is some weird grammar in the latest version.

The jacobi symbol of an odd number if...

The symbols have two inputs, right? Not sure what "of an odd number" means without more clarification. And Jacobi should be capitalized, most likely.

You also still don't have the convention of a or b or n worked out properly. In fact, you might as well raise a ValueError "%s must be odd"%b or something like that, since it's an asymmetric situation but fairly nonstandardized notation (as opposed to p for prime, for instance).

After trying two that were identical, except for replacing the factoring and return value with

sage: def jacobi_symbol1(a,b):
    if b%2==0:
        raise ValueError, "n must be odd"
    return kronecker_symbol(a,b)
....: 

I get the following timings:

sage: timeit('jacobi_symbol(55,10000049000057)')
625 loops, best of 3: 271 µs per loop
sage: timeit('jacobi_symbol1(55,10000049000057)')
625 loops, best of 3: 8.55 µs per loop

Granted, this is a product of two relatively large primes, but

sage: n = next_prime(10^30)*next_prime(10^40)
sage: timeit('jacobi_symbol1(97,n)')
625 loops, best of 3: 8.24 µs per loop
sage: timeit('jacobi_symbol(97,n)')
<took over a minute and I got bored waiting>

really shows the difference. Make sure to use the kronecker symbol :) Indeed, if you look in number theory texts (well, the ones that have the Jacobi symbol as opposed to just Legendre symbol), none of them compute the Jacobi symbol 'by hand' - they all use that definition to prove you can do a Euclidean algorithm-style quadratic or sub-quadratic complexity.

By the way, this is normal review process for Sage; this is great for your first contribution, please don't be discouraged! Mine needed much more work (well, my second one did - the first one was a one-word change to remove an unused keyword).

Changed 9 years ago by tdupu

comment:6 Changed 9 years ago by tdupu

Ok. So this time it passed all the tests. The only issue could be the documentation. Dang it... I just checked. I copied and pasted the note from the Legendre Symbol and I need to fix this... don't review this until I fix that.

Changed 9 years ago by tdupu

comment:7 Changed 9 years ago by tdupu

Ok, I think I took care of all the issues. The function works quickly, the documentation appears to be correct and it passed all of the doc tests.

comment:8 Changed 9 years ago by kcrisman

  • Status changed from needs_work to needs_review

Great work, and doc looks great as well.

The only things that remain to be fixed is that you didn't include a commit message (see here, item 6, and a couple very minor typos.

Since this is your first patch, I've fixed those for you as a reviewer prerogative (this is fairly typical). Thank you for doing this!

Incidentally, I'm not getting the failure that the buildbot reports, which seems TOTALLY unrelated.

Changed 9 years ago by kcrisman

comment:9 Changed 9 years ago by kcrisman

  • Description modified (diff)
  • Status changed from needs_review to positive_review

comment:10 Changed 9 years ago by kcrisman

  • Milestone set to sage-4.7.1

Changed 9 years ago by jdemeyer

Patch rebased to sage-4.7.1.alpha3

comment:11 Changed 9 years ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 9 years ago by jdemeyer

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