开发环境与版本管理要求

本实验建议在类 Unix 系统（如 openEuler 或 Ubuntu）上进行，Windows 环境下亦可但非首选。在开发过程中，必须使用 Git 进行源代码版本控制。为确保代码演进的可追溯性，提交记录（commit）至少需要包含五个有意义的节点，分别对应环境初始化、基础算法编写、功能完善、测试用例增加以及最终整理。

扩展欧几里得算法核心实现

依据《密码工程》教材中的逻辑定义，我们需要构建一个函数来求解贝祖等式 $ax + by = \gcd(a, b)$ 中的系数 $x$ 和 $y$。该函数通常采用递归方式实现。为了与通用命名规范区分，我们将主函数命名为 compute_ext_gcd。

/**
 * 计算最大公约数及线性组合系数
 * @param n 输入整数 n
 * @param m 输入整数 m
 * @param res_x 输出指针，对应等式中 n 的系数
 * @param res_y 输出指针，对应等式中 m 的系数
 * @return 返回 n 与 m 的最大公约数
 */
int compute_ext_gcd(int n, int m, int *res_x, int *res_y) {
    // 递归终止条件
    if (m == 0) {
        *res_x = 1;
        *res_y = 0;
        return n;
    }
    
    int next_x, next_y;
    // 递归调用：计算 gcd(m, n % m)
    int gcd_val = compute_ext_gcd(m, n % m, &next_x, &next_y);
    
    // 更新系数以适配当前层级
    int temp = *res_x;
    *res_x = next_y;
    *res_y = next_x - (n / m) * next_y;
    
    return gcd_val;
}

模逆元计算逻辑封装

基于上述扩展欧几里得算法，我们可以进一步封装出计算模逆元的接口。若整数 $a$ 关于模数 $m$ 存在逆元，则必须满足 $\gcd(a, m) = 1$。计算得到的系数可能为负数，因此需要通过取模运算将其修正到 $[0, m-1]$ 区间内。

/**
 * 获取整数 a 在模 m 意义下的乘法逆元
 * @param target 待求逆元的数值
 * @param modulus 模数
 * @return 返回逆元值；若不存在则返回 -1
 */
int calculate_modular_inverse(int target, int modulus) {
    int x_coeff, y_coeff;
    int common_divisor = compute_ext_gcd(target, modulus, &x_coeff, &y_coeff);
    
    // 检查互质条件
    if (common_divisor != 1) {
        printf("错误：数值与模数不互质，无模逆元。\n");
        return -1;
    }
    
    // 处理负数情况，确保结果为非负最小剩余
    int final_result = (x_coeff % modulus + modulus) % modulus;
    return final_result;
}

功能验证与测试用例设计

完成核心算法后，需在主程序中构造具体的测试场景。标准案例包括验证 74 在模 167 下的逆元。此外，开发者应自行设计额外的测试数据以覆盖边界条件。

#include <stdio.h>

// ... 此处包含上述两个函数的定义 ...

int main() {
    int input_a, input_m;
    
    // 测试用例 1: 题目指定案例
    printf("[Case 1] 计算 74 mod 167 的逆元\n");
    int inv_1 = calculate_modular_inverse(74, 167);
    if(inv_1 > 0) printf("结果：%d (验证：%d * 74 %% 167 = %d)\n", inv_1, inv_1, (inv_1 * 74) % 167);
    
    // 测试用例 2: 自定义大数
    printf("\n[Case 2] 计算 65 mod 99 的逆元\n");
    int inv_2 = calculate_modular_inverse(65, 99);
    if(inv_2 > 0) printf("结果：%d\n", inv_2);

    // 测试用例 3: 错误输入（非互质）
    printf("\n[Case 3] 计算 10 mod 15 的逆元 (预期失败)\n");
    int inv_3 = calculate_modular_inverse(10, 15);
    
    return 0;
}

文档交付与代码归档

项目结束后，需生成包含完整源码和运行截图的技术文档。推荐使用 Markdown 格式撰写并转换为 PDF，或直接提供 Word 文档。Git 仓库的历史记录需清晰展示开发步骤，提交时应附带明确的日志信息以便审查。所有证据材料（运行截图、git log 导出图）应作为附件一同提交。