Authors: Research Scholar Tripti Gautam, Professor Dr. Narendra Bahadur Singh
Abstract: Factoring, discrete logarithms and their elliptic-curve analogues are number-theoretic problems that a large quantum computer can solve in polynomial time. This paper explains why, describes the lattice-based replacements now standardised by NIST, and shows that number theory still does much of the work inside them. Three computational experiments support the argument. First, the classical reduction inside Shor’s algorithm was applied to 300 semiprime moduli: a random base yielded a nontrivial factor 74.3% of the time on average, and never less than 50% for any modulus, matching theory. Second, a toy learning-with-errors (LWE) instance modulo q = 3329 was solved exactly by Gaussian elimination without noise, but in none of 300 trials per dimension once errors as small as ±1 were added. Third, a number-theoretic transform over Z_3329, using the 256th root of unity 17, reproduced schoolbook polynomial multiplication exactly while needing 18 times fewer modular multiplications (3,584 versus 65,536). The paper also quantifies the price of migration: an ML-KEM-768 exchange transmits 2,272 bytes against 64 for X25519.
