Shorのアルゴリズムは、整数因数分解のための量子コンピューターアルゴリズムです。量子コンピューターではポリロガリズム（サブポリノミアル）時間で実行されますが、現在は整数因数分解のための多項式時間の古典的アルゴリズムは既知ではなく、そのようなアルゴリズムが存在するかどうかは不明です。

Shorのアルゴリズムは、ビットではなく量子ビット（Qubits）で動作するため、古典的なコンピューターで実行できません。抽象的には、量子ビットは2つの状態の重ね合わせにあると言われています - 測定時に特定の確率でどちらの状態を想定できます。対照的に、古典的なビットは、いつでも可能な2つの状態の1つを想定することができます。

このqubitのこのプロパティにより、量子コンピューターは複数のポイントで機能を同時にサンプリングできます。Shorのアルゴリズムは、この事実を使用して、モジュラー指数関数の期間を見つけます。クラシックコンピューターは関数の各ポイントを個別にサンプリングする必要があるため、このタスクを合理的な時間で完了することはできません。
Shor's algorithm is a quantum-computer algorithm for integer factorization. It runs in polylogarithmic (sub-polynomial) time on a quantum computer, while there is currently no known polynomial-time classical algorithm for integer factorization, and it is unknown whether such an algorithm exists.

Shor's algorithm cannot run on a classical computer since it operates on quantum bits (qubits) rather than bits. Abstractly, quantum bits are said to be in a superposition of two states - they can assume either state when measured, with a certain probability. In contrast, classical bits can only assume one of their two possible states at any given time. 

This property of the qubit allows quantum computers to sample functions in multiple points simultaneously. Shor's algorithm uses this fact to find the period of the modular exponentiation function, which can be used to factorize the modulous. Since a classical computer must sample each point in the function individually, it would not be able to finish this task in a reasonable time.