Судебное отделение - Trial division

Пробное деление - самый трудоемкий, но самый простой для понимания алгоритм целочисленной факторизации . Основная идея, лежащая в основе тестов пробного деления, заключается в том, чтобы увидеть, можно ли целое число n , целое число, которое нужно разложить на множители, по очереди разделить на каждое число, которое меньше n . Например, для целого числа $n = 12$ единственными числами, которые делят его, являются 1, 2, 3, 4, 6, 12. Выбор только наибольших степеней простых чисел в этом списке дает $12 = 3 \times 4 = 3 \times 2. 2$ .

Пробное деление было впервые описано Фибоначчи в его книге Liber Abaci (1202).

Метод

Учитывая целое число n ( n означает «целое число, подлежащее факторизации»), пробное деление состоит из систематической проверки, делится ли n на любое меньшее число. Ясно, что имеет смысл тестировать факторы-кандидаты меньше n и в порядке от двух вверх, потому что произвольное n с большей вероятностью будет делиться на два, чем на три, и так далее. При таком порядке нет смысла проверять делимость на четыре, если число уже определено, что оно не делится на два, и так далее для трех и любого кратного трех и т. Д. Следовательно, усилия можно уменьшить, выбрав только простое число. числа в качестве возможных факторов. Кроме того, пробные коэффициенты не должны идти дальше, чем потому, что, если n делится на некоторое число p , то n = p × q, и если бы q было меньше p , n было бы обнаружено раньше как делимое на q или на простое число. коэффициент q . ${\ displaystyle \ scriptstyle {\ sqrt {n}}}$

Возможна определенная оценка простых множителей. Предположим, что $P i$ - это $i$ -е простое число, так что P ₁ = 2, P ₂ = 3, P ₃ = 5 и т. Д. Тогда последнее простое число, которое стоит проверить в качестве возможного множителя n, равно $P i,$ где $P 2 i + 1 > п$ ; равенство здесь означало бы, что $P i + 1$ является фактором. Таким образом, тестирования с 2, 3 и 5 достаточно до n = 48, а не только до 25, потому что квадрат следующего простого числа равен 49, а ниже n = 25 достаточно 2 и 3. Если квадратный корень из n является целым, то это множитель, а n - полный квадрат .

Пример алгоритма пробного деления, использующего последовательные целые числа в качестве пробных факторов, выглядит следующим образом (на Python ):

def trial_division(n: int) -> List[int]:
    """Return a list of the prime factors for a natural number."""
    a = []               # Prepare an empty list.
    f = 2                # The first possible factor.    
    while n > 1:         # While n still has remaining factors...
        if n % f == 0:   # The remainder of n divided by f might be zero.        
            a.append(f)  # If so, it divides n. Add f to the list.
            n //= f       # Divide that factor out of n.
        else:            # But if f is not a factor of n,
            f += 1       # Add one to f and try again.
    return a             # Prime factors may be repeated: 12 factors to 2,2,3.

Или в 2 раза эффективнее:

def trial_division(n: int) -> List[int]:
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
    # Only odd number is possible
    return a

Эти версии пробного разделения гарантированно найти коэффициент п , если есть один , так как они проверяют все возможные факторы из п - и если п простого числа, это означает испытание факторы вплоть до п . Таким образом, если алгоритм находит только один множитель, n, это доказывает, что n является простым числом . Если найдено более одного фактора, то n - составное целое число . Более выгодный с вычислительной точки зрения способ сказать это: если любое простое число, квадрат которого не превышает n, делит его без остатка, то n не является простым.

Ниже представлена версия C ++ (без квадрата f)

template <class T, class U>
vector<T> TrialDivision(U n)
{
    vector<T> v; T f;
    f = 2;
    while (n % 2 == 0) { v.push_back(f); n /= 2; }
    f = 3;
    while (n % 3 == 0) { v.push_back(f); n /= 3; }
    f = 5;
    T ac = 9, temp = 16;
    do {
        ac += temp; // Assume addition does not cause overflow with U type
        if (ac > n) break; 
        if (n % f == 0) {
            v.push_back(f);
            n /= f;
            ac -= temp;
        }
        else { 
            f += 2;
            temp += 8;
        }
    } while (1);
    if (n != 1) v.push_back(n);
    return v;
}

