Jump to content

User:James in dc/sandbox/Jacobi symbol

From Wikipedia, the free encyclopedia

sandbox

Jacobi symbol

[edit]

In algebraic number theory and related branches of mathematics the Jacobi symbol is defined for all integers and all positive odd integers [1]. For where the are odd primes[2] the Jacobi symbol is the product of Legendre symbols

. (and for completeness is defined to be )

Properties of the Jacobi symbol

[edit]

The Legendre symbol is defined for all integers and all odd primes by

The properties of the Jacobi symbol are derived from those of the Legendre symbol.[3]

Since is true for each factor,

Obviously from the definition

These imply that and

If then for every in the product so and therefore

If then one of the s divides and

If then every and as well.

Differences between Legendre and Jacobi symbols

[edit]

for composite only means that there were an even number of minus signs in the product; it does not mean that is a quadratic residue . For prime it does.

Euler's criterion is not true for composite . For example but[4] See uses, below.

Quadratic reciprocity

[edit]

First Supplement

[edit]

Let where and . The values of the Legendre symbols are known: and

if and only if the number of is odd.

Likewise is if and only if the number of is odd. This shows that

which is equivalent to

Second Supplement

[edit]

Let where and . The values of the Legendre symbols are known: and

if and only if the number of is odd.

Likewise is if and only if the number of is odd. This shows that

which is equivalent to

Combining with the first supplement gives

which is equivalent to

Legendre

[edit]

must be positive and odd.

Let where and .

In the same way let where the and are prime and and .

The values of the inverted Legendre symbols are known:

if and only if the number of is odd

if and only if the number of is odd.

The sign is negative if and only if the number of factors is odd, i.e. when both the number of is odd and the number of is odd. This shows that

which is equivalent to

Gauss

[edit]

must be positive and odd.

Define the operator on positive odd as:

This operator is multiplicative

Let and .

For every Legendre symbol in the product it is known that

Gauss' lemma

[edit]

Gauss's lemma extends to Jacobi symbols. Let be an odd number and define the sets and Then . For let .

Then .

Zolotarev's lemma

[edit]

Zolotarev's lemma extends to Jacobi symbols. For let be the permutation of the set (all residue classes, not just the relatively prime ones) induced by multiplication by . The signature of this permutation is the Jacobi symbol:

See here for details and an example.

Calculating the Jacobi symbol

[edit]

The expression means any number satisfying and [5]

Repeat these steps until is 0 or 1. If it is 0, the two original numbers were not relatively prime; if it is 1 the accumulated sign is the value of the Jacobi symbol.

1) if is negative       I.e. flip the sign if .

2) If is even repeatedly divide by 4 until is odd or is twice an odd number.

In the latter case       I.e. flip the sign if .

3) If is odd and positive       I.e. flip the sign if and .

A few examples:

Analysis

[edit]

Calculating the Jacobi symbol is similar to computing the gcd using the Euclidean algorithm.





Examine the bits in to find where



To show the parallel use the notation for the gcd[6]

Lamé’s Theorem (1844) states that the number of evaluations to compute a gcd is at most five times the number of base-ten digits of the smaller number. The Jacobi calculation does the same sort of recursion[7] but sometimes divides by powers of 4. This has the effect of skipping ahead (the example would stop after the first step), reducing the number of operations and also reducing the size of the numbers compared to Euclid. In other words, the Lamé bound applies to Jacobi as well.

So, for example 2000-digit numbers will require about twice as many s as 1000-digit ones. The cost of may go up with the number of digits.

Machine calculation

[edit]

The algorithm is well-suited to machine calculations since its running time is and it requires negligeable storage. A number of authors[8] have published code to evaluate Jacobi. The Lua and C++ routines below replace the recursion with a loop.[9]

