Factoring, Order Finding and Cryptographic Impact

Introduction

Public-key cryptography depends on mathematical problems that are believed to be difficult for classical computers. Two especially important assumptions are the difficulty of factoring large integers and the difficulty of computing discrete logarithms. Shor’s algorithm demonstrated that sufficiently large, fault-tolerant quantum computers could solve both problems in polynomial time.

This chapter explains the mathematical structure of Shor’s factoring algorithm, the role of order finding, the quantum circuits used for modular arithmetic, and the classical post-processing step based on continued fractions. It then connects the algorithm to public-key cryptography, migration to post-quantum cryptography (PQC), and organizational security planning.

The practical message is important: Shor’s algorithm is not currently a routine attack against deployed cryptographic keys because large-scale fault-tolerant quantum hardware does not yet exist. However, cryptographic migration must begin well before such hardware becomes available because systems have long lifetimes, sensitive data may need confidentiality for decades, and replacing cryptography is organizationally complex.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Explain why factoring can be reduced to order finding.
2. Describe the main quantum and classical stages of Shor’s algorithm.
3. Explain the role of modular exponentiation, the quantum Fourier transform, and continued fractions.
4. Identify the major resource requirements and implementation challenges.
5. Assess the effect of quantum computing on RSA, Diffie–Hellman, and elliptic-curve cryptography.
6. Propose practical steps for post-quantum migration and organizational risk management.

1. The Cryptographic Setting

1.1 Factoring and RSA

In RSA, two large primes p and q are multiplied to form

The modulus N is public, while p and q are secret. The security of RSA relies on the practical difficulty of recovering p and q from N. For appropriately chosen parameters, the best known classical factoring algorithms are subexponential rather than polynomial, and factoring sufficiently large RSA moduli is computationally expensive.

RSA also uses Euler’s totient function. When p and q are distinct primes,

A public exponent e is selected such that gcd(e, φ(N)) = 1. The private exponent d satisfies

The exact security details of RSA involve padding schemes, implementation protections, and parameter sizes. Nevertheless, discovering the factorization of N is sufficient to compute φ(N), derive the private exponent, and compromise the corresponding key.

1.2 Discrete-logarithm systems

Diffie–Hellman key exchange, DSA, and elliptic-curve cryptography rely on discrete-logarithm problems. In a multiplicative group, given g and g^a, the problem is to recover a. In an elliptic-curve group, given a generator G and point aG, the corresponding problem is to recover a.

Shor’s algorithm applies to both factoring and discrete logarithms. Therefore, a cryptographically relevant quantum computer threatens RSA, finite-field Diffie–Hellman, DSA, ECDH, and ECDSA. Symmetric cryptography is affected differently: quantum search algorithms provide a quadratic, rather than exponential, speed-up, so larger symmetric keys can generally compensate.

2. The Mathematical Core: Order Finding

2.1 Definition of order

Let a and N be positive integers with gcd(a, N) = 1. The multiplicative order of a modulo N is the least positive integer r such that

The condition gcd(a, N) = 1 is essential because a modular inverse, and hence a finite multiplicative group element, is required. The order r divides the size of the relevant group. For RSA-style N = pq, Euler’s theorem guarantees that a^φ(N) ≡ 1 mod N, so an order exists and divides φ(N).

Order finding is useful because the periodic function

has period r:

The quantum computer does not directly output r. Instead, it produces information about frequencies associated with the period. Classical continued-fraction processing then attempts to recover r.

2.2 From order finding to factors

Suppose r is even. Then

Because a^r ≡ 1 mod N,

If a^{r/2} is not congruent to −1 modulo N, the values

and

often reveal nontrivial factors of N.

The probabilistic qualification matters. A randomly selected a can produce an unsuitable order: r may be odd, or a^{r/2} may be congruent to −1 modulo N. In those cases, the algorithm selects another a and repeats. For suitable composite N, the probability of obtaining useful factors is sufficiently high that repetition is efficient.

2.3 Worked example: factoring 15

This small example illustrates the classical reduction; it is not a security-sized computation.

Let N = 15 and choose a = 2. Since gcd(2, 15) = 1, calculate powers modulo 15:

• 2^1 ≡ 2 mod 15
• 2^2 ≡ 4 mod 15
• 2^3 ≡ 8 mod 15
• 2^4 ≡ 16 ≡ 1 mod 15

Thus r = 4. The order is even, and

The two greatest common divisors are

and

