Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The algorithm is described as follow,

Eisenstein proposed the following algorithm for computing the Jacobi symbol $(a|n)$ where $a$ and $n$ are odd numbers. Write $n = aq + er$ where $q = \lfloor n/a \rfloor$ if this is even, or $q = \lfloor n/a \rfloor + 1$ otherwise, and $e = \pm 1$ accordingly. Then $r$ is odd, and you can use the quadratic reciprocity law and the formula for $(-1|r)$ to continue by replacing the pair $n,a$ with the pair $a, r$.

I understand the Euler's algorithm (division), and got it to work correctly. Unfortunately, I have no idea how this algorithm works. Furthermore, what's the end condition of this algorithm? My guess was $r \neq 1$ is the end condition, but the result was completely wrong. An example to illustrate this algorithm would be greatly appreciated.

Edit This is my solution, written in C#

public int eisensteinAlgo( int a, int n ) {
            int parity = 1;
            int q = 0;
            int epsilon;
            int r = 0;
            while ( ( n % a ) == 0 ) {
                q = n / a;
                if ( ( q % 2 ) == 1 ) {
                    q += 1;
                    epsilon = -1;
                }
                else {
                    epsilon = 1;
                }
                r = n - ( a * q );
                r *= epsilon;
                parity *= ( int )Math.Pow( -1.0, ( r - 1 ) / 2 );
                n = a;
                a = r;
            }
            return parity;
}    

Thank you,

share|improve this question
    
Notes on your code: a. It might be better to use (q & 1) == 1 instead of ( q % 2 ) == 1 b. n - ( a * q ) is just n % a all over again; why are you computing it again? c. Exponentiation is slow; figure out a conditional to replace your computation for parity (which I'll leave as an exercise). –  J. M. Apr 7 '11 at 5:13
    
@J.M.: Many thanks for your comments. However, my rule of thumb is to get the right code first, then optimize it later. Because I think writing the right code in the first place is often much harder than optimize it. –  Chan Apr 7 '11 at 5:29
    
"get the right code first, then optimize it later." - of course. :) –  J. M. Apr 7 '11 at 5:30
    
Thanks for the agreement ;) –  Chan Apr 7 '11 at 5:37
add comment

1 Answer

up vote 1 down vote accepted

The reduction step is simply to apply quadratic reciprocity in order to rewrite $(a|n)$ to $\pm (n|a)\:,\:$ then reduce $n$ modulo $a\:$ in a way that the remainder stays odd (by forcing the quotient $q\:$ to be even). The algorithm terminates when $a$ divides $n\:,$ with the result being either the accumulated sign (if $ a=1)\:,$ or else $\:0\:$ (if $ a>1)\:.\:$ The choice of odd remainder eliminates the need to pull out factors of $2\:.$ But one pays a price for this algorithmic simplification since it makes the algorithm less efficient.

share|improve this answer
    
Sorry for late reply. I was trying to solve other problems. First of all, thanks a lot for your answer. But I don't understand how the result were calculated. Do we calculate $(-1|r)$ each time using the formula $(-1)^{\frac{n-1}{2}}$ and then multiply it with the result? –  Chan Apr 7 '11 at 4:03
1  
Yes, you can keep a $\:\pm 1\:$ sign "accumulator" multiplying the symbol during the calculation. If you're stuck then show your work so we can see precisely where you're stuck. –  Bill Dubuque Apr 7 '11 at 4:19
    
Thanks, I posted my solution in C# since I don't know which language you're most familiar with. However, the semantic meaning should be straightforward. Thanks. –  Chan Apr 7 '11 at 4:45
    
I've just figured out the program I wrote above was incorrect for several cases. I got the reverse sign, would you mind taking a look at my code? Thanks in advance. –  Chan Apr 11 '11 at 23:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.