В мапле есть функции: divisors и tau;
divisors - находит все делители числа.
tau - говорит сколько у числа делителей.
Каков их алгоритм? Ведь это не просто перебор, типа: (n%m == 0) ? print(m):isdiv(n, m+1);
Обе функции работают очень быстро даже с огромными числами 10^96 - за 2 секунды при 400MHz.

Если бы была известна какая-то математическая функция нахождения делителей, то не искали бы простые числа так долго.
Перебор, скорее всего.

Мне кажется, тут используются алгоритмы разложение числа на множители...

хоть и занимаюсь математикой,
но именно с этой проблемой не сталкивался.

Цитата

Перебор, скорее всего

хочу заметить, что даже если используется перебор(что на мой взгляд маловероятно, все таки алгоритмы поиска делителей числа существуют), то достаточно
рассматривать числа
p : {p<=(sqrt(n)+1) && p-простое}
где n - заданное число(делители которого мы ищем)
ведь вполне логичный подход:
если n%k=0 && k=i*j => n%i=0 && n%j=0
такой алгоритм называется решетом Эротосфена.

Цитата

Мне кажется, тут используются алгоритмы разложение числа на множители

а это вроде как и есть поиск всех делителей числа?!
правда, вероятно, когда мы разлогаем число на множители
мы еще считаем кратность каждого делителя.

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

Действительно, быстрых алгоритмов разложения на множители не существует. Но есть алгоритмы, позволяющие это делать гораздо быстрее, чем решето эратосфена. Конечно, они и более трудные для понимания и обоснования. Например, можно использовать т.н. N+1 и N-1 методы разложения.

1. Даже если идет перебор, то он перебирает только до половины числа. Вот уже в два раза сократили.
2. Потом опускаются сразу такие варианты когда делится не будет, например, вы видели, чтоб на *5 делилось число с последней цифрой 1. Э таких случаев - очень много.
3. Помоему в математике была такая фишка, что число делится на 3 если сумма его цифр делится на 3...
Вот тут можно еще выкинуть...

Это все мелочи. Алгоритмы, применяемые на практике для больших чисел далеко ушли от этих простых методов.

RSA, но они основанны на простых методах и во многом их повторят...

__vi

Я тоже не силен в этой математике. Согласен с рассуждениями RSA. В целом.

Если тебе нужно знать, как она это делает, то можно посмотреть ее (дизассемблировать) или немного прочесть про разные методы получения делителей.

В последнем случае ты должен прочесть что-то типа: метод такой-то имеет временную сложность порядка 2^n, где n-число бит (например !!!).

Далее ты делаешь такой опыт: подаешь ему на вход числа с разным числом битов (интересно также подать только простые числа - если она сможет сделаь их быстро, это косвенный признак качества). И записываешь время. В результате у тебя будет экспериментальная зависимость времени обсчета от числа бит. Видимо, так можно получить тип алгоритма.

С вероятностью 95 процентов Мапл использует вероятностные алгоритмы нахождения делителей, так как они обычно самые быстрые в теории чисел. Поэтому сложность этих алгоритмов может сильно варьироваться.
И у всех таких алгоритмов есть зависимость не только от величины числа, которое мы разлагаем, но больше от величины ее делителей. То есть, число, у которого много небольших делителей разложится на порядок быстрее, чем то, которое есть произведение двух больших простых чисел. Кстати, в для "числа порядка 10^96 за 2 секунды" наверняка имеет место первый случай. Иначе за 2 секунды оно бы не разложилось.
А чтобы понять, как работают такие алгоритмы, нужно для начала освоить пару-другую умных книжек по алгебре и теории чисел.