Therefore, 15 = 3 × 5. In a real RSA setting, the same logical process applies, but the order r is obtained through a quantum period-finding circuit rather than by listing powers.

3. Shor’s Algorithm

Shor’s factoring algorithm contains a classical setup, a quantum period-finding stage, and classical post-processing.

3.1 High-level procedure

For a composite odd integer N:

1. Choose a random integer a with 1 < a < N.
2. Compute gcd(a, N). If it is greater than 1, a factor has already been found.
3. Prepare a quantum register in a superposition of values x.
4. Compute a^x mod N coherently into a second register.
5. Measure the second register, leaving the first register in a state related to values separated by the period r.
6. Apply the quantum Fourier transform (QFT) to the first register.
7. Measure a value c that is likely to approximate kQ/r, where Q is a power of two and k is an integer.
8. Use continued fractions to obtain a candidate denominator r.
9. Verify the candidate by checking a^r mod N = 1 and, if necessary, test multiples of the candidate.
10. If r is suitable, compute the two greatest common divisors and obtain factors.

The algorithm is probabilistic. Verification is inexpensive compared with the quantum computation, so unsuccessful trials can be detected and repeated.

3.2 Quantum registers and superposition

Let Q = 2^n be a power of two satisfying Q > N^2 in a standard presentation of the algorithm. The first register contains n qubits and represents x from 0 to Q − 1. The second register contains enough qubits to represent values modulo N, usually O(log N) logical qubits.

Applying Hadamard gates to the first register creates

where |x⟩ denotes the computational-basis state corresponding to x. A reversible modular-exponentiation circuit then performs

by unitary computation. This is not a classical parallel evaluation in which every x is individually read. Quantum interference is arranged so that measurement probabilities concentrate near frequencies associated with the period.

3.3 The quantum Fourier transform

For a register of dimension Q, the QFT maps a basis state |x⟩ to

Here i is the imaginary unit, x and c are integer labels, and Q is the register dimension. The transform is unitary and analogous to a discrete Fourier transform, but it is implemented as a quantum circuit and is not followed by direct classical access to all amplitudes.

If the first register contains a periodic or approximately periodic state with period r, the QFT produces high-probability outcomes c satisfying approximately

for some integer k. The approximation becomes useful when Q is sufficiently large relative to N.

The QFT circuit uses Hadamard gates and controlled phase-rotation gates, followed by a reversal of qubit order. An exact QFT on n qubits can use O(n²) elementary controlled rotations. Approximate QFTs omit very small rotations, reducing gate counts while introducing a controlled approximation error.

4. Continued Fractions and Classical Recovery

4.1 Why continued fractions are needed

The measured value c does not normally reveal r directly. Instead, it gives a rational approximation to k/r:

When this inequality holds and k/r is in reduced form, a theorem about continued fractions states that k/r appears among the convergents of c/Q. The denominator of a convergent is therefore a candidate for r.

This condition is an applicability condition, not a guarantee for every measurement. If k and r have a common factor, the recovered denominator may be a divisor of r. Multiple samples or verification of candidate multiples may be necessary.

4.2 Continued-fraction procedure

Given measured c and known Q:

1. Form the rational number c/Q.
2. Compute its simple continued-fraction expansion.
3. Generate its convergents p_j/q_j.
4. Test each denominator q_j as a candidate order.
5. Check whether a^{q_j} ≡ 1 mod N.
6. If necessary, test small multiples of q_j.
7. Use the first verified candidate that satisfies the factoring conditions.

A continued fraction has the form

where the a_i are nonnegative integers and a_i > 0 for i > 0. Its convergents are rational approximations obtained by truncating the expansion.

4.3 A small approximation example

Suppose a measurement gives c/Q = 5/16 and the true relationship is close to 1/3. The continued fraction of 5/16 is

Its convergents include 0/1, 1/3, and 5/16. The denominator 3 is a candidate for a divisor of the order. In an actual run, the candidate must be checked by modular exponentiation; numerical closeness alone is not proof.

5. Modular-Arithmetic Circuits

5.1 Reversibility requirement

Quantum operations must be reversible and therefore unitary. Ordinary classical modular arithmetic often discards carries, overwrites registers, or branches irreversibly. Quantum circuits must preserve enough information to allow the operation to be inverted.

A reversible adder maps input registers to output registers without collisions. Modular addition can then be constructed from reversible addition, comparison, conditional subtraction, and uncomputation. Uncomputation removes temporary information so that ancilla qubits return to a known state such as |0⟩.

5.2 Modular exponentiation by repeated squaring

