International Journal of Science, Engineering and TechnologyAuthors: Research Scholar Tripti Gautam, Professor Dr. Narendra Bahadur Singh
Abstract: Almost every public-key cryptosystem deployed today rests on a small set of results from elementary and algebraic number theory: modular arithmetic, Euler’s theorem, the Chinese remainder theorem, primality testing and the group structure of finite fields and elliptic curves. This paper explains how these results yield the RSA, Diffie–Hellman/ElGamal and elliptic-curve families, and then tests the central claims with reproducible experiments. Over 1,070 odd composites below 3,000, no Miller–Rabin base misclassified more than 23.7% of candidates (theoretical bound 25%), whereas the Fermat test was fooled by up to 76.6%. Baby-step giant-step discrete-logarithm cost followed the square-root law across 16–44-bit primes. Applying the Chinese remainder theorem made RSA private-key operations 2.8–3.8 times faster for 1,024–4,096-bit moduli. In a library benchmark, RSA-2048 signing was about 11 times slower than ECDSA P-256 signing, while RSA verification was several times faster than elliptic-curve verification. The paper closes with the parameter and implementation lessons that follow from these results and notes the limit imposed by quantum computing.
