Blog

Categories:

16. 3. 2026

Security Cryptography

Comparing Digital and Quantum Computers, Part 6: Shor's Algorithm

Everyone in the IT world is wondering how big a threat quantum computers pose to cryptography and how to deal with the problem. This series of articles tries to explain the problem in a popular way. After explanation of how quantum computer work is it important to understand how Shor's algorithm work.

Shor's algorithm

Although Shor's algorithm is relatively simple compared to other algorithms in the quantum zoo (more at https://quantalgorithmzoo.org/), its implementation differs slightly for use with factorization and discrete logarithm. In the examples used, the rule is used for the number of logical qubits for factorization $2 \bullet n + 5$ , for the attack on the discrete logarithm $2 \bullet n + 10$ and for the number of gates in both cases $O\left( n^{3} \right)$ . Due to developments in the field of algorithmization, the rules mentioned may not correspond to the current level of knowledge, but the information given is sufficient for estimation.

Factorization

For factorization, Shor's algorithm with an input and a single register is used. Both the input and the register must have the length of the key. In a schematic drawing, this algorithm looks like this:

To understand how the individual logic gates are connected and their significance for the calculation, it is necessary to explain this connection in much more detail. Before starting, it is necessary to encode part of the public key, i.e. the number n and a randomly chosen value a (not co-efficient of n ) into the circuit connection. At the beginning, all values of the control register (x) are superposed using Hadamard gates, i.e. a superposition of all possible exponents, and the working register is set to a defined state. Subsequently, combinations of CNOT and CCNOT gates are used for controlled sequences of modular multiplication $a^{x}\ mod\ N$ . Each qbit of the exponent controls the entire set of reversible modular multiplication implemented within the network of CNOT and CCNOT gates. The CNOT and CCNOT gates also transform the intermediate results into the working register. This entire process takes place in a superposition of states. After the modular exponentiation is completed, both registers are quantumly linked and a quantum Fourier transform is applied to the control register to determine the period. This converts the periodic phase structure into a measurable result that can be later read and evaluated in post-processing from the control register. QFT itself uses Hadamard gates, controlled phase rotation gates (CP, CR _k ) and SWAP gates to adjust the order of the qubits. The working register contains the contributions of the control register and can be discarded at the end of the calculation.

To attack the discrete logarithm problem (DLP), Shor's algorithm is used, but this time with an input and two registers. Both the input and both registers must have the length of the key. However, the connection differs between the attack on pure DLP, i.e. DH and DSA (multiplicative group), and the attack on ECDLP, i.e. ECDH and ECDSA (additive group). For the pure DLP problem, the following scheme is used.

And for ECDLP the scheme is slightly different.

Real connections are again more complicated. The explanation of the difference from factorization and the actual analysis of the algorithm run are combined into one paragraph, because only the computational part differs. This is listed separately as the difference between DLP and ECDLP.

Before starting, it is necessary to encode important parameters into the circuit. For DLP, this means the generator g and the modulus p, for ECDLP the starting point G and the curve parameters. At the beginning, all values of independent control registers (a) and (b) are superposed using Hadamard gates. This means that all possible states are superposed separately for each register. The registers represent the unknown values sought. The working register is set to the initial state. Gradually, values for the necessary group operations are created from it (excitation in the multiplicative group for DLP, addition and doubling in the additive group for ECDLP). Thanks to this, the superposition of all values corresponding to individual operations with the generator is stored in the working register, i.e. the possible values of its powers for DLP or curve points for ECDLP. After creating a quantum connection between the control and working registers, a quantum Fourier transform is applied to the control registers to determine the period. This converts the periodic structure of the phases into a measurable result, which can later be read and evaluated in post-processing. The evaluation is performed over the control registers. QFT itself uses Hadamard gates, controlled phase rotation gates (CP, CR _k ) and SWAP gates to adjust the order of the qubits, in the case of solving the discrete logarithm problem it is performed over both registers simultaneously.

In the case of DLP, values of the type are calculated in the working register $g^{x} \bullet h^{b}\ mod\ p$ . These operations are implemented using reversible arithmetic based on CNOT and CCNOT gates. Each qbit of the control register controls the relevant modular multiplication sequences, with the entire calculation taking place in parallel over the superposition of all possible exponents. In the case of ECDLP, controlled scalar multiplication of an elliptic curve point is performed using reversible circuits for adding points and doubling them. These circuits are again assembled from networks of CNOT and CCNOT gates and are controlled by individual qbits of the control registers. In both cases, each qbit of the control register controls the relevant part of the calculation of point operations, with the entire process taking place in quantum superposition. The working register contains the contributions of both registers and can be discarded at the end of the calculation.

