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.

I have a problem with Tonelli-Shanks algorithm with numbers $n = 87463$ and $p = 17$. Solutions are supposed to be $x_1 = 7$, $x_2 = 10$, but I get $11$ and $6$.
First with sieving I get a list of primes $<p$: $2, 3, 4, 7, 11, 13$ and then start computing Legendre symbols for each of the numbers in the list. I use binary Jacobi algorithm ( http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.9089) and get these values of Legendre symbol:
$a = 2, p = 17, (\frac{2}{17}) = 1$
$a = 3, p = 17, (\frac{3}{17}) = -1$
$a = 5, p = 17, (\frac{5}{17}) = -1$
$a = 7, p = 17, (\frac{7}{17}) = -1$
$a = 11, p = 17, (\frac{11}{17}) = -1$
$a = 13, p = 17, (\frac{13}{17}) = 1$
So then I have to pick the first prime which is non-residue and plug this into Tonelli-Shanks to get the solution.
But here is the problem: I can't understand why $(\frac{3}{17}) = -1$. Binary-Jacobi says it's $-1$, Legendre symbol calculators in the web say it's $-1$. But when I put these number directry to Euler's criterion I get confused: $3^{\frac{17-1}{2}} = 3^8 = 6551$, and $6551 \mod 17 = 6$. How can this even happen as $(\frac{a}{p}) = \{-1, 0, 1\}$?
And then, when I plug $a = 5$ for Tonelli-Shanks (and Legendre is $-1$ here and seems corerct) I get correct results - $7$ and $10$.
Could someone help me figure out where I've messed up?

Update: problem solved - just made a typo in 6561...

share|improve this question
2  
You will find that $3^8=6561$ (6551 is not divisible by 3) –  Mark Bennet Aug 13 '12 at 8:48
1  
I get $3^{(17-1)/2} \equiv 16 \equiv -1 \pmod{17}$ –  Old John Aug 13 '12 at 8:50
1  
Note $3^3=27\equiv 10 \mod 17$. $10^2=100\equiv-2$. $3^8\equiv 3^2\times -2 = -18\equiv -1$ –  Mark Bennet Aug 13 '12 at 8:54
    
Thanks! I was trying to go through Tonelli-Shanks computing all values by hands and made a mistake with $6561$. But now I can't explain why $3$ leads to incorrect solution and $5$ to a correct one :( –  Ypsilon IV Aug 13 '12 at 9:00

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.