Paper 2024/1002
Elementary Formulas for Greatest Common Divisors and Semiprime Factors
Abstract
We present new formulas for computing greatest common divisors (GCDs) and extracting the prime factors of semiprimes using only elementary arithmetic operations: addition, subtraction, multiplication, floored division, and exponentiation. Our GCD formula simplifies a result of Mazzanti, and is derived using Kronecker substitution techniques from our previous work. We utilize the GCD formula, along with recent developments on arithmetic terms for square roots and factorials, to derive explicit expressions for the prime factors of a semiprime $n=pq$.
Note: Updates in this version include: Additional GCD formulas, tightening of constraints on existing GCD formulas to handle an edge case, addition of a formula for Euler's totient function for semiprimes, and a minor simplification of the factorial formula used in the semiprime factoring formulas.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- semiprimesrsainteger factorizationfactoringelementary formulaarithmetic term
- Contact author(s)
- jshunia1 @ jh edu
- History
- 2024-06-22: revised
- 2024-06-21: received
- See all versions
- Short URL
- https://ia.cr/2024/1002
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2024/1002,
author = {Joseph M. Shunia},
title = {Elementary Formulas for Greatest Common Divisors and Semiprime Factors},
howpublished = {Cryptology ePrint Archive, Paper 2024/1002},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/1002}},
url = {https://eprint.iacr.org/2024/1002}
}
