Step by Step solution about How to resolve the algorithm Jacobi symbol step by step in the C++ programming language

The provided C++ code calculates and prints a table of Jacobi symbols for various pairs of integers (k, n), where k is odd and positive, and n is odd and positive or zero. The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol and is defined as follows:

jacobi(k, n) = 1 if n is a quadratic residue modulo k
jacobi(k, n) = -1 if n is a quadratic non-residue modulo k
jacobi(k, n) = 0 if n is divisible by k

Key Implementation Details:

1. The jacobi function:

   • Computes the Jacobi symbol for a given pair (k, n).
   • Uses a while loop to perform the necessary operations.
   • It handles various special cases based on the divisibility of n by 2 and 4, and the divisibility of k by 8.

2. The print_table function:

   • Prints a table of Jacobi symbols for k values ranging from 0 to kmax and n values ranging from 1 to nmax, both with an increment of 2 to only consider odd numbers.
   • It also prints the column and row headers.

Main Function:

• The main function calls print_table with kmax set to 20 and nmax set to 21.
• This generates a table of Jacobi symbols for odd pairs (k, n) within the specified ranges.

Sample Output:

The output of the program, considering kmax and nmax set to 20 and 21, respectively, will be a table of Jacobi symbols as follows:

n\k|  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
----
---|---
1 | -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1
3 |  0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0
5 |  1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1
7 | -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1
9 |  0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0
11 |  1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1   1  1
13 | -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1  1  -1
15 |  0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0
17 |  1  1   1  1   1  1   1  1   1  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  -1  1  -1
21 |  0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0   0  0

This table shows the Jacobi symbols for various combinations of (k, n) within the specified ranges.

#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>

int jacobi(int n, int k) {
    assert(k > 0 && k % 2 == 1);
    n %= k;
    int t = 1;
    while (n != 0) {
        while (n % 2 == 0) {
            n /= 2;
            int r = k % 8;
            if (r == 3 || r == 5)
                t = -t;
        }
        std::swap(n, k);
        if (n % 4 == 3 && k % 4 == 3)
            t = -t;
        n %= k;
    }
    return k == 1 ? t : 0;
}

void print_table(std::ostream& out, int kmax, int nmax) {
    out << "n\\k|";
    for (int k = 0; k <= kmax; ++k)
        out << ' ' << std::setw(2) << k;
    out << "\n----";
    for (int k = 0; k <= kmax; ++k)
        out << "---";
    out << '\n';
    for (int n = 1; n <= nmax; n += 2) {
        out << std::setw(2) << n << " |";
        for (int k = 0; k <= kmax; ++k)
            out << ' ' << std::setw(2) << jacobi(k, n);
        out << '\n';
    }
}

int main() {
    print_table(std::cout, 20, 21);
    return 0;
}