Скорость

В худшем случае пробное разделение - трудоемкий алгоритм. Для n- значного числа a с основанием 2 , если оно начинается с двух и работает только до квадратного корня из a , алгоритм требует

{\ displaystyle \ pi (2 ^ {n / 2}) \ приблизительно {2 ^ {n / 2} \ over \ left ({\ frac {n} {2}} \ right) \ ln 2}}

пробные деления, где обозначает функцию подсчета простых чисел, количество простых чисел меньше x . При этом не учитываются накладные расходы на проверку простоты для получения простых чисел в качестве факторов-кандидатов. Полезная таблица не обязательно должна быть большой: P (3512) = 32749, последнее простое число, которое умещается в шестнадцатиразрядное целое число со знаком, и P (6542) = 65521 для беззнаковых шестнадцатиразрядных целых чисел. Этого было бы достаточно, чтобы проверить простоту чисел до 65537 ² = 4 295 098 369. Подготовка такой таблицы (обычно с помощью сита Эратосфена ) имела бы смысл только в том случае, если бы нужно было проверить много чисел. Если вместо этого используется вариант без проверки на простоту, а просто деление на каждое нечетное число, меньшее квадратного корня, n- значное число по основанию 2 a , простое или нет, это может занять примерно до: ${\ displaystyle \ scriptstyle \ pi (x)}$

{\ Displaystyle 2 ^ {п / 2}}

В обоих случаях необходимое время растет экспоненциально с разрядами номера.

Тем не менее, это вполне удовлетворительный метод, учитывая, что даже самые известные алгоритмы имеют экспоненциальный рост во времени. Для выбрано равномерно случайным образом из целых чисел заданной длины, существует 50% вероятность того, что 2 является фактором и 33% шанс, что 3 является фактором , и так далее. Можно показать, что 88% всех положительных целых чисел имеют множитель меньше 100 и 92% имеют множитель меньше 1000. Таким образом, при столкновении с произвольно большим a стоит проверить делимость на маленькие простые числа, поскольку для , в базе-2 . ${\ displaystyle a = 1000}$ ${\ displaystyle n = 10}$

Однако для многозначных чисел, не имеющих делителей в малых простых числах, могут потребоваться дни или месяцы, чтобы разложить их с пробным делением. В таких случаях используются другие методы, такие как квадратное решето и решето общего числового поля (GNFS). Поскольку эти методы также имеют суперполиномиальное время роста, практический предел в n цифр достигается очень быстро. По этой причине в криптографии с открытым ключом значения для a выбираются так, чтобы иметь большие простые множители аналогичного размера, так что они не могут быть разложены на множители каким-либо общеизвестным методом в полезный период времени на любой доступной компьютерной системе или компьютерном кластере, таком как суперкомпьютеры и компьютерные сети . Наибольшее число, подвергшееся факторингу, - это RSA-250 , 250-значное число, использующее GNFS и ресурсы нескольких суперкомпьютеров. Срок эксплуатации - 2700 основных лет.

использованная литература

Чайлдс, Линдси Н. (2009). Конкретное введение в высшую алгебру . Тексты для бакалавриата по математике (3-е изд.). Нью-Йорк, штат Нью-Йорк: Springer-Verlag . ISBN 978-0-387-74527-5. Zbl 1165.00002 .
Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа. Вычислительная перспектива (2-е изд.). Нью-Йорк, штат Нью-Йорк: Springer-Verlag . ISBN 0-387-25282-7. Zbl 1088.11001 .

внешние ссылки

Быстрый калькулятор основного коэффициента JavaScript с использованием пробного деления . Может обрабатывать числа до 2 ⁵³
Пробный отдел по Java, C и JavaScript (на португальском языке)

Languages

In other projects

Судебное отделение - Trial division

СОДЕРЖАНИЕ

Метод

Скорость

использованная литература

внешние ссылки