Calculation time estimate

Because it is difficult to estimate what the gate switching speed (rotation in Hilbert space) will be for a given technology, the following assumptions were used for the calculation. The number of qubits doubles every 3 years, but these are physical, not logical qubits. For protection, each logical qubit will be 1000 physical qubits. The physical volume of the QPU will then be reduced to roughly two-thirds of its original size every 3 years. These conditions only apply if development continues in the same way, there is no technological breakthrough or we do not encounter physical barriers (which is also possible). Furthermore, the gate speed will be constant, all gates switch at a speed of 1µs. This is also not true, but the information provided is sufficient for the estimate. Based on the mentioned developments and the required number of qubits and gates, it is possible to estimate the size of the quantum computer's volume without cooling and insulation around 2035. Here, I would like to point out again that this is only an estimate. And the last important piece of the puzzle. Since information only propagates at the speed of light (in this case, it is a limit describing the length of interaction between several qubits), the size of the sphere is determined based on the volume. For this sphere, with an even distribution of components, the mean distance is determined, which allows us to determine the average gate delay. If we rely on these data, it is possible to estimate the parameters of a given cryptographically relevant quantum computer around 2035. And this includes the time it would take to process one pass of Shor's algorithm.

Algorithm	Logical qubits	Number of gates	Time (s)	Volume (m³)
DSA 1024	2058	1.074·10¹⁰	1.074·10³	0.028
DSA 2048	4106	8.590·10¹⁰	8.590·10³	0.055
DH 1024	2058	1.074·10¹⁰	1.074·10³	0.028
DH 2048	4106	8.590·10¹⁰	8.590·10³	0.055
DH 3072	6154	2.899·10¹¹	2.899·10⁴	0.083
DH 4096	8202	6.872·10¹¹	6.872·10⁴	0.111
DH 6144	12298	2.319·10¹²	2.319·10⁵	0.166
DH 8192	16394	5.498·10¹²	5.498·10⁵	0.221
brainpoolP256r1	522	1.678·10⁸	16.78	0.007
brainpoolP384r1	778	5.662·10⁸	56.62	0.010
brainpoolP521r1	1052	1.414·10⁹	141.42	0.014
NIST P-256	522	1.678·10⁸	16.78	0.007
NIST P-384	778	5.662·10⁸	56.62	0.010
NIST P-521	1052	1.414·10⁹	141.42	0.014
Curve25519	520	1.658·10⁸	16.58	0.007
Curve448	906	8.992·10⁸	89.92	0.012
RSA 512	1029	6.711·10⁸	67.11	0.014
RSA 1024	2053	5.369·10⁹	536.87	0.028
RSA 2048	4101	4.295·10¹⁰	4.295·10³	0.055
RSA 2540	5085	8.194·10¹⁰	8.194·10³	0.069
RSA 3072	6149	1.450·10¹¹	1.450·10⁴	0.083
RSA 4096	8197	3.436·10¹¹	3.436·10⁴	0.110
RSA 7168	14341	1.841·10¹²	1.841·10⁵	0.193
RSA 8192	16389	2.749·10¹²	2.749·10⁵	0.221
RSA 13550	27105	1.244·10¹³	1.244·10⁶	0.365
RSA 37100	74205	2.553·10¹⁴	2.553·10⁷	1.000
RSA 76608	153221	2.248·10¹⁵	2.248·10⁸	2.064

An important parameter for determining the result is the number of repetitions. The problem with quantum computing is the probabilistic process. And this is where it gets interesting. If I want to achieve the appropriate statistical value of sigma (standard deviation), a significant number of repetitions of the calculation must occur for a normal random distribution of the outputs. The number of repetitions is thus given as a separate parameter that depends on the probability of the correct result of the task. The best possible case is 60%, the worst possible case is 40%. The disadvantage is the cost of increasing accuracy. For a simple change in accuracy from 1% to 0.1%, the number of measurements required will increase by a hundredfold.

$N = \frac{p \bullet (1 - p)}{\sigma^{2}} = \frac{0.5 \bullet (1 - 0.5)}{{0.01}^{2}} = 2500$