Lua code
[edit]
function jacobi(a, m)
  assert(m > 0 and m % 2 == 1, "m must be positive and odd")

  local t = 1                      -- returned value

  while true do

    if a == 1 then 
       return t                             -- success t is the Jacobi symbol
    elseif a == 0 then 
       return 0                              -- a and m were not relatively prime
    end

    if a < 0 then
       a = -a                            -- if a is negative set a = |a|
       if m % 4 == 3 then                -- and evaluate (-1|m)
         t = -t
       end
    end
                                           -- a is positive
    local p = 0                       -- power of 2 dividing a
    while a % 2 == 0 do
      p = p + 1
      a = a / 2
    end
    if p % 2 == 1 then                   -- if the power of 2 is odd
      if m % 8 == 3 or m % 8 == 5 then     -- evaluate (2|m)
        t = -t
      end
    end
                                         -- a is odd
    if m % 4 == 3 and a % 4 == 3 then    -- does inverting the symbol
      t = -t                             -- change its sign?
    end 

    local temp = a                       -- next iteration is (m mod a|a)
    a = m % a
    m = temp
end
C++ code
[edit]
int jacobi(int a, int m) {
    assert(m > 0 && m % 2 == 1);
    
    int t = 1;      // return value (accumulated sign)
    
    while (1) {

        if (a == 1) return t;        // success 
        if (a == 0) return 0;        // a and m were not coprime

        if (a < 0) {               // if a is negative replace it with the absolute value 
           a = -a;                 // and evaluate (-1|m)
           if (m % 4 == 3) t = -t;     
        }                          // a is positive

        int p = 0;                 // power of 2 dividing a        
        while (a % 2 == 0) {
            a /= 2;
            p++;
        }                          // a is odd
        if (p % 2 == 1)                                  // if the power of 2 was odd
            if (m % 8 == 3 || m % 8 == 5)   t = -t;      // evaluate (2|m)
                                                      
        if (m % 4 == 3 && a % 4 == 3) t = -t;              // evaluate (m|a)

        int temp = a;                                    // next iteration is m mod a over a
        a = m % a;
        m = temp;
    }
}

Uses

[edit]

The Jacobi symbol is of theoretical interest in number theory,[10] but its main use is computational.[11] Cryptography in particular uses large prime numbers. A number of primality testing and integer factorization algorithms take advantage of the fact that Jacobi symbols can be computed quickly.

Because Euler's criterion is not valid for composite , the Jacobi symbol can be used to detect composite numbers. Pick a random number and calculate the Jacobi symbol . If then is composite; this is the basis of the Solovay–Strassen primality test. In some algorithms, such as the Lucas–Lehmer primality test, the value of certain Jacobi symbols is known theoretically[12] and can be used to detect (hardware or software) errors.[13]

An example of a factoring algorithm that uses Jacobi symbols is the continued fraction algorithm[14] To factor it tries to find numbers satisfying . This involves constructing a database of primes and quadratic residues which requires multiple Jacobi symbol evaluations.

History

[edit]

The Legendre symbol was introduced in 1798. It is not practical for calculations because it requires factorization into primes before it can be inverted. Jacobi introduced his symbol in 1837.[15] to facilitate calculation. As explained here Gauss' first proof of quadratic reciprocity[16] considers composite moduli[17] and obtains some special cases of the Jacobi symbol.[18]

Table

[edit]

(k/n)   for  1≤ k ≤ 30,   1≤ n ≤ 59,   n odd.