Classically, a^x mod N is evaluated efficiently by expressing x in binary. If

where x_j ∈ {0, 1}, then

The constants a^{2^j} mod N can be precomputed classically. A reversible circuit conditionally multiplies by each constant according to the value of the control qubit x_j. The multiplication and reduction must be implemented reversibly.

5.3 Resource implications

The asymptotic complexity of Shor’s algorithm is polynomial in n = log₂N, but asymptotic polynomial time does not mean low engineering cost. The dominant resources include:

• logical qubits for exponent, data, and workspace registers;
• reversible adders, multipliers, and modular-reduction circuits;
• total logical gate count;
• circuit depth and degree of parallelism;
• error-correction overhead;
• physical-qubit count and communication requirements;
• runtime and the number of repeated trials.

Resource estimates vary substantially with the arithmetic architecture, error-correction code, physical gate error rates, connectivity, and target cryptographic size. Consequently, a responsible estimate should state its assumptions rather than quote a single universal number.

The first register requires O(log N) logical qubits, and the modular-arithmetic workspace also scales polynomially with log N. Fault-tolerant implementations require many more physical qubits because logical qubits are encoded into error-correcting codes and logical gates are synthesized from fault-tolerant operations. The overhead can be orders of magnitude and is hardware- and architecture-dependent.

5.4 Logical versus physical resources

A logical qubit is an error-corrected computational unit intended to behave reliably. A physical qubit is a hardware device subject to noise. Confusing these two levels produces misleading security claims. A statement that an algorithm needs a certain number of qubits may refer only to logical qubits and may omit the much larger physical implementation.

Similarly, circuit depth is not equivalent to wall-clock time. Wall-clock time depends on gate duration, parallel scheduling, measurement latency, error-correction cycles, and the number of repetitions required for a successful factorization.

6. Complexity and Practical Limitations

6.1 Complexity comparison

For input length n = log₂N, Shor’s algorithm has polynomial quantum time complexity under standard circuit models. Classical factoring algorithms, such as the general number field sieve, are subexponential in n rather than polynomial. This asymptotic separation explains the cryptographic significance of Shor’s result.

However, three qualifications are essential:

1. The algorithm assumes a sufficiently large fault-tolerant quantum computer.
2. The implementation must perform large, accurate modular arithmetic.
3. The algorithm threatens mathematical assumptions, not every security mechanism in the same way.

For example, authenticated symmetric encryption is not broken by simply applying Shor’s algorithm. Quantum search affects symmetric primitives through a different algorithmic mechanism.

6.2 Noise and fault tolerance

Uncorrected quantum devices suffer from gate errors, measurement errors, decoherence, leakage, and imperfect state preparation. Shor’s algorithm has long coherent computations and therefore requires error correction. Fault tolerance does not make computation error-free automatically; it requires physical error rates, codes, decoding procedures, and logical operations to satisfy engineering thresholds and resource constraints.

6.3 Input format and special cases

Shor’s factoring procedure is designed for integer factorization and related algebraic problems. It does not imply that every hard problem has a quantum polynomial-time solution. Nor does a successful period-finding measurement always produce the full order in one trial. Candidate orders must be verified, and classical gcd computations remain part of the workflow.

7. Cryptographic Impact

7.1 Directly vulnerable public-key systems

The impact differs by use. A compromised encryption key may expose stored ciphertext. A compromised signing key can enable forged software updates, certificates, transactions, or identity assertions. Therefore, public-key migration is not merely a confidentiality project.

7.2 Harvest now, decrypt later

An adversary may record encrypted traffic today and attempt decryption after acquiring a capable quantum computer. This creates a present-day risk for information with a long confidentiality lifetime, including government records, health data, intellectual property, diplomatic communications, and industrial designs.

The risk is greatest when:

• data remains sensitive for many years;
• encryption uses vulnerable key exchange;
• archives are accessible to an adversary;
• re-encryption after collection is impossible;
• certificate or key-management systems have long replacement cycles.

7.3 Symmetric cryptography

Grover’s algorithm gives an idealized quadratic speed-up for unstructured search. A rough security heuristic is that an n-bit symmetric key may offer about n/2 bits of quantum search security, subject to model and implementation assumptions. This is not a direct application of Shor’s algorithm and does not mean that all symmetric primitives become insecure.

Organizations should prefer modern authenticated encryption, use adequate key sizes, protect keys operationally, and follow current standards guidance. Hash functions also require security-level analysis; increasing output sizes can provide additional margin against quantum search and collision-related effects, depending on the application.

