Си. Как разложить число длинною в 100 символов на простые множители за 1-2 секунды?
Необходимо разложить число длинною ~100 символов на простые множители. При вводе нуля сканирование чисел останавливается.
Пример ввода: 932865073719992059629773513614789388266580305083920591925740371392254317064584855785088915745761 0
Пример вывода: Prime factor of 932865073719992059629773513614789388266580305083920591925740371392254317064584855785088915745761 is: 995663^8 x 995669^8
Я смог реализовать это с числами меньшей длины с помощью решета Эратосфена, signed long long и циклов for:
int main(int argc, char *argv[]){
int ch = 0;
signed long long int num;
int div = 2;
while ((ch = scanf("%lli", &num)) == 1)
{
if (num > 0){
printf("Prime factor of %lli is:\n", num);
if (num == 1){
printf("%lli", num);
}
while (num > 1){
int tmp = 0;
long int limit = 1000000;
int prime[limit+1];
int arrprime[tmp];
for(int i = 1; i <= limit; i++){
prime[i] = i;
}
for(int i = 2; i*i <= limit; i++){
if (prime[i] != -1){
for(int j = 2*i; j<= limit; j += i){
prime[j] = -1;
}
}
}
for (int i = 0; i < limit; i++){
if (prime[i] > 0){
arrprime[tmp] = prime[i];
tmp++;
}
}
int power = 0;
for (int i = 1; i < tmp; i++){
while ((num % div) == 0){
num /= div;
power++;
if (num == 1){
break;
}
else{
continue;
}
}
if (power > 0){
printf("%d", div);
if (power > 1){
printf("^%d", power);
}
if (num > 1){
printf(" x ");
}
}
div++;
}
}
printf("\n");
div = 2;
}
else if(num == 0){
return 0;
}
}
}
Но в случае с числами длинною в 100 символов использовать решето не получится из-за слишком долгой обработки (программа должна выводить результат примерно за 1-2 секунды).
Ответы (2 шт):
Для очень больших чисел, как у вас, факторизацию эффективно коротким С/С++ алгоритмом не напишешь.
Если можно использовать сторонние библиотеки, советую GMP-ECM, это C-библиотека в исходных кодах, она реализует самый быстрый (как мне известно) способ факторизации больших чисел, использующий Эллиптические Кривые.
GMP-ECM по умолчанию доступна в Linux дистрибутивах установкой пакета sudo apt install gmp-ecm.
Под Windows можно скачать версию по этой ссылке, там же доступны и другие программы под Windows, использующие эффективные алгоритмы факторизации.
Если задачи нет именно в исходниках C/C++ использовать библиотеку, а задача просто факторизовать заданное число, то досточно использовать из GMP-ECM пакета готовую программу ecm.exe. Для её использования запускаем ecm 1000000, здесь 1000000 это B1-граница, эта граница может быть задана любой, чем она больше тем больше перебор по времени и больше шанс найти факторизацию. У меня для 1000000 границы перебор для 100-значного входного числа занимает в районе 20 сек. Если не найдена факторизация, то требуется перезапустить программу с большей границе, например в 10 раз большей и т.д. увеличивать постепенно.
После запуска ecm программы будет открыта интерактивная консоль, просто вводим число и жмём Enter. Через некоторое время вычислений будет выведено Step 1 took N ms, затем ещё позже Step 2 took M ms. Это означает что все 2 стадии выполнены, если при этом на консоль не вывело делителей числа, значит введённая граница при запуске программы (1000000 в примере выше) слишком мала, не найдены делители, либо их не существует, нужно увеличивать границу (на каждом этапе раз в 10 увеличивать).
Если важно именно иметь исходный С/С++ код, то библиотека GMP-ECM поставляется в исходниках, по этой ссылке описано как скачать исходники используя SVN. Эти исходные коды у меня на Windows 64-bit MSVC 2019 успешно скомпилировались в ecm.exe, после небольших настроек и доработок.
Если нужна мною скомпилированная версия ecm.exe, собранная из самых свежих исходников из SVN, это Release 64-bit вариант, собранный на MSVC 2019 Community, под Windows, для получения этой версии запустите в командной строке (требуется установленный Python):
python -c "import base64, urllib.request; d = urllib.request.urlopen('https://pastebin.com/raw/wcMFrqna').read(); d = base64.b64decode(d); f = open('ecm_pass_1.7z', 'wb'); f.write(d); f.close()"
эта команда выше скачает файл ecm_pass_1.7z из PasteBin сервиса, это 7-Zip архив с паролем 1, содержащий программу. Проверка на вирусы.
Кстати по ссылке RSA Numbers сообщается что 100-значное число уже было факторизовано после нескольких дней распределённых вычислений (параллельные вычисления на большом количестве компьютеров), так что сомнительно что любое 100-значное число можно было бы факторизовать за 1-2 секунды на одном комьютере, вряд ли даже самые быстрые алгоритмы способны на это. Кстати, самое короткое из не факторизованных чисел RSA это 260-значное RSA-260.
Если требуется доказать (или опровергнуть) простоту числа, но не требуется найти сами делители, то одна из самых эффективных (быстро вычисляющих) готовых программ для этого это популярная программа Primo, она поставляется только под Linux, и насколько я знаю, имеет закрытые исходники. Например эта программа за долю секунды сообщает, что число RSA-260 составное, т.к. не проходит тест Ферма с основанием 2, но программа при этом конечно не сообщает самих делителей.
Хотелось бы добавить, что сам по себе тест Ферма весьма прост в реализации и может быть написан даже новичком в любом языке программирования.
Идея такова: нет, вы не можете сказать, на какие делители разлагается такое то число. Но можете с очень высокой вероятностью (а при вероятности порядка "единица минус единица, деленная на десять в тридцатой степени" = 1-1/10**30 это становится гораздо более вероятно, чем точное вычисление с учетом возможных аппаратных ошибок) сказать, что такое то число - простое.
Сам по себе тест Ферма формулируется так: Если p простое и a не делится на p, то a^(p−1) ≡ 1 (mod p)