The C++ program incorrectly outputs the message

My program encrypts and decrypts the message according to Shamir's algorithm, one finally decrypted message does not converge with the input, they say that this problem may be related to encoding, however, I think that the problem is in the code and I cannot understand my mistake.

I tried to change the encryption type, instead of addition and subtraction, I did XOR, added array sorting, in case the problem is there, but it didn't help

#include <iostream>   
#include <cstdlib>   
#include <ctime>   
#include <vector>   
#include <string>   
#include <algorithm> // для функции sort 
using namespace std;
// Объявляем константы   
const int MAX = 1000;
const int PRIME = 31;
// Функция, вычисляющая степень числа по модулю   
int power(int x, unsigned int y, int p)
{
int res = 1; // Инициализируем результат   
x = x % p; // Берем остаток от деления x на p   
while (y > 0) {
// Если степень нечетная, умножаем результат на x   
if (y & 1)
res = (res * x) % p;
// Уменьшаем степень вдвое и удваиваем x   
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int main()
{
string message; // Объявляем переменную для сообщения   
cout << "Enter the message to be encrypted: ";
getline(cin, message); // Получаем сообщение от пользователя   
int n, k; // Объявляем переменные для количества ключей   
cout << "Enter the number of keys (n): ";
cin >> n;
cout << "Enter the number of keys required for decryption (k): ";
cin >> k;
// Генерируем случайный секретный ключ и коэффициенты   
int secretKey = rand() % PRIME;
vector<int> coefficients(k - 1);
for (int i = 0; i < k - 1; i++) {
coefficients[i] = rand() % PRIME;
}
// Генерируем ключи   
vector<int> keys(n);
for (int i = 1; i <= n; i++) {
keys[i - 1] = power(PRIME, i, MAX);
}
// Создаем части секретного сообщения   
vector<int> shares(n);
for (int i = 0; i < n; i++) {
int sum = secretKey;
for (int j = 0; j < k - 1; j++) {
sum += coefficients[j] * power(keys[i], j + 1, MAX);
}
shares[i] = sum;
}
// Пользователь выбирает ключи для расшифровки   
vector<int> selectedKeys(k);
cout << "Enter the keys to be used for decryption: ";
for (int i = 0; i < k; i++) {
cin >> selectedKeys[i];
if (selectedKeys[i] < 1 || selectedKeys[i] > n) { // проверка на правильность ввода ключей 
cout << "Invalid key. Please try again: ";
i--;
}
}
sort(selectedKeys.begin(), selectedKeys.end()); // сортировка выбранных ключей 
// Восстанавливаем секретное сообщение   
int secretMessage = 0;
for (int i = 0; i < k; i++) {
int num = shares[selectedKeys[i] - 1];
int denom = 1;
for (int j = 0; j < k; j++) {
if (i != j) {
num *= keys[selectedKeys[j] - 1];
denom *= keys[selectedKeys[j] - 1] - keys[selectedKeys[i] - 1];
}
}
secretMessage += num / denom;
}
// Шифруем и расшифровываем сообщение   
string encryptedMessage = "";
string decryptedMessage = "";
for (int i = 0; i < message.length(); i++) {
int val = message[i];
int encryptedVal = val ^ secretKey; // XOR-шифрование 
encryptedMessage += char(encryptedVal);
int decryptedVal = encryptedVal ^ secretMessage; // XOR-расшифрование 
decryptedMessage += char(decryptedVal);
}
// Выводим результаты на экран   
cout << "The secret key is: " << secretKey << endl;
cout << "The shares are: ";
for (int i = 0; i < n; i++) {
cout << shares[i] << " ";
}
cout << endl;
cout << "The decrypted message is: " << decryptedMessage << endl;
cout << "The encrypted message is: " << encryptedMessage << endl;
return 0;
}

Example output:

Enter the message to be encrypted: Hello World
Enter the number of keys (n): 6
Enter the number of keys required for decryption (k): 3
Enter the keys to be used for decryption: 3 2 1
The secret key is: 10
The shares are: 10302 26362 24222 15882 11342 22602
The decrypted message is: ┤ЩРРУ▄лУОРШ
The encrypted message is: Boffe*]exfn

Besides debugging I would suggest to add invariant checking, like assertions in various points. Also unit testing during development process helps a lot. Run your code with -fsanitize=undefined and check for any UBs, like integer overflows etc.

Actually running your code with sanitization shows error:

x86-64 clang 16.0.0
x86-64 clang 16.0.0
-std=c++20 -fsanitize=integer -fsanitize=undefined
Program returned: 0
Program stdout
The secret key is: 10
The shares are: 3048 6378 6008 3938 3168 5698 
The decrypted message is: ����
The encrypted message is: ofge
Program stderr
/app/example.cpp:92:21: runtime error: signed integer overflow: 2929128 * 791 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.cpp:92:21 in 

https://godbolt.org/z/b477shh1f

Changing line:

num *= keys[selectedKeys[j] - 1]);

to:

num = (num * keys[selectedKeys[j] - 1]) % MAX;

fixes it