1
$\begingroup$

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,

  • 0
    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).2011-04-07
  • 0
    @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.2011-04-07
  • 0
    "get the right code first, then optimize it later." - of course. :)2011-04-07
  • 0
    Thanks for the agreement ;)2011-04-07

1 Answers 1

1

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.

  • 0
    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?2011-04-07
  • 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.2011-04-07
  • 0
    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.2011-04-07
  • 0
    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.2011-04-11