Jacobi symbol

The Jacobi symbol is another generalization of the Legendre symbol its multiplicative extension to arbitrary odd numbers as the lower parameter. Thus the Jacobi symbol of y modulo n is denoted by ( ) it only depends on y mod n and takes the values 1 and -1 on and 0 outside and it is multiplicative in both its parameters, i.e., ( )( ) = ( ) and (p( ) = always hold. 

The subgroup of residues with Jacobi symbol +1 is denoted by Z (+l). 

The Jacobi symbol is interesting because it can be computed efficiently for any pair of numbers, by use of the so-called law of quadratic reciprocity. Actually, one would often be more interested in deciding quadratic residuosity, but no probabilistic polynomial-time algorithm for that is known, unless the prime factors of n are additional inputs. (A cryptologic assumption that deciding quadratic residuosity is infeasible has been used several times in the literature, e.g., in the... 

Secondly, the two roots Wp of a quadratic residue mod p have different Legendre symbols, and similarly for q. Hence the four roots of a quadratic residue mod n are mapped to all the four different values (1, 1), (1, -1), (-1, 1), and (-1, -1) by Xn-In particular, two of them have the Jacobi symbol +1 they form a pair w and exactly one of them is a quadratic residue. 

Their special property used in the following (as in [Will80, G0MR88]) is that 2 has the Jacobi symbol -1 modulo any of them. This follows from the second supplement to the law of quadratic reciprocity ... 

One can generalize everything to all odd numbers, but the restriction that the Jacobi symbol of -1 modulo n is +1 simplifies the representation and makes the resulting constructions a little more efficient, and it is so easy to verify locally that the generalization does not seem worth while. 

Inversion, Chinese Remainder Algorithm, and Jacobi Symbol... 

As mentioned, Jacobi symbols can be evaluated using the law of quadratic reciprocity, which yields an algorithm similar to the Euclidean algorithm and of asymptotic complexity OQr ). 

If the function/is specified by an algorithm, one must take care what its intended domain is, because an algorithm may produce results even outside this domain. Values should only be regarded as a collision if they are in the domain. (For instance, they must have the correct Jacobi symbol in the factoring case — this is why the sets RQR , where membership can be decided efficiently, were introduced.)... 

One could exclude this by requiring algorithms to stop with an error message outside their intended domains. However, it is often more efficient to separate the membership test for the domain from the algorithm that computes the function. For instance, the squaring function on RQR would become very inefficient if each application included the computation of the Jacobi symbol of the input and in many situations, the input is the result of a previous squaring and therefore in the correct domain anyway. 

The algorithm for random choice in the weak family repeatedly generates a random element y of Z and computes its Jacobi symbol modulo , until y Z (-tl) then it outputs the class iy. In the strong family, the following faster algorithm can be used, because RQR is then equal to RQR % for n e Good Generate y gr let y = y , and use the class iy. ... 

The random choice of y (and similarly y ) in RQR works as follows In the scheme with zero-knowledge proof, y is chosen randomly in 2Z , and y = y or y = -y, whichever is smaller than nil, is used. In the scheme with local verifiability, a number y is chosen repeatedly, until it has the Jacobi symbol +1, and then negated if it is greater than nil. 

Remark 9.20. In the scheme with local verifiability, the random choice of jkj and sk2 is rather inefficient because of the computation of Jacobi symbols. One could avoid this if the bundling homomorphism were based on RQR% instead of RQR. However, no polynomial-time membership test in RQR" is known, and hence Definition 8.29 is not fulfilled. Nevertheless, it is now shown that the random choice in the main key generation of the signature scheme can be restricted to RQR, while maintaining the weaker membership tests for RQR in test and in verify simple. 

Recall that the computation of the Jacobi symbol is necessary to exclude trivial claws such as (2x) = 4(x). The computation of a Jacobi symbol in test is necessary to guarantee that if the signature is a successful forgery, it will pass this verification. 

In the scheme with local verifiability Generation of random numbers (six on average, because half of all numbers have the Jacobi symbol +1), the computation of Jacobi symbols (four on average) and 2t squarings modulo numbers of length 1. 

Testing a signature s = (a, u) on a message block m starts with the computation of a Jacobi symbol. 

---