|
|
Какие способы применяются для факторизации числа? И почему сложно факторизовать? |
☑ |
|
0
DirecTwiX
02.03.13
✎
13:23
|
Кроме простого перебора есть что-нибудь?
Почему сложно факторизовать большие числа? Проблема в долгом переборе? Или в долгом делении?
|
|
|
1
NS
02.03.13
✎
13:25
|
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора (класс BQP).
|
|
|
2
DirecTwiX
02.03.13
✎
13:36
|
Спасибо!
Был на этой странице, но не дочитав первого абзаца, перешёл по гиперссылке)
|
|
|
3
NS
02.03.13
✎
13:38
|
(2) Вопрос не совсем понятен.
Если взять 100 значное число, и тупо проверять делимость на числа до корня из него - нужно количество операций из 99 знаков.
Вопрос в (0) то в чем?
|
|
|
4
NS
02.03.13
✎
13:43
|
виноват, из 50
|
|