k
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0
5 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0
7 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1
9 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
11 1 −1 1 1 1 −1 −1 −1 1 −1 0 1 −1 1 1 1 −1 −1 −1 1 −1 0 1 −1 1 1 1 −1 −1 −1
13 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 0 1 −1 1 1
15 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 0
17 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1
19 1 −1 −1 1 1 1 1 −1 1 −1 1 −1 −1 −1 −1 1 1 −1 0 1 −1 −1 1 1 1 1 −1 1 −1 1
21 1 −1 0 1 1 0 0 −1 0 −1 −1 0 −1 0 0 1 1 0 −1 1 0 1 −1 0 1 1 0 0 −1 0
23 1 1 1 1 −1 1 −1 1 1 −1 −1 1 1 −1 −1 1 −1 1 −1 −1 −1 −1 0 1 1 1 1 −1 1 −1
25 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
27 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0
29 1 −1 −1 1 1 1 1 −1 1 −1 −1 −1 1 −1 −1 1 −1 −1 −1 1 −1 1 1 1 1 −1 −1 1 0 1
31 1 1 −1 1 1 −1 1 1 1 1 −1 −1 −1 1 −1 1 −1 1 1 1 −1 −1 −1 −1 1 −1 −1 1 −1 −1
33 1 1 0 1 −1 0 −1 1 0 −1 0 0 −1 −1 0 1 1 0 −1 −1 0 0 −1 0 1 −1 0 −1 1 0
35 1 −1 1 1 0 −1 0 −1 1 0 1 1 1 0 0 1 1 −1 −1 0 0 −1 −1 −1 0 −1 1 0 1 0
37 1 −1 1 1 −1 −1 1 −1 1 1 1 1 −1 −1 −1 1 −1 −1 −1 −1 1 −1 −1 −1 1 1 1 1 −1 1
39 1 1 0 1 1 0 −1 1 0 1 1 0 0 −1 0 1 −1 0 −1 1 0 1 −1 0 1 0 0 −1 −1 0
41 1 1 −1 1 1 −1 −1 1 1 1 −1 −1 −1 −1 −1 1 −1 1 −1 1 1 −1 1 −1 1 −1 −1 −1 −1 −1
43 1 −1 −1 1 −1 1 −1 −1 1 1 1 −1 1 1 1 1 1 −1 −1 −1 1 −1 1 1 1 −1 −1 −1 −1 −1
45 1 −1 0 1 0 0 −1 −1 0 0 1 0 −1 1 0 1 −1 0 1 0 0 −1 −1 0 0 1 0 −1 1 0
47 1 1 1 1 −1 1 1 1 1 −1 −1 1 −1 1 −1 1 1 1 −1 −1 1 −1 −1 1 1 −1 1 1 −1 −1
49 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1
51 1 −1 0 1 1 0 −1 −1 0 −1 1 0 1 1 0 1 0 0 1 1 0 −1 1 0 1 −1 0 −1 1 0
53 1 −1 −1 1 −1 1 1 −1 1 1 1 −1 1 −1 1 1 1 −1 −1 −1 −1 −1 −1 1 1 −1 −1 1 1 −1
55 1 1 −1 1 0 −1 1 1 1 0 0 −1 1 1 0 1 1 1 −1 0 −1 0 −1 −1 0 1 −1 1 −1 0
57 1 1 0 1 −1 0 1 1 0 −1 −1 0 −1 1 0 1 −1 0 0 −1 0 −1 −1 0 1 −1 0 1 1 0
59 1 −1 1 1 1 −1 1 −1 1 −1 −1 1 −1 −1 1 1 1 −1 1 1 1 1 −1 −1 1 1 1 1 1 −1

See also

[edit]

Notes

[edit]
  1. ^ It is an extension of the Legendre symbol, which is only defined for positive odd prime values of and is itself extended by the Kronecker symbol, which is defined for all nonzero values of
  2. ^ positive, but not necessarily distinct
  3. ^ Practically all textbooks on elementary number theory cover this material, e.g. Cohen, Hardy & Wright, Ireland and Rosen, Lemmermeyer.
  4. ^ Note that and 2 is a residue mod the primes 7 and 23
  5. ^ Typical ranges are or Euclid uses the first; Jacobi doesn't care.
  6. ^ Consecutive Fibonacci numbers are used in Lames's proof as they provide an upper bound
  7. ^ Cohen
  8. ^ Riesel p. 285 (Pascal), Cohen
  9. ^ Cohen p 26 gives efficient ways to code the tests mod 2, 4, and 8: e.g. if (a%4 == 3 && m%4 == 3) is the same as if (a & m & 2).
  10. ^ If the top or the bottom argument is held fixed and the other one is allowed to vary it is a real Dirichlet character
  11. ^ See below computing JS
  12. ^ For example a primitive root must be a nonresidue, so its Jacobi symbol will be -1
  13. ^ Lucas–Lehmer does arithmetic modulo the number being tested (the largest prime so far found current record holder has over eighty million bits) and often has to run for weeks at a time
  14. ^ Riesel p. 194ff
  15. ^ Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin: 127–136.
  16. ^ Disquisitiones Arithmeticae arts 131-133
  17. ^ (cases 9-14)
  18. ^ He proves e.g. that if the prime is a quadratic residue mod a composite number and both are , then is a residue mod This is not the same as because being a residue mod is not the same as

References

[edit]

Books

  • Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second ed.). New York: Springer. ISBN 0-387-97329-X.
  • Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4.
  • Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5

Journal articles