8. Post-Quantum Migration

Post-quantum cryptography seeks classical algorithms believed to resist both classical and quantum attacks. Important families include lattice-based, code-based, hash-based, and other structured or combinatorial constructions. Standardization decisions are made by standards bodies and are revised as cryptanalysis develops; organizations should therefore use approved, well-reviewed standards rather than inventing proprietary schemes.

8.1 Migration principles

A practical migration programme should:

1. Create a cryptographic inventory. Identify certificates, algorithms, key lengths, protocols, libraries, hardware modules, backups, APIs, embedded devices, and third-party dependencies.
2. Classify data by confidentiality and integrity lifetime. Estimate how long compromise would remain harmful.
3. Map trust dependencies. Record certificate authorities, firmware-signing keys, identity providers, service meshes, VPNs, databases, and supplier connections.
4. Prioritize high-impact systems. Begin with long-lived secrets, safety-critical systems, root credentials, and externally exposed infrastructure.
5. Require crypto-agility. Design systems so algorithms and parameters can be replaced through controlled configuration and protocol negotiation rather than full application rewrites.
6. Test hybrid deployments. Hybrid key establishment can combine a classical method with a post-quantum method during transition, but the composition must be standardized and correctly implemented.
7. Validate performance and interoperability. Measure key sizes, handshake messages, CPU cost, memory use, latency, certificate limits, and failure recovery.
8. Update governance and procurement. Require supplier roadmaps, vulnerability disclosure, algorithm provenance, support lifetimes, and migration commitments.
9. Retire obsolete algorithms. Migration is incomplete if vulnerable algorithms remain enabled as silent fallbacks.
10. Monitor standards and cryptanalysis. Security assumptions can change, and implementations require patching and revalidation.

8.2 Crypto-agility as an architecture property

Crypto-agility is more than selecting a new algorithm. It includes abstraction boundaries, algorithm identifiers, key lifecycle controls, certificate profiles, negotiation rules, telemetry, rollback procedures, and emergency replacement capability. A system is not agile if a new algorithm requires replacing every device or if old algorithms can be re-enabled without authorization.

8.3 Hybrid security and downgrade risks

Hybrid mechanisms may provide protection if at least one component remains secure, but this depends on the exact combiner and protocol design. Poorly designed hybrids can introduce downgrade attacks, transcript ambiguity, key-confirmation failures, or algorithm-confusion vulnerabilities. Security teams should use standardized constructions and conduct independent testing.

9. Illustrative Organizational Case

Background

A fictional international engineering company, Meridian Systems, operates a public-key infrastructure for employee authentication, VPN access, software signing, and encrypted communication with customers. Its products have a fifteen-year support life, and some designs must remain confidential for twenty-five years.

Problem

The company initially treats quantum risk as a distant hardware issue. An assessment reveals that encrypted design archives could be harvested today. It also discovers that several embedded devices have fixed certificate formats and cannot easily accept larger post-quantum keys.

Analysis

The security team separates threats into confidentiality, authentication, and operational continuity. Archived traffic is a harvest-now-decrypt-later concern. Firmware signing is an integrity and safety concern: a future signing-key compromise could permit malicious updates. Embedded devices create a supply-chain and lifecycle constraint because replacement may take a decade.

The team ranks assets using an indicative risk score:

This is a governance heuristic, not a universal law. Impact, likelihood, and exposure must be defined using an organizational scale, such as 1 to 5, and the scoring method must be documented so that results are comparable.

Approach

Meridian first inventories algorithms and dependencies. It then establishes an approved cryptographic abstraction layer, pilots standardized post-quantum key establishment in a hybrid mode for selected services, increases protection for long-lived archives, and redesigns firmware-signing infrastructure with a staged key-transition process. Procurement contracts require suppliers to disclose quantum-readiness assumptions and support algorithm replacement.

The company also creates a cryptographic emergency plan. It specifies who can revoke certificates, how replacement keys are generated, how devices receive trust-anchor updates, how old signatures are handled, and how incidents are communicated to customers.

Outcome

The programme does not claim that quantum risk has been eliminated. Instead, Meridian reduces exposure, gains measurement data, identifies incompatible devices early, and creates a repeatable process for future algorithm changes. The most valuable result is architectural readiness rather than a single algorithm choice.

Learning points

