Skip to content
Tech Interview Prep
Technical interview guide

Quantum Algorithms II: Shor's Algorithm & Cryptographic Implications

How Shor's algorithm factors integers exponentially faster than any known classical method, and why that breaks RSA/ECC and drives the shift to post-quantum cryptography.

Read
56 min
Practice MCQs
25
Interview Q&A
25
Edition
v2
Editorial status
Reviewed

Scope: IBM Quantum current Shor/QPE documentation; Shor primary paper; NIST FIPS 203/204/205, IR 8547 draft, SP 800-57, and crypto-agility guidance reviewed 2026-09-04.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A migration team is tagging every algorithm in its inventory with the mathematical problem a quantum adversary would have to solve to break it. The next entry reads "RSA-2048, TLS key transport." Which problem belongs on that entry?
MCQ-2A post-quantum readiness review inventories a TLS 1.3 service: X25519 key agreement, Ed25519 certificate signatures, AES-256-GCM record encryption, SHA-384 transcript hashing, and RSA-2048 keys that the config disables. The reviewer must file the deployed primitives that Shor's algorithm, in its discrete-logarithm formulation, breaks. Which filing is correct?
MCQ-4A team is implementing Shor's algorithm for N = 15 and picks the base a = 7. They run the order-finding subroutine and need to confirm the period r it returns before using it in the continued-fraction step. Which value of r should they expect, and why is it the correct period?
MCQ-3A team is implementing Shor's algorithm to factor N = 91. Before building the quantum circuit, their classical preprocessing picks a = 14. What is the correct outcome of that step?
MCQ-10A Shor's-algorithm run on N = 15 draws base a = 14, and the order-finding circuit returns r = 2. What does the classical post-processing conclude?
MCQ-11A Shor's-algorithm run on N = 15 draws base a = 14. The order-finding subroutine returns r = 2. The classical post-processing computes gcd(14^1 − 1, 15) = 1 and gcd(14^1 + 1, 15) = 15. What should the run do next?
MCQ-12A Shor run on N = 15 with base a = 7 measures the phase register; continued-fraction post-processing of the measured phase yields the order r = 4. The classical step must now turn r into the factors of N. Which computation does it perform, and what does it return?
MCQ-13A team runs Shor's algorithm on N = 8051. Across 1024 shots the most frequent measurement outcome is post-processed into the candidate factor 91, which the pipeline reports as a factor of 8051. What should the pipeline do next?
MCQ-8A counting register of n = 3 qubits is put into uniform superposition and used to control U^(2^0), U^(2^1) and U^(2^2) on a second register that holds an eigenstate of U with eigenphase phi = 1/4. Measured at this point, the counting register returns each of its eight outcomes about 12.5% of the time. One inverse QFT is then applied to the counting register alone, and every shot now reads 010. Which statement accounts for that?
MCQ-5An order-finding circuit for N = 15 uses a = 7. The work register starts in |1>, the phase register has 4 qubits, and the controlled gate is meant to implement U: |x> -> |7x mod 15>. After the inverse QFT, the phase register is measured as 0100, i.e. φ = 0.25. Which conclusion about the order r and the operation phase estimation was applied to is correct?
MCQ-9A Shor run for N=15 uses a=7. Phase estimation returns the 4-bit register value 0100, interpreted as φ=4/16=0.25. The continued-fraction expansion of φ is [0;4], whose first convergent is 1/4. What should the classical post-processing do with this convergent?
MCQ-7A team runs Shor's order-finding subroutine on N = 15 with a = 7, using a phase-estimation register of t = 8 qubits. The measured register value is 170. They run the continued-fraction expansion of 170/256 and take the convergent with denominator below N, getting 2/3. What does this tell them about the order r of 7 modulo 15?
MCQ-6A team is synthesizing Shor's algorithm against a 2048-bit RSA modulus N with base a, so the exponent register has 2n = 4096 qubits indexed j = 0 through 4095. For each j the circuit applies the controlled multiplication U: |y> -> |a*y mod N> exactly 2^j times, and synthesis of the j = 4095 qubit has been running for a week, estimated at 2^4095 applications of U. The modulus size and the algorithm's usual success probability are fixed. Which change removes the blowup?
MCQ-24A team factors 15 = 3 × 5 with Shor's algorithm on a superconducting device and argues that the algorithm is now demonstrated, leaving only engineering scale, more qubits and lower error rates, before RSA-2048 falls. Which limitation most directly undercuts that argument?
MCQ-25A team is sizing a fault-tolerant machine to break 128-bit classical security and is comparing RSA-2048 with ECDSA over P-256. Both fall to Shor's algorithm, but the resource profiles differ. Which statement about the logical qubit counts and circuit structure of the two attacks is correct?
MCQ-23A team estimates RSA-2048 at 4,000 logical qubits, 10^10 Toffoli gates, a 10^-3 physical error rate, a 1 µs surface-code cycle, and 8 hours wall-clock. A reviewer recomputes the data block as 4,000 × 2d² with d = 15: about 1.8 million physical qubits, and concludes the team's 20 million figure is inflated roughly tenfold. Which statement about the reviewer's conclusion is correct?
MCQ-14A payments service uses RSA-2048 (e = 65537) for TLS key transport and AES-256-GCM for stored records. An adversary records today's handshakes. Ten years later it has a fault-tolerant quantum computer with enough logical qubits to run Shor's algorithm on a 2048-bit modulus, and it runs Grover's algorithm against the AES-256 key. Which secret does it end up holding?
MCQ-15A payments gateway terminates TLS 1.3 with X25519 key exchange and ECDSA P-256 certificates, and encrypts records with AES-256-GCM. A tap records every handshake and ciphertext, and regulation requires that traffic to stay confidential for 15 years. The migration plan retires RSA-2048 first and leaves this gateway for last, arguing that X25519 and ECDSA are not factoring-based and their keys are ephemeral. When a cryptographically relevant quantum computer (CRQC) running Shor becomes available, which recorded material can an attacker who kept the tap output recover?
MCQ-16An archive service must keep every customer upload confidential for 30 years. Each file is encrypted with its own AES-128-GCM data key; that data key is wrapped with the service's RSA-2048 public key, and the wrapped blob is stored beside the file. The RSA private key never leaves the service's KMS. The team's rule is that a symmetric key must require at least 2^128 quantum evaluations to recover, and it assumes an adversary copies the whole archive today and gets a cryptographically relevant quantum computer in year 12. Which conclusion about what to migrate is correct?
MCQ-17An adversary copies one artifact today: a 6 KB TLS 1.2 session record whose key exchange used a 2048-bit finite-field Diffie-Hellman group, whose record encryption is AES-256-GCM, and whose certificate expired after 90 days. The data must stay confidential for 12 years. Which property of the copied artifact decides whether the adversary gains anything from running Shor on a cryptographically relevant quantum computer later?
MCQ-19A vendor signs firmware bundles and appends the signature to a fixed 10,240-byte field in each bundle. The security policy requires that the signature scheme's security rest only on the properties of a hash function, no lattice or other number-theoretic hardness assumption, so that bundles stay unforgeable even if lattice problems fall. Which FIPS 204/205 parameter set satisfies both the field size and the policy?
MCQ-18A team terminates TLS 1.3 and has enabled the X25519MLKEM768 group. Their edge proxy drops any ClientHello whose key share for the offered group exceeds 1200 bytes, a limit set when the deployment offered X25519 alone. The component sizes for this group are: X25519 public key 32 bytes, X25519 shared secret 32 bytes, ML-KEM-768 encapsulation key 1184 bytes, ML-KEM-768 ciphertext 1088 bytes, ML-KEM-768 shared secret 32 bytes. After the change, clients that offer X25519MLKEM768 are dropped, while clients that offer only X25519 connect. What is the size of the key_exchange field in the client's key share for X25519MLKEM768?
MCQ-22An internal TLS 1.3 service offers exactly two key-exchange groups, X25519MLKEM768 and X25519, using a vendor build of the TLS library. Over 200,000 handshakes in one week, 37 connections logged "ML-KEM decapsulation failed" at WARN level and then completed the handshake; SSL_get_negotiated_group() returned X25519MLKEM768 for those same 37 connections, and nothing else was logged for them. What is the correct reading of those 37 sessions?
MCQ-20A payments platform runs 240 internal services. A TLS scanner reports that all 240 negotiate TLS 1.3 with X25519 and that none use RSA key exchange, so the team schedules an ML-KEM (FIPS 203) rollout for Q1. The scanner reads application configuration only. In the pilot, 21 of the 240 services fail the ML-KEM handshake: 17 because their traffic terminates on a hardware load balancer whose firmware pins the supported-group list, and 4 because a vendor SDK hardcodes a static RSA key for license validation. Which conclusion about the scanner's report is correct?
MCQ-21A payments service compiles its TLS cipher-suite list and signing algorithm into the binary, and its negotiation code accepts any suite a peer offers unless it is on a denylist. Compliance requires ECDSA P-256 over TLS 1.3 within one quarter, and the roadmap lists a post-quantum key exchange within 18 months. The team counts 14 hardcoded call sites and 3 client SDKs pinning the current RSA-2048 certificate, and estimates 3 sprints per migration. Which change most reduces the cost of the next migration?