Алгоритм

← →
ArtemESC © (2005-10-09 15:54) [0]

Доброго времени суток...
Хочу составить эффективный по времени алгоритм
разложения числа на простые самножители,
может есть готовые решения?

← →
Джо © (2005-10-09 15:54) [1]

> Хочу составить

и

> может есть готовые решения?

как-то не состыковуется, имхо.

← →
Anatoly Podgoretsky © (2005-10-09 16:03) [2]

Трудновато будет создать новый алгоритм, тут уже все застолблено. Но пусть пробует, может нобелевку получит.

← →
DillerXX © (2005-10-09 16:04) [3]

http://algolist.manual.ru/maths - тебе туда

← →
partizan (2005-10-09 16:12) [4]

Несуществует такого алгоритма, а
если ты его составиш - сможеш без труда взломать RSA

← →
SergP. (2005-10-09 19:47) [5]

> partizan (09.10.05 16:12) [4]
> Несуществует такого алгоритма, а
> если ты его составиш - сможеш без труда взломать RSA

Как это не существует?
Может и малоэффективные,но существуют...

← →
SergP. (2005-10-09 20:01) [6]

Например, вот на скорую руку набросал:

procedure searchmull(a:integer); var i,max:integer; begin max:=trunc(sqrt(a)); for i:=2 to max do if (a mod i)=0 then begin searchmull(a div i); searchmull(i); exit; end; form1.Memo1.Lines.Add(inttostr(a)); end; Неэффективный конечно, так как на скорую руку... Но алгоритм.

← →
GuAV © (2005-10-09 20:46) [7]

http://www.fastcode.dk/fastcodeproject/fastcodeproject/30.htm

← →
GuAV © (2005-10-09 20:48) [8]

А, не то, сабж невнимательно глянул. Но и эту задачку им можно предложить.

← →
partizan (2005-10-09 20:53) [9]

> Как это не существует?
> Может и малоэффективные,но существуют...

Так я про эффективный говорю. Эффективного не существует

← →
SergP. (2005-10-09 21:01) [10]

> Так я про эффективный говорю. Эффективного не существует

Ну эффективность - это понятие растяжимое...

Слышал, что несколько лет назад был придуман эффективный эвристический алгоритм. Для огромного большинства длинных чисел он быстро выдает правильное решение. Чисел, для которых алгоритм не совсем применим мало (хотя они есть). Так что теперь криптосхемы типа RSA не являются такими надежными, как ранее.

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

Вопрос в том, ограничено ли сверху заданное число (для которого ищем разложение)?

http://algolist.manual.ru/maths/teornum/factor/

<offtop>
Придумав алгоритм в этой ветке нобелевку поровну поделим или пропорциональну числу постов? :)
</offtop>

> А если хранить список простых чисел константно в теле программы,
> то думаю можно и быстренько находить.

Разумно, но возникает вопрос оптимального хранения и выборки.

Взято из http://algolist.manual.ru/maths/teornum/factor/trial.php :

Заметки к практической реализации.

Предположим, что мы используем таблицу простых до 500"000 ( 41"538 простых чисел ). Простое деление при таком ограничении никогда не занимает больше нескольких секунд на современных компьютерах. Причем хранить можно только разности между простыми (или их половины), а не сами числа, так как p[k] - p[k-1] можно поместить в 1 байт вместо четырех, если p[k] <= 1"872"851"947 ( а половину этой разности - если p[k] <= 1"999"066"711"391).

Кроме того, не нужно делать больше делений после того, как кончится таблица простых, так как есть лучшие методы для удаления малых делителей.

И, наконец, заметим, что нет необходимости в вычислении L := [ N1/2 ] во время инициализации, так как проверка d >= L в шаге 4 может быть заменена на q <= L, где q - евклидово частное при делении N на d : N = q * d + r, обычно вычисляемое одновременно с остатком в шаге 3.

Вот потому и интересно мне, есть ли верхняя грань для заданного числа?

Алгоритм Найти похожие ветки