Цифровой компьютер, как это общепринято считать, является эффективным универсальным вычислительным устройством. Также считается, что он способен воспроизвести работу любого физического вычислительного устройства, причем требуемое для этого время возрастет не более, чем на полиномиальный множитель. Однако это не так, если принять в рассмотрение квантовую механику. В данной статье рассматриваются разложение целых чисел на простые множители и нахождение дискретных логарифмов. Хорошо известно, что обе эти проблемы являются сложными для классического компьютера и являются основой различных предлагаемых криптографических систем. В работе предлагаются эффективные алгоритмы для решения этих двух проблем на квантовом компьютере. Эти алгоритмы являются полиномиальными по числу шагов по отношения к размеру входного слова, другими словами, по отношению к количеству цифр, содержащихся в слове, которое необходимо факторизовать.