Jacobi符号在C中的实现

Question

我对C编程很陌生，并为Jacobi符号的计算编写了以下算法。虽然有一些更快的版本，这个算法可用，我只是寻找一些反馈，我的编码风格。我应该提到的是，我被教导在函数中只使用一个返回语句，而不使用像break、continue或go-to这样的东西。我也相信这是一种“哲学”。

1. 我该如何改进呢？
2. 有什么不清楚的地方吗？

我可以想到的一点是使用“长长”而不是“长”，因为这个算法在密码学中使用，因此应该适用于非常大的整数。

任何形式的反馈都将受到欢迎。

编辑:在这段代码中仍然有一个(注释的) print语句，它有助于将算法可视化。

#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

我只是在寻找一些关于我的编码风格的反馈。

格式化很好。我希望是自动格式化的。

尊重表示宽度

与其强制使用水平滚动条，不如将自动格式设置为较窄的宽度以避免这种情况。

避免教条

“在函数中只使用一个返回语句，而不使用中断、继续或转到之类的东西。”->这是一个合理的目标，但最好是为清晰的代码编写代码。当break, continue提供更干净的代码时，使用它，甚至有时使用goto。

我该如何改进呢？

使用short来节省数组中的空间--而不是这里的

short jacobi(long a, long n)返回0,1，-1。short没有任何空间、代码和性能节省。建议在这里返回int。int通常是整数的最佳类型。

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

加密请求无符号类型

与long不同，考虑最宽的无符号类型的uintmax_t或最宽的固定大小类型：uint64_t。

无符号类型将提高代码性能。

long n ... n_mod8 = n % 8;需要一个部门，因为n % 8有15个不同的结果( -7 .7 )。使用unsigned long n，n % 8只是一个掩码操作。

考虑bool

为了清晰起见，请使用bool。

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

删除调试代码

例如// printf("(%d|%d) and result = %d \n", a, n, result);。

错误消息:考虑stderr

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

Post预期测试代码结果

printf("%d", jacobi(4852777,12408107));应该打印什么？

再考虑几个测试用例。

后可编译代码

尾随‘破坏编译。

未成年人

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

有什么不清楚的地方吗？

我会为雅可比符号添加一个引用。

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

n == 1?

嗯。雅可比符号允许n==1。这里的代码没有。

Answer 2

我可以想到的一点是使用“长长”而不是“长”，因为这个算法在密码学中使用，因此应该适用于非常大的整数。

非常大的整数意味着使用GMP或类似的库，而不是使用long long。虽然如果您使用的是GMP，那么您也可以使用mpz_jacobi。

这可能会引起争议，但在我看来，所有新的C代码都应该使用来自stdint.h的类型，除非强制使用不太特定的类型来与遗留代码进行互操作性。

a = a % n;

这是婴儿车。第一次执行时，a可能是负的，但是算法的其余部分要求a是非负的。作为测试用例，请考虑jacobi(-1, 3)。