Proof
(related to Algorithm: Jacobi Symbol (Python))
- The correctness of the algorithm follows from the properties of the Jacobi symbol.
- Referring to these properties, the first (5) and second (6) supplementary laws are implemented as static methods of the class JacobiSymbol and their runtime is $\mathcal O(1).$
- The recursive method calculate removes for even numbers $a$ the factor $2$ and for odd numbers $a,$ the greatest common divisor (Python) algorithm is used.
- Since both operations need the runtime $\mathcal O(\log(b)),$ the recursive method calculate requires the runtime $\mathcal O(\log^2(b)),$ which corresponds to $\mathcal O(\log^3(b))$ bit operations.
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
- Blömer, J.: "Lecture Notes Algorithmen in der Zahlentheorie", Goethe University Frankfurt, 1997