• Quantum risk is a data-lifetime and system-lifecycle issue, not only a hardware forecast.
• Public-key uses must be separated into encryption, key establishment, signatures, and authentication.
• Inventory and dependency mapping are prerequisites for rational migration.
• Algorithm replacement must include operational, legal, supplier, and governance controls.
• Hybrid deployment must be standardized, tested, and protected against downgrade.

10. Governance, Ethics and Professional Responsibility

Quantum security planning involves decisions about privacy, safety, national security, and inter-organizational trust. Organizations should avoid exaggerated claims such as “quantum-proof” without defining the threat model and evidence. They should communicate uncertainty honestly while still acting on long-lived risks.

Security professionals must protect personal data during cryptographic inventory work, because inventories can reveal sensitive system architecture. Access to key metadata should be controlled, and migration testing should not expose production secrets. Procurement teams should evaluate independent cryptanalysis, implementation quality, licensing, supply-chain provenance, and standards status.

Regulated organizations may also need to document risk assessments, retention decisions, incident-response procedures, and evidence of compliance with sector-specific requirements. Legal and regulatory obligations vary by jurisdiction; technical migration should therefore be coordinated with legal, audit, privacy, and business-continuity functions.

11. Best Practices Checklist

• Maintain an authoritative inventory of cryptographic assets.
• Record algorithm, parameter, purpose, owner, location, dependency, and retirement date.
• Classify information by required confidentiality and integrity lifetime.
• Separate public-key encryption, key exchange, signatures, and authentication use cases.
• Use standardized post-quantum algorithms and approved protocol profiles.
• Design for crypto-agility and prevent unauthorized downgrade.
• Test performance on constrained devices and high-latency networks.
• Protect roots of trust and firmware-signing processes as high-priority assets.
• Plan certificate, key, firmware, and archival-data transitions together.
• Reassess assumptions as quantum hardware, standards, and cryptanalysis evolve.

Chapter Summary

Shor’s algorithm factors integers and solves discrete logarithms by reducing the problem to quantum order finding. For a chosen a relatively prime to N, the function a^x mod N is periodic, and the period r can reveal factors when r is even and a^{r/2} is not congruent to −1 modulo N. Quantum parallelism and interference are used through reversible modular exponentiation and the quantum Fourier transform. Measurement produces an approximation to k/r, and continued fractions provide candidate denominators that are verified classically.

The algorithm is polynomial in the input length under standard fault-tolerant quantum models, but practical execution requires substantial logical and physical resources. Modular arithmetic, error correction, circuit depth, connectivity, and repeated trials are central engineering concerns.

RSA, finite-field Diffie–Hellman, DSA, ECDH, and ECDSA rely on problems threatened by Shor’s algorithm. Symmetric cryptography faces a different, generally quadratic quantum-search effect. Organizations should respond through cryptographic inventory, data-lifetime analysis, crypto-agility, standardized post-quantum migration, hybrid testing where appropriate, and strong governance. The correct professional response is neither complacency nor unsupported alarm, but structured preparation based on explicit assumptions and verified controls.

Key Terms

Order finding: Determining the least positive r such that a^r ≡ 1 mod N.

Multiplicative order: The order of an element in a finite multiplicative group.

Period: The repeating interval of a function such as a^x mod N.

Shor’s algorithm: A quantum algorithm for factoring and discrete logarithms.

Modular arithmetic: Arithmetic in which values are considered equivalent modulo a specified integer.

Reversible computation: Computation in which the input can be recovered from the output.

Modular exponentiation: Computing a^x mod N efficiently, often by repeated squaring.

Quantum Fourier transform: A unitary quantum analogue of the discrete Fourier transform.

Continued fraction: An expression that generates rational approximations through convergents.

Convergent: A rational approximation obtained by truncating a continued fraction.

Logical qubit: An error-corrected qubit intended to support reliable computation.

Physical qubit: A hardware qubit subject to physical noise.

Fault tolerance: The ability to perform reliable computation using error correction and controlled logical operations.

RSA: A public-key system whose security depends primarily on integer factoring.

Discrete logarithm: Recovering an exponent from a group element such as g^a.

Post-quantum cryptography: Cryptography designed to resist known classical and quantum attacks.

Crypto-agility: The capability to replace cryptographic algorithms and parameters with limited disruption.

Harvest now, decrypt later: Collecting ciphertext today for possible future decryption.

Hybrid cryptography: A transition design combining classical and post-quantum components.

Cryptographic inventory: An authoritative record of algorithms, keys, certificates, protocols, and dependencies.

Review Questions

5 Short Answer Questions

