Нахождение минимального значения для удовлетворения модуля

Проблема у меня есть х = (16807 хк) % 65536

то есть 16807k k x (мод. 65536)

Мне нужно рассчитать к зная х. Мое лучшее усилие на данный момент - это грубая сила. Есть ли математический способ вычислить k? Если бы не какая-либо оптимизация моего текущего кода была бы оценена.

t = x;
while ( t += 15115 ) // 16807k = 65536n + x - this is the n
{
    if (t%16807 == 0)
    return t/16807;
}
return x;

РЕДАКТИРОВАТЬ: Изменено += до 15115

Источник

4 ответа

Решение

Нечетное число имеет обратное мультипликативное значение по модулю степени два.

Инверсия 16807 мод 216 - 22039.

Это означает, что (16807 * 22039) % 65536 == 1и, следовательно, что

(16807 * 22039 * x) % 65536 == x

А также

k = (22039 * x) % 65536

Так что вам не нужно ничего пробовать, вы можете просто рассчитать k непосредственно.

Источник

Вы решаете проблемы такого рода, используя расширенный евклидов алгоритм для GCD 16807 и 65536

Остальная последовательность начинается с

R0=65536
R1=16807

и вычисление обратного с

V0=0  (V0*16807 == R0 mod 65536)
V1=1  (V1*16807 == R1 mod 65536)

Затем с помощью целочисленного длинного деления,

Q1=R0/R1=3,
R2=R0-Q1*R1=15115
V2=V0-Q*V1=-3 (V2*16807 == R2 mod 65536)

Q2=R1/R2=1,  
R3=R1-Q2*R2=1692
V3=V1-Q2*V2=4

Q3=8,  R4=1579,  V4=-35
Q4=1,  R5=113,   V5=39
Q5=13, R6=110,   V6=-542
Q6=1,  R7=3,     V7=581
Q7=36, R8=2,     V8=-21458
Q8=1,  R9=1,     V9=22039

так что 22039 находится как модульное обратное 15115 по модулю 65536.

Источник

Если k это решение, то k+65536 это тоже решение.

Простой метод грубой силы для нахождения первого k (k>= 0) будет:

for (k=0; k < 65536; k++) {
    if ( (k*16807) % 65536 == x ) {
        // Found it!
        break;
    }
}
if (k=65536) {
    // No solution found
}
return k;
Источник

Если вам нужно посмотреть вверх k неоднократно для разных xВы можете создать таблицу решений, прежде чем приступить к декодированию:

uint16_t g = 16807u;
uint16_t *mods = malloc(0x10000 * sizeof(*mods));
int i;

for (i = 0; i < 0x10000; i++) {
    uint16_t x = g * i;    // x is effectively x mod 2**16

    mods[x] = i;
};

Решение для вашего уравнения в 16-битном диапазоне:

uint16_t k = mods[x];

Предполагается, что x 16-разрядное целое число без знака. Не забудь free(mods) после того, как вы сделали

Источник
Другие вопросы по тегам