Факторизация, математика, fandom powered by wikia
Алгоритми факторизації Правити
Найбільш тривіальним алгоритмом факторизації чисел є повний перебір можливих дільників. Складність цього алгоритму дорівнює. # 961; -алгоритми Полларда має складність. Метод безперервних дробів. метод квадратичного решета і метод на основі еліптичних кривих мають складність .В даний час найефективнішим алгоритмом факторизації є метод решета числового поля зі складністю.
Питання про існування алгоритму факторизації з поліноміальною складністю на класичному комп'ютері є однією з важливих відкритих проблем сучасної теорії чисел. У той же час, для родинної завдання про розпізнаванні простоти числа існує поліноміальний рішення - тест простоти AKS.
Рішення завдання факторизації з поліноміальною складністю можливо на квантовому комп'ютері за допомогою алгоритму Шора.