Paper 2024/1002
Elementary Formulas for Greatest Common Divisors and Semiprime Factors
Abstract
We conjecture new elementary formulas for computing the greatest common divisor (GCD) of two integers, alongside an elementary formula for extracting the prime factors of semiprimes. These formulas are of fixed-length and require only the basic arithmetic operations of: addition, subtraction, multiplication, division with remainder, and exponentiation. Our GCD formulas result from simplifying a formula of Mazzanti and are derived using Kronecker substitution techniques from our earlier research. By applying these GCD formulas together with our recent discovery of an arithmetic expression for $\sqrt{n}$, we are able to derive explicit elementary formulas for the prime factors of a semiprime $n=p q$.
Note: Updates in this version include: Restating the polynomial GCD formula as a conjecture, due to an issue in the previous proof. Addition of lemmas for square root formula
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- semiprimesrsainteger factorizationfactoringelementary formulaarithmetic term
- Contact author(s)
- jshunia1 @ jh edu
- History
- 2024-11-06: last of 3 revisions
- 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},
url = {https://eprint.iacr.org/2024/1002}
}
