Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Пусть есть N, являющееся произведением двух простых p,q... 11.06.04 17:21 Число просмотров: 3623
Автор: RElf <M> Статус: Member
|
> Во-первых, алгоритм может работать без таблиц, т.к. он > годен для любых (не только простых) чисел.
Пусть есть N, являющееся произведением двух простых p,q примерно равных p~=sqrt(N)/2 и q~=2*sqrt(N).
В Вашем методе вы будете спускаться по b от sqrt(N) до p, и на это потребуется около sqrt(N)/2 шагов. Идаже если Вы будете спускаться только по простым, то потребуется порядка sqrt(N)/log(N) шагов. А теперь подставьте, например, N=2^1024 и убедитесь, что Ваш метод требует экспоненциального (от log(N)) времени и практически непригоден.
|
|
|