Implementation of the Jacobi Symbol in C

Question

I am new to C programming and wrote the following algorithm for the calculation of the Jacobi Symbol. Though there are some faster versions of this algorithm available I am only looking for some feedback on my coding style. I should mention that I was taught to ONLY USE ONE return statement in functions and NOT to use things like break, continue or go-to. This is a "philosophy" I also believe in.

1. How could I improve?
2. Is anything unclearly formulated?

One point I could think of would be to use "long long" instead of only "long" since this algorithm is used in cryptography and should thus be suited for very large integers.

Any kind of feedback would be welcome.

EDIT: There is still a (commented) print statement in this code that helps to visualize the algorithm.

#include <stdio.h>
#include <stdlib.h>


/*
+*****************************************************************************

* Function Name:    jacobi

* Function:         Calculate the Jacobi Symbol

* Arguments:        a   =   numerator
                    n   =   denominator

* Return:           (a|n)

* Notes:            This function evaluates the Jacobi Symbol for two integers
                    a and n. It is based on the same idea as the Euclidean 
                    alogrithm for the gcd. The bit complexity is O(log^2(p)). 

-****************************************************************************/

short jacobi(long a, long n)
{
    // The two if-conditions below terminate the function in case of wrong inputs, i.e.: n < 3  or 2 | n.
    if (n<3) {
        printf("Wrong input for the Jacobi Symbol: The denominator has to be greater than 2.\n");
        exit(0);
    }
    if (n%2 == 0) {
        printf("Wrong input for the Jacobi Symbol: The denominator has to be coprime to 2.\n");
        exit(0);
    }
    long n_mod8 = 0;
    short result = 1;
    short condition = 1;
    while (condition == 1) {
        // printf("(%d|%d) and result = %d \n", a, n, result);
        a = a % n;
        // The The if-condition below utilises the fact that (0|n) = 0.
        if (a == 0) {
            condition = 0;
            result = 0;
        } else {
            // The while-loop below utilises the Second Supplement
            // to extract the 2’s out of a.
            while (a % 2 == 0) {
                a = a / 2;
                n_mod8 = n % 8;
                if (n_mod8 == 3 || n_mod8 == 5) {
                    result = -result;
                }
            }
            // The if-condition below utilises the fact (1|n) = 1.
            if ( a == 1) {
                condition = 0;
            } else {
                // This else-condition utilises the Law of
                // Quadratic Reciprocity to transfer (a|n) to (n|a).
                long tmp = a;
                a = n;
                n = tmp;
                if (a % 4 == 3  &&  n % 4 == 3) {
                    result = -result;
                }
            }
        }
    }
    return result;
}





int main()
{
    printf("%d", jacobi(4852777,12408107));
    return 0;
}

```

Answer 1

I am only looking for some feedback on my coding style.

Formatting is good. I hope it is auto formatted.

Respect the presentation width

Rather than oblige a horizontal scroll bar, auto format to a narrower width to avoid that.

Avoid dogma

"to ONLY USE ONE return statement in functions and NOT to use things like break, continue or go-to." --> This is a reasonable goal, but better to code for clarity. Use break, continue and even sometimes goto when it provides cleaner code.

---

How could I improve?

Use short to save space in arrays - not here

short jacobi(long a, long n) returns 0,1,-1. There is no space, code, performance savings expected with short. Recommend returning int here. int is often the optimal type for an integer.

// short result = 1;
int result = 1;
...
return result;

Cryptography begs for unsigned types

Instead of long, consider the widest unsigned type of uintmax_t or the widest fixed size type: uint64_t.

Unsigned types will improve code performance.

long n ... n_mod8 = n % 8; requires a division as n % 8 has 15 different results [-7 ... 7]. With unsigned long n, n % 8 is simply a mask operation.

Consider bool

For clarity, use bool.

//short condition = 1;
//while (condition == 1) {
bool condition = true;
while (condition) {

Remove debug code

e.g. // printf("(%d|%d) and result = %d \n", a, n, result);.

Error messages: consider stderr

// printf("Wrong input for the Jacobi Symbol:...
fprintf(stderr, "Wrong input for the Jacobi Symbol: ...

Post expected test code results

What should printf("%d", jacobi(4852777,12408107)); print?

Consider a few more test cases.

Post compilable code

Trailing ``` breaks compilation.

Minor

// The The if-condition below utilises the fact that (0|n) = 0.
to
// The if-condition below utilises the fact that (0|n) = 0.

---

Is anything unclearly formulated?

I'd add a reference for Jacobi symbol.

// https://en.wikipedia.org/wiki/Jacobi_symbol

n == 1?

Hmmm. Jacobi symbol allows n==1. Code here does not.

Answer 2

One point I could think of would be to use "long long" instead of only "long" since this algorithm is used in cryptography and should thus be suited for very large integers.

Very large integers means using GMP or a similar library, not using long long. Although if you're using GMP then you might as well use mpz_jacobi.

This may be controversial, but in my opinion all new C code should use the types from stdint.h unless forced to use less specific types for interoperability with legacy code.

---

        a = a % n;

This is buggy. The first time this is executed, a might be negative, but the rest of the algorithm requires a to be non-negative. As a test case consider jacobi(-1, 3).