Elementary Formulas for Greatest Common Divisors and Semiprime Factors

Autor:	Shunia, Joseph M.
Rok vydání:	2024
Předmět:	Mathematics - General Mathematics
Druh dokumentu:	Working Paper
Popis:	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$. Comment: Version 1 of this preprint was published to the Cryptology ePrint Archive. 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
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2407.03357 Zobrazit plný text záznamu View this record from Arxiv