1. Define the multiplicative order of a modulo N.
2. Why must a modular-exponentiation circuit be reversible in a quantum computer?
3. What information does the QFT reveal in Shor’s algorithm?
4. Why are continued-fraction denominators treated as candidates rather than automatically accepted as the order?
5. Name two public-key systems threatened by Shor’s algorithm.

5 Long Answer Questions

1. Explain the complete workflow of Shor’s factoring algorithm, distinguishing quantum operations from classical post-processing.
2. Derive the factor-extraction step from the relation a^r ≡ 1 mod N when r is even.
3. Explain how reversible modular multiplication and uncomputation support modular exponentiation.
4. Compare logical-qubit requirements with physical-qubit requirements and explain why resource estimates vary.
5. Discuss why post-quantum migration is an architectural and governance programme rather than a simple algorithm replacement.

3 Analytical / Application Questions

1. An organization stores encrypted engineering designs that must remain confidential for twenty years. Analyze the relevance of harvest-now-decrypt-later risk and recommend three immediate actions.
2. A measured QFT result produces a fraction c/Q whose continued-fraction convergents have denominators 3, 8, and 24. Explain how the organization implementing the algorithm should test these candidates before attempting factor extraction.
3. Design a migration-priority framework for a company using RSA certificates, ECDH VPNs, ECDSA firmware signing, and AES-protected archives. Justify the order in which these systems should be addressed.

Multiple Choice Questions with Answers

Question 1

What is the multiplicative order of a modulo N?

A. The smallest positive r such that a^r ≡ 1 mod N

B. The largest prime factor of N

C. The value of a divided by N

D. The number of qubits required to represent N

Correct Answer: A. The smallest positive r such that a^r ≡ 1 mod N

Question 2

Why is the condition gcd(a, N) = 1 required in the usual order-finding step?

A. It guarantees that N is prime

B. It ensures a is an element with a modular inverse

C. It makes the QFT unnecessary

D. It guarantees that the order is odd

Correct Answer: B. It ensures a is an element with a modular inverse

Question 3

What is the main purpose of the quantum Fourier transform in Shor’s algorithm?

A. To factor N directly without measurement

B. To erase the modular-exponentiation register

C. To convert periodicity into measurable frequency information

D. To generate cryptographic keys

Correct Answer: C. To convert periodicity into measurable frequency information

Question 4

What does continued-fraction processing usually provide from a measured value c/Q?

A. Candidate denominators related to the order r

B. The physical error rate of the quantum processor

C. The prime factors without verification

D. The number of physical qubits

Correct Answer: A. Candidate denominators related to the order r

Question 5

For N = 15 and a = 2, what is the order r?

A. 2

B. 3

C. 4

D. 5

Correct Answer: C. 4

Question 6

Using N = 15, a = 2, and r = 4, which pair gives the nontrivial factors?

A. gcd(2 − 1, 15) and gcd(2 + 1, 15)

B. gcd(4 − 1, 15) and gcd(4 + 1, 15)

C. gcd(15 − 1, 2) and gcd(15 + 1, 2)

D. gcd(4, 15) and gcd(8, 15)

Correct Answer: B. gcd(4 − 1, 15) and gcd(4 + 1, 15)

Question 7

Which system is directly threatened by Shor’s algorithm because it relies on elliptic-curve discrete logarithms?

A. ECDSA

B. AES-GCM

C. One-time pad

D. A random password generator

Correct Answer: A. ECDSA

Question 8

Which statement best distinguishes logical and physical qubits?

A. They are two names for exactly the same resource

B. A logical qubit is an error-corrected computational unit, while a physical qubit is a hardware device

C. A physical qubit exists only in software

D. A logical qubit cannot be used in fault-tolerant computation

Correct Answer: B. A logical qubit is an error-corrected computational unit, while a physical qubit is a hardware device

Question 9

What is a central purpose of a cryptographic inventory?

A. To increase the mathematical order of every key

B. To identify algorithms, keys, certificates, protocols, and dependencies

C. To replace all symmetric encryption immediately

D. To predict the exact date of the first cryptographically relevant quantum computer

Correct Answer: B. To identify algorithms, keys, certificates, protocols, and dependencies

Question 10

Why may organizations need to migrate before a large fault-tolerant quantum computer exists?

A. Quantum computers already factor all deployed keys routinely

B. Recorded ciphertext may be decrypted later, and migration has long lead times

C. Post-quantum algorithms require no testing

D. Classical computers cannot use public-key cryptography

Correct Answer: B. Recorded ciphertext may be decrypted later, and migration has long lead times