}citenamefont \#1[\#1]{}url \#1[`#1`]{}urlprefix\[2\][\#2]{} \[2\]\[\][[\#2](#2)]{}


---
abstract: 'The family of left-to-right algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Schönhage, Möller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in .'
author:
- Niels Möller
bibliography:
- 'ref.bib'
date: 2019
title: Efficient computation of the Jacobi symbol
---

Introduction
============

The Legendre symbol and its generalizations, the Jacobi symbol and the Kronecker symbol, are important functions in number theory. For simplicity, in this paper we focus on computation of the Jacobi symbol, since the Kronecker symbol can be computed by the same function with a little preprocessing of the inputs.

Jacobi and GCD
--------------

Two quadratic algorithms for computing the Kronecker symbol (and hence also the Jacobi symbol) are described as Algorithm 1.4.10 and 1.4.12 in [@cohen]. These algorithms run in quadratic time, and consists of a series of reduction steps, related to Euclid’s algorithm and the binary algorithm, respectively. Both Kronecker algorithms share one property with the binary algorithm: The reduction steps examine the current pair of numbers in both ends. They examine the least significant end to cast out powers of two, and they examine the most significant end to determine a quotient (like in Euclid’s algorithm) or to determine which number is largest (like in the binary algorithm).

Fast, subquadratic, algorithms work by divide-and-conquer, where a substantial piece of the work is done by examining only one half of the input numbers. Fast left-to-right is related to f