However, the advantage on our side is the actual output of Shor's algorithm. It does not have a typical Gaussian distribution, i.e. a function resembling a hat or the image of a snake swallowing an elephant from The Little Prince. It has sharp peaks, which indicate specific values of possible outputs. It looks approximately as follows.

Thanks to the existence of these sharp values and the probability of finding corresponding values, it is possible to significantly reduce the number of repetitions. From the original thousands of measurements required, we get to units to tens of repetitions. The mentioned sharp values are distributed in a certain way in the output in a ratio corresponding to the length of the register compared to the sought period of the function. So there are several probable outputs and we have to find and test them. This brings us to the following change. For simplicity, it is only in the form of a table, it does not contain a complete set of possible algorithms. The results are more or less similar.

Algorithm	Register length	Number of peaks	Number of measurements for 99% probability
RSA 2048	2048	~2¹⁰²⁴	7
DH 3072	3072	~2³⁰⁷²	7
ECDH 256	512	~2²⁵⁶	7

The results of the calculation using a quantum computer undergo post-processing on a classical computer. The time of this calculation is negligible compared to the work performed by the quantum computer. For discrete logarithm problems, the times are less than 1s, for a 1024b RSA key, units of seconds, for a 2048b RSA key, tens of seconds, and then approximately every doubling of the key width extends the time for processing the results on a classical digital computer by a factor of ten. Nevertheless, this is a negligible time compared to the calculation. From this perspective, a quantum computer can be imagined as a kind of analog probability machine.

To be continued in the next section Estimation of the Power Consumption of Quantum Computer (March 23th 2026)

References:

Quantum complexity of Shor’s algorithms implementations
Source: https://www.nature.com/
Quantum Computation and Shor’s Algorithm tutorial
Source: https://journals.aps.org/
Surface codes: Towards practical large-scale QC
Source: https://www.pnas.org/
Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit
Source: https://www.nature.com/
Lieb–Robinson bounds and locality in quantum systems
Source: https://journals.aps.org/
Quantum algorithms for discrete logarithms on elliptic curves
Source: https://www.worldscientific.com/
Amplitude estimation and quantum probability amplification
Source: https://arxiv.org/

Autor článku:

Jan Dušátko

Jan Dušátko has been working with computers and computer security for almost a quarter of a century. In the field of cryptography, he has cooperated with leading experts such as Vlastimil Klíma or Tomáš Rosa. Currently he works as a security consultant, his main focus is on topics related to cryptography, security, e-mail communication and Linux systems.

1. Introductory Provisions

1.1. These General Terms and Conditions are, unless otherwise agreed in writing in the contract, an integral part of all contracts relating to training organised or provided by the trainer, Jan Dušátko, IČ 434 797 66, DIČ 7208253041, with location Pod Harfou 938/58, Praha 9 (next as a „lector“).
1.2. The contracting parties in the general terms and conditions are meant to be the trainer and the ordering party, where the ordering party may also be the mediator of the contractual relationship.
1.3. Issues that are not regulated by these terms and conditions are dealt with according to the Czech Civil Code, i.e. Act No.89/2012 Coll.
1.4. All potential disputes will be resolved according to the law of the Czech Republic.

2. Creation of a contract by signing up for a course

2.1. Application means unilateral action of the client addressed to the trainer through a data box with identification euxesuf, e-mailu with address register@cryptosession.cz or register@cryptosession.info, internet pages cryptosession.cz, cryptosession.info or contact phone +420 602 427 840.
2.2. By submitting the application, the Client agrees with these General Terms and Conditions and declares that he has become acquainted with them.
2.3. The application is deemed to have been received at the time of confirmation (within 2 working days by default) by the trainer or intermediary. This confirmation is sent to the data box or to the contact e-mail.
2.4. The standard time for registration is no later than 14 working days before the educational event, unless otherwise stated. In the case of a natural non-business person, the order must be at least 28 working days before the educational event.
2.5. More than one participant can be registered for one application.
2.6. If there are more than 10 participants from one Client, it is possible to arrange for training at the place of residence of the intermediary or the Client.
2.7. Applications are received and processed in the order in which they have been received by the Provider. The Provider immediately informs the Client of all facts. These are the filling of capacity, too low number of participants, or any other serious reason, such as a lecturer's illness or force majeure. In this case, the Client will be offered a new term or participation in another educational event. In the event that the ordering party does not agree to move or participate in another educational event offered, the provider will refund the participation fee. The lack of participants is notified to the ordering party at least 14 days before the start of the planned term.
2.8. The contract between the provider and the ordering party arises by sending a confirmation from the provider to the ordering party.
2.9. The contract may be changed or cancelled only if the legal prerequisites are met and only in writing.

