Большое целочисленное модульное возведение в степень

Как вычислить (xy) по модулю z, если 1 ‹= x, y ‹= 101000 и z любое положительное целое число 1 ‹= z ‹ 231< /суп> ?

До сих пор я делал следующее: сканировал x и y как строку, получал по модулю, затем вычислял (xy) по модулю z.

Я знаю, что это неправильно, потому что (xy) mod z не равно ((x mod z)(y mod z)) mod z. Тогда как мне это решить?

Изменить: извините, я сделал нижнее ограничение x и y таким высоким при создании вопроса. Я просто хочу сосредоточиться на большой целочисленной проблеме, а не на модульном возведении в степень :).

#define MOD z

long long power (long long k, long long n) {
    if (n == 1) return k;
    else {
        long long p = power (k, n/2);
        if (n % 2 == 0) return (p * p) % MOD;
        else return (((p * p) % MOD) * k) % MOD;
    }
}

long long convert (char *n) {
    long long number = 0;
    int ln = strlen (n);
    
    for (int x = 0; x < ln; x++) {
        number = number * 10;
        number = (number + (n[x] - '0')) % MOD;
    }
    
    return number % MOD;
}

int main () {
    char s_x[1111], s_y[1111];
    scanf ("%s %s", s_x, s_y);
    
    long long x, y, r;
    x = convert (s_x);
    y = convert (s_y);
    r = power (x, y);
        
    printf ("%lld\n", r);
}

c exponentiation modulus
person Ronald Sumbayak    schedule 05.10.2016    source источник
comment
K*x % x всегда равно 0. Установка K = pow(x, y-1) ничего не меняет.   -  person Cheers and hth. - Alf    schedule 05.10.2016
comment
Я думаю, вы, возможно, имели в виду pow(x,y)%z, а не pow(x,y)%x.   -  person Cheers and hth. - Alf    schedule 05.10.2016
comment
Извиняюсь. Опечатка. Отредактировано.   -  person Ronald Sumbayak    schedule 05.10.2016
comment
@RonaldSumbayak Вы должны уточнить диапазон z. Странно показывать диапазон x и y, но не z. По крайней мере, один ответ предполагал определенный диапазон, сильно упрощая задачу, и вы не уточнили, верно ли это предположение. Пожалуйста, отредактируйте свой вопрос, чтобы прояснить этот момент.   -  person anatolyg    schedule 05.10.2016
comment
Хорошо, спасибо. Отредактировано.   -  person Ronald Sumbayak    schedule 05.10.2016

Ответы (4)


arrow_upward
3
arrow_downward

Поскольку модульное возведение в степень используется так часто, для него существуют библиотеки. Ниже приведен пример, который считывает a, b и c и выводит b mod c с использованием GMP.

#include <stdio.h>
#include <gmp.h>

int main(void)
{
  mpz_t a, b, c, d;
  mpz_inits (a, b, c, d, NULL);
  printf ("a: ");
  mpz_inp_str (a, stdin, 10);
  printf ("b: ");
  mpz_inp_str (b, stdin, 10);
  printf ("c: ");
  mpz_inp_str (c, stdin, 10);
  mpz_powm (d, a, b, c); // compute d = a ^ b mod c
  gmp_printf ("a ^ b mod c = %Zd\n", d);
  return 0;
}

Скомпилируйте его с помощью -lgmp.

Кстати, ab ≡ ab mod Φ(c) (mod c), где Φ равно функция totient Эйлера

person v7d8dpo4    schedule 05.10.2016
comment
если a^b ≡ (a^(b mod Φ (c))) mod c, сделал ли (a^(b mod Φ (c))) mod c равным ((a mod c)^(b mod Φ (c ))) мод с? - person Ronald Sumbayak; 05.10.2016
comment
@RonaldSumbaak Да. Когда речь идет о целых числах по модулю с, а и (а по модулю с) совпадают. - person v7d8dpo4; 05.10.2016

arrow_upward
1
arrow_downward

Во-первых, я предполагаю, что z довольно мал (например, вписывается в long). Также обратите внимание, что

(x ^ y) % z = ((x % z) ^ y) % z

