# Implementation of the Jacobi Symbol in C

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;
}

$$$$

• As chux indicated below, it would be better if the variables result and condition were int variables to improve performance, result could be cast to short if the function absolutely has to return short. – pacmaninbw Jun 16 at 15:12
• Refusing to use break in a loop to...break out of the loop is a curious anti-pattern you've developed, especially considering that you use exit inside of pre-condition checks to break out of the entire program! I've seen this sort of code before, setting flags to indicate when the loop was done instead of actually just breaking out. It was a horrible spaghetti mess. Fortunately, it wasn't generated by a human; it was generated by a tool. I promptly rewrote it, reduced the number of lines by about half, and made it much more readable in the process. Also easier for compiler to optimize. – Cody Gray Jun 16 at 20:25
• “taught to ONLY USE ONE return statement”—This (perennial) advice is an unfortunate misunderstanding of historical context. The phrase “single return”/“single exit” means that you should only return to one address, not only from one address. Please read this answer for more details. – wchargin Jun 17 at 1:09
• If those exits are error exist you should use exit(EXIT_FAILURE) instead of exit(0). It may be useful for shell &&/|| combinations. And those printf's should go to stderr: printf(…) => fprintf(stderr, …). – user28434 Jun 17 at 9:19
• @user28434, the box for answers is further down the page. – Peter Taylor Jun 17 at 9:22

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.

• Thanks for your answers, I will try to apply your suggestions. And concerning the case n == 1: My textbooks never mentioned this convention, but thanks for pointing that out. Again many thanks for your time. – 3nondatur Jun 16 at 15:46
• Actually, the widest fixed-size type may be std::uint_fast64_t (in practice, that's unlikely, though). – Toby Speight Jun 17 at 10:19

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).

• Thanks a lot for pointing that out, I fixed it. – 3nondatur Jun 18 at 11:23