# Shor¶

`Shor(quantum_instance=None)`

Bases: `object`

The deprecated Shor’s factoring algorithm.

The Shor class is deprecated as of Qiskit Terra 0.22.0 and will be removed no sooner than 3 months after the release date. It is replaced by the tutorial at Shor (opens in a new tab)

Shor’s Factoring algorithm is one of the most well-known quantum algorithms and finds the prime factors for input integer $N$ in polynomial time.

Adapted from https://github.com/ttlion/ShorAlgQiskit (opens in a new tab)

See also https://arxiv.org/abs/quant-ph/0205095 (opens in a new tab)

**Parameters**

**quantum_instance** (`Union`

[`Backend`

, `QuantumInstance`

, `None`

]) – Quantum Instance or Backend

## Methods

### construct_circuit

`Shor.construct_circuit(N, a=2, measurement=False)`

Construct quantum part of the algorithm.

**Parameters**

**N**(`int`

) – The odd integer to be factored, has a min. value of 3.**a**(`int`

) – Any integer that satisfies 1 < a < N and gcd(a, N) = 1.**measurement**(`bool`

) – Boolean flag to indicate if measurement should be included in the circuit.

**Return type**

**Returns**

Quantum circuit.

### factor

`Shor.factor(N, a=2)`

Execute the algorithm.

The input integer $N$ to be factored is expected to be odd and greater than 2. Even though this implementation is general, its capability will be limited by the capacity of the simulator/hardware. Another input integer $a$ can also be supplied, which needs to be a co-prime smaller than $N$ .

**Parameters**

**N**(`int`

) – The odd integer to be factored, has a min. value of 3.**a**(`int`

) – Any integer that satisfies 1 < a < N and gcd(a, N) = 1.

**Returns**

results of the algorithm.

**Return type**

**Raises**

**ValueError**– Invalid input**AlgorithmError**– If a quantum instance or backend has not been provided

### modinv

`static Shor.modinv(a, m)`

Returns the modular multiplicative inverse of a with respect to the modulus m.

**Return type**

`int`

## Attributes

### quantum_instance

Returns quantum instance.

**Return type**

`Optional`

[`QuantumInstance`

]