时间戳

首页 > 解决方案 > 如何在c中计算数组元素到整数的模乘法？

c - 如何在c中计算数组元素到整数的模乘法？

问题描述

考虑以下：

uint8_t message[15] = {
     0x32, 0xdc, 0x21, 0x55, 0x3f, 0x87, 0xc8, 0x1e,
     0x85, 0x10, 0x43, 0xf9, 0x93, 0x34, 0x1a
};
uint64_t num = 0xa1b2c33412;

我想将上述变量乘以num数组message[]。我需要的伪代码如下：

uint8_t message[15] = {
     0x32, 0xdc, 0x21, 0x55, 0x3f, 0x87, 0xc8, 0x1e,
     0x85, 0x10, 0x43, 0xf9, 0x93, 0x34, 0x1a
};
uint64_t num = 0xa1b2c33412;
uint64_t p = 0x31ba62ca3037;
uint64_t result = 0x00;
result = moduloMultiplication(message, num, p); // (message * num) (mod p)

我期待以下结果：

num * msg = num*msg mod p
num * msg = 0x2bf2d18cdf92   (Final result)

有没有办法将数组与 type 的值相乘uint64_t？

任何有关这方面的帮助将不胜感激......

标签： carraysuint64

解决方案

假设存储在 15 字节数组中的数字是大端顺序，这里有一个简单的解决方案：

#include <stdio.h>
#include <stdint.h>

uint64_t moduloMultiplication(const uint8_t message[15], size_t n,
                              uint64_t num, uint64_t p)
{
    uint64_t res = 0;
    for (size_t i = 0; i < n; i++) {
        // assuming `p < 1ULL << 56`
        res = (res * 256 + message[i] * num) % p;
    }
    return res;
}

int main() {
    uint8_t message[15] = {
        0x32, 0xdc, 0x21, 0x55, 0x3f, 0x87, 0xc8, 0x1e,
        0x85, 0x10, 0x43, 0xf9, 0x93, 0x34, 0x1a
    };
    uint64_t num = 0xa1b2c33412;
    uint64_t p = 0x31ba62ca3037;
    // result = (message * num) (mod p)
    uint64_t result = moduloMultiplication(message, sizeof message, num, p);

    printf("%#"PRIx64"\n", result);
    return 0;
}

输出：0x2bf2d18cdf92

结果与问题中的结果不同，因为要么message不正确，要么您的中间结果是近似的：201FF4CDCFE8C0000000000000000000000000000似乎不正确。

推荐阅读