в общем, это пока считается нерешенной математической проблемой
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Теория чисел, ... |
| Автор: __vi 4.2.2004, 23:17 |
| В мапле есть функции: divisors и tau; divisors - находит все делители числа. tau - говорит сколько у числа делителей. Каков их алгоритм? Ведь это не просто перебор, типа: (n%m == 0) ? print(m):isdiv(n, m+1); Обе функции работают очень быстро даже с огромными числами 10^96 - за 2 секунды при 400MHz. |
| Автор: acp 5.2.2004, 01:03 |
| Если бы была известна какая-то математическая функция нахождения делителей, то не искали бы простые числа так долго. Перебор, скорее всего. |
| Автор: val 5.2.2004, 11:06 |
| Мне кажется, тут используются алгоритмы разложение числа на множители... |
| Автор: @lex 5.2.2004, 12:23 | ||||
| хоть и занимаюсь математикой, но именно с этой проблемой не сталкивался.
хочу заметить, что даже если используется перебор(что на мой взгляд маловероятно, все таки алгоритмы поиска делителей числа существуют), то достаточно рассматривать числа p : {p<=(sqrt(n)+1) && p-простое} где n - заданное число(делители которого мы ищем) ведь вполне логичный подход: если n%k=0 && k=i*j => n%i=0 && n%j=0 такой алгоритм называется решетом Эротосфена.
а это вроде как и есть поиск всех делителей числа?! правда, вероятно, когда мы разлогаем число на множители мы еще считаем кратность каждого делителя. |
| Автор: maxim1000 5.2.2004, 14:26 |
| есть один из видов цифровой подписи, который основан на том, что нельзя очень большое число быстро разложить на множители (правда, не знаю, какие там порядки фигурируют) в общем, это пока считается нерешенной математической проблемой |
| Автор: RSA 19.2.2004, 21:05 |
| Действительно, быстрых алгоритмов разложения на множители не существует. Но есть алгоритмы, позволяющие это делать гораздо быстрее, чем решето эратосфена. Конечно, они и более трудные для понимания и обоснования. Например, можно использовать т.н. N+1 и N-1 методы разложения. |
| Автор: Mal Hack 19.2.2004, 21:11 |
| 1. Даже если идет перебор, то он перебирает только до половины числа. Вот уже в два раза сократили. 2. Потом опускаются сразу такие варианты когда делится не будет, например, вы видели, чтоб на *5 делилось число с последней цифрой 1. Э таких случаев - очень много. 3. Помоему в математике была такая фишка, что число делится на 3 если сумма его цифр делится на 3... Вот тут можно еще выкинуть... |
| Автор: RSA 19.2.2004, 21:29 |
| Это все мелочи. Алгоритмы, применяемые на практике для больших чисел далеко ушли от этих простых методов. |
| Автор: Mal Hack 19.2.2004, 21:36 |
| RSA, но они основанны на простых методах и во многом их повторят... |
| Автор: Chingachguk 20.2.2004, 06:07 |
| __vi Я тоже не силен в этой математике. Согласен с рассуждениями RSA. В целом. Если тебе нужно знать, как она это делает, то можно посмотреть ее (дизассемблировать) или немного прочесть про разные методы получения делителей. В последнем случае ты должен прочесть что-то типа: метод такой-то имеет временную сложность порядка 2^n, где n-число бит (например !!!). Далее ты делаешь такой опыт: подаешь ему на вход числа с разным числом битов (интересно также подать только простые числа - если она сможет сделаь их быстро, это косвенный признак качества). И записываешь время. В результате у тебя будет экспериментальная зависимость времени обсчета от числа бит. Видимо, так можно получить тип алгоритма. |
| Автор: RSA 20.2.2004, 08:15 |
| С вероятностью 95 процентов Мапл использует вероятностные алгоритмы нахождения делителей, так как они обычно самые быстрые в теории чисел. Поэтому сложность этих алгоритмов может сильно варьироваться. И у всех таких алгоритмов есть зависимость не только от величины числа, которое мы разлагаем, но больше от величины ее делителей. То есть, число, у которого много небольших делителей разложится на порядок быстрее, чем то, которое есть произведение двух больших простых чисел. Кстати, в для "числа порядка 10^96 за 2 секунды" наверняка имеет место первый случай. Иначе за 2 секунды оно бы не разложилось. А чтобы понять, как работают такие алгоритмы, нужно для начала освоить пару-другую умных книжек по алгебре и теории чисел. |