Так что можно конвертировать x так, как вы это делаете, единственная проблема - y. Удобно, что вы делаете только две вещи с y — вы делите его на два и проверяете остаток после деления на два. Обе эти вещи тривиальны, если вы представляете y в виде массива. Во-первых, для простоты переверните y так, чтобы младшая значащая цифра шла первой, а также сохраните цифры, а не цифровые символы в массиве (например, сохраните 5, а не «5»). Вы также можете рассмотреть возможность хранения более одной цифры в каждом элементе, но это только улучшит его на константу.

Теперь, чтобы проверить остаток, просто проверьте, делится ли первый элемент массива на два (число четное, если его младшая значащая цифра четная). Чтобы разделить на два, сделайте что-нибудь вроде:

for (int i = 0; i < y_len; ++ i) {
    if (i && y[i] % 2) y[i - 1] += 5;
    y[i] /= 2;
}
if (y_len && y[y_len - 1] == 0) -- y_len;

Включите это в свою программу power, и она будет работать нормально. Обратите внимание, что ваш метод power является логарифмическим по y, поэтому тот факт, что y может достигать 10^1000, не делает его неуправляемо медленным.

person Ishamael    schedule 05.10.2016
comment
Так вот как вычислить x^y? Или я ошибаюсь? Как насчет большой части int? - person Ronald Sumbayak; 05.10.2016
comment
Краткое изложение моего ответа: вам не нужно рассматривать x как bigint, можно использовать его по модулю z, как вы уже делаете. Вам действительно нужно рассматривать y как bigint, однако единственные две вещи, которые ваша процедура power делает с y, это %2 и /2, обе из которых тривиальны, если вы представляете y как массив цифр. - person Ishamael; 05.10.2016
comment
Чтобы уточнить: я предлагаю хранить y в массиве целых чисел, где каждый элемент хранит одну цифру. Например, если y равно 154, оно будет представлено в виде массива {4, 5, 1}. - person Ishamael; 05.10.2016
comment
Чтобы уточнить: как я сказал в конце, ваше решение уже хорошо с точки зрения скорости, ваше power логарифмично в y, поэтому оно будет работать быстро для y до 10^1000, поэтому единственное, что вам нужно исправить, это не возьмите y по модулю z, и для этого вам нужно представить его в виде массива цифр и реализовать деление и по модулю вручную, как описано в ответе - person Ishamael; 05.10.2016
comment
Итак, я должен рассматривать y как строку и выполнять n/2 с большой строкой int? Хорошо, я попробую. - person Ronald Sumbayak; 05.10.2016

arrow_upward
1
arrow_downward

Я предполагаю, что вы пытаетесь построить алгоритм обмена ключами Диффи-Хеллмана. Попробуйте импортировать библиотеку OpenSSL, а затем используйте ее функцию BN_mod_exp().

BN_mod_exp() вычисляет a в степени p по модулю m (r=a^p % m). Эта функция использует меньше времени и места, чем BN_exp().

Источник: https://www.openssl.org/docs/manmaster/crypto/BN_add.html

person Taha Paksu    schedule 05.10.2016

arrow_upward
0
arrow_downward

Благодаря объяснению @ v7d8dpo4 функции Эйлера Тотиент. Я отредактировал свой код следующим образом:

#define MOD z

long long power (long long k, long long n) {
    if (n == 1) return k;
    else {
        long long p = power (k, n/2);
        if (n % 2 == 0) return (p * p) % MOD;
        else return (((p * p) % MOD) * k) % MOD;
    }
}

long long convert (char *n, int mod) {
    long long number = 0;
    int ln = strlen (n);

    for (int x = 0; x < ln; x++) {
        number = number * 10;
        number = (number + (n[x] - '0')) % mod;
    }

    return number % mod;
}

int main () {
    char s_x[1111], s_y[1111];
    scanf ("%s %s", s_x, s_y);

    long long x, y, r;
    x = convert (s_x, MOD);
    y = convert (s_y, totient (MOD)); // totient (x) is Euler's Totient Function of x
    r = power (x, y);

    printf ("%lld\n", r);
}
person Ronald Sumbayak    schedule 29.10.2016