3. Termination of the contract by cancellation of the application

3.1. The application may be cancelled by the ordering party via e-mail or via a data mailbox.
3.2. The customer has the right to cancel his or her application for the course 14 days before the course takes place without any fees. If the period is shorter, the subsequent change takes place. In the interval of 7-13 days, an administrative fee of 10% is charged, cancellation of participation in a shorter interval than 7 days then a fee of 25%. In case of cancellation of the application or order by the customer, the possibility of the customer's participation in an alternative period without any additional fee is offered. The right to cancel the application expires with the implementation of the ordered training.
3.3. In case of cancellation of the application by the trainer, the ordering party is entitled to a full refund for the unrealized action.
3.4. The ordering party has the right to request an alternative date or an alternative training. In such case, the ordering party will be informed about all open courses. The alternative date cannot be enforced or enforced, it depends on the current availability of the course. If the alternative training is for a lower price, the ordering party will pay the difference. If the alternative training is for a lower price, the trainer will return the difference in the training prices to the ordering party.

4. Price and payment terms

4.1. By sending the application, the ordering party accepts the contract price (hereinafter referred to as the participation fee) indicated for the course.
4.2. In case of multiple participants registered with one application, a discount is possible.
4.3. The participation fee must be paid into the bank account of the company held with the company Komerční banka č. 78-7768770207/0100, IBAN:CZ5301000000787768770207, BIC:KOMBCZPPXXX. When making the payment, a variable symbol must be provided, which is indicated on the invoice sent to the client by the trainer.
4.4. The participation fee includes the provider's costs, including the training materials. The provider is a VAT payer.
4.5. The client is obliged to pay the participation fee within 14 working days of receipt of the invoice, unless otherwise stated by a separate contract.
4.6. If the person enrolled does not attend the training and no other agreement has been made, his or her absence is considered a cancellation application at an interval of less than 7 days, i.e. the trainer is entitled to a reward of 25% of the course price. The overpayment is returned within 14 days to the sender's payment account from which the funds were sent. Payment to another account number is not possible.
4.7. An invoice will be issued by the trainer no later than 5 working days from the beginning of the training, which will be sent by e-mail or data box as agreed.

5. Training conditions

5.1. The trainer is obliged to inform the client 14 days in advance of the location and time of the training, including the start and end dates of the daily programme.
5.2. If the client is not a student of the course, he is obliged to ensure the distribution of this information to the end participants. The trainer is not responsible for failure to comply with these terms and conditions.
5.2. By default, the training takes place from 9 a.m. to 5 p.m. at a predetermined location.
5.3. The trainer can be available from 8 a.m. to 9 a.m. and then from 17 a.m. to 6 p.m. for questions from the participants, according to the current terms and conditions.
5.4. At the end of the training, the certificate of absorption is handed over to the end users.
5.5. At the end of the training, the end users evaluate the trainer's approach and are asked to comment on the evaluation of his presentation, the manner of presentation and the significance of the information provided.

6. Complaints

6.1. If the participant is grossly dissatisfied with the course, the trainer is informed of this information.
6.2. The reasons for dissatisfaction are recorded in the minutes in two copies on the same day. One is handed over to the client and one is held by the trainer.
6.3. A statement on the complaint will be submitted by e-mail within two weeks. A solution will then be agreed within one week.
6.4. The customer's dissatisfaction may be a reason for discontinuing further cooperation, or financial compensation up to the price of the training, after deduction of costs.

7. Copyright of the provided materials

7.1. The training materials provided by the trainer in the course of the training meet the characteristics of a copyrighted work in accordance with Czech Act No 121/2000 Coll.
7.2. None of the training materials or any part thereof may be further processed, reproduced, distributed or used for further presentations or training in any way without the prior written consent of the trainer.

8. Liability

8.1. The trainer does not assume responsibility for any shortcomings in the services of any third party that he uses in the training.
8.2. The trainer does not assume responsibility for injuries, damages and losses incurred by the participants in the training events or caused by the participants. Such costs, caused by the above circumstances, shall be borne exclusively by the participant in the training event.

9. Validity of the Terms

9.1 These General Terms and Conditions shall be valid and effective from 1 October 2024.