Make Jacobi symbol

[kcrisman]

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 attachment: 11138_rebased.patch

Component: number theory

Author: Taylor Dupuy

Reviewer: François Bissey, Karl-Dieter Crisman

Merged: sage-4.7.1.alpha4

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

[tdupu]

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

[tdupu]

comment:1

Attachment: trac11138.patch.gz

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.

[kiwifb]

comment:2

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.

[kcrisman]

Reviewer: François Bissey, Karl-Dieter Crisman

[kcrisman]

comment:3

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!

[kcrisman]

Author: Taylor Dupuy

[tdupu]

comment:4

Attachment: trac11138.2.patch.gz

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.

[kcrisman]

comment:5

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

[tdupu]

Attachment: trac11138.3.patch.gz

[tdupu]

comment:6

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.

[tdupu]

Attachment: trac11138.4.patch.gz

[tdupu]

comment:7

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.

[kcrisman]

comment:8

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.

[kcrisman]

comment:9

Attachment: trac11138.4-with-commit-message.patch.gz

Apply only attachment: trac11138.4-with-commit-message.patch.

[jdemeyer]

Attachment: 11138_rebased.patch.gz

Patch rebased to sage-4.7.1.alpha3

[jdemeyer]

Merged: sage-4.7.1.alpha4