Факторизация чисел вида x^a + b, где x простое число

Мне нужно рассчитать простую факторизацию больших чисел, под большими числами я подразумеваю диапазон 10 ^ 100.

Я получаю ввод a[0] ‹= 10^5 (простые множители которого я уже вычислил с помощью сита и других оптимизаций). После этого я получаю ряд входных данных a[1], a[2], a[3] в диапазоне 2 ‹= a[i] ‹= 10^5. Мне нужно рассчитать продукт и получить коэффициенты нового продукта. У меня есть следующая математика

Пусть X будет данными в памяти, и X может быть представлен как:

X = (p[0]^c1)(p[1]^c2)(p[2]^c[3]) .... где p[i] — его простые множители. Поэтому я сохраняю это как,

A[p[0]] = c1, A[p[1]] = c2.... поскольку p[i] ‹= 100000, это работает очень хорошо.

и по мере поступления нового числа я просто добавляю мощность простых чисел нового числа в A.

Так что это работает очень хорошо, а также достаточно быстро. Сейчас думаю оптимизировать пространство и компенсировать это снижением эффективности времени.

Итак, если я могу представить любое число P как x ^ a + b, где x - простое число. Могу ли я его факторизовать? P явно не помещается в память, но 2 ‹= x, a, b ‹= 100000? Или есть ли другой возможный метод, который сэкономит мне пространство A? Я согласен с более медленным алгоритмом, чем приведенный выше.


algorithm dynamic-programming primes prime-factoring
person Community    schedule 02.06.2017    source источник
comment
Если ваше целевое число, которое нужно разложить на множители, является результатом умножения многих известных a[i], вам не нужно изобретать какую-либо другую форму. Просто факторизируйте каждый a[i] и вычислите степень простого числа (показатель степени), складывая их, как вы это делали (почему вы хотите изменить текущий метод?). Вы можете использовать более компактный массив A (степени простых чисел) - существует только четная степень простого числа 2, поэтому вы можете перевести каждое простое число ‹ 10^5 в этот простой индекс в массиве A (A[4], A[6], A [8] ... всегда будет 0, если фактор a[i]). x^a+b - это общая форма, которую не легче учитывать, а сложнее.   -  person osgx    schedule 02.06.2017

Ответы (2)


arrow_upward
2
arrow_downward

Я не думаю, что представление числа в виде xa + b с простым числом x упрощает факторизацию .

Факторизация стозначных чисел в наши дни не так уж и сложна. Хороший персональный компьютер с большим количеством ядер и хорошим квадратичным ситом может факторизовать большинство стозначных чисел примерно за день, хотя вы должны знать, что стозначные числа находятся на пределе того, что разумно использовать для факторизации на настольном компьютере. Взгляните на программу Джейсона Пападопулоса msieve — передовую программу факторизации.

person user448810    schedule 02.06.2017

arrow_upward
0
arrow_downward

Во-первых, вам лучше посчитать на бумаге (возможно, возможны некоторые упрощения, я не знаю...).

Затем вам нужно использовать некоторую библиотеку арифметики произвольной точности (она же bignums или bigints). Я рекомендую GMPlib, но они другие.

См. также этот ответ.

person Basile Starynkevitch    schedule 02.06.2017
comment
Поскольку числа произвольны, я не думаю, что есть много упрощений. И я бы предпочел не использовать эти библиотеки bigint, а попытаться решить эту проблему на как можно более низком уровне. Поскольку я почти уверен, что хранить весь продукт не нужно. - person ; 02.06.2017
comment
Почему вы не хотите использовать библиотеки bigint? Вы не сможете сделать лучше, чем они, и вы сделаете намного хуже. - person Basile Starynkevitch; 02.06.2017