New offer! Get 30% off one whole year of Unlimited learning. Subscribe for just £249.99 £174.99. New subscribers only. T&Cs apply

# Basic Goal: Factoring

The goal for this activity is to understand Shor's algorithm for factoring large numbers in polynomial time.

In computer science, the two most important classes of problems are P and NP. The P class stands for polynomial, that is, we can solve the problem in order of (N) to the (k) time ((O(N^k))) where (N) represents the size of the problem and (k) is some constant number. NP is non-deterministic polynomial.

The best known solutions to problems in NP and believed to be outside of P are exponential. Of course, any exponential grows very fast, so problems that take exponential time are considered to be hard to solve. So what about factoring, where does it fall?

Factoring is, so far as we know, harder than polynomial, but not as hard as exponential. Because Shor’s algorithm shows that a quantum computer can factor in polynomial time, it is exciting for three big reasons:

1. the problem is important;
2. the performance gains are exciting; and
3. techniques are exciting and valuable.

# 基本目標：素因数分解

NPの問題の解法は指数関数的であり、Pに属さないと考えられていることはよく知られています。 言うまでもなく、どの指数関数も非常に速く値が増大していくため、指数関数的な時間を要する問題の解を計算することは一般的には困難であると考えられています。では、因数分解はどのクラスに属するのでしょうか？

1. 問題そのものが重要
2. 性能の向上が魅力的
3. 新しい技術の確立