EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Exact Totient Recovery in Semiprimes via Square-Root Proximity

Abdinabi Mukhamadiyev, Ugiloy Akhadova, Ilkhom Boykuziev, Bakhtiyor Abdurakhimov, Ergashevich Halimjon Khujamatov, Razvan Craciunescu

Mathematics · 21.05.2026 · 14 (10) · 1784

DOI: 10.3390/math14101784 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics, online erschienen am 21.05.2026. Verfasst von Abdinabi Mukhamadiyev und 5 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper studies structural properties of semiprimes N=pq in computational number theory, focusing on cases where the prime factors are close. We analyze the relationship between N and φ(N) and show that, under a bounded prime gap condition, these quantities exhibit strong proximity. Specifically, assuming |p−q|≤2l/4 for an l-bit semiprime, we prove that the Euler totient function admits the exact representation φ(N)=N−1−2⌊N⌋. Based on this result, we develop an interval-based method for reconstructing φ(N) within a narrow neighborhood derived from square-root bounds, followed by a discriminant-based refinement step for recovering the prime factors. Experimental evaluation on large semiprimes, including RSA-type moduli of 4095 and 4096 bits, shows that the method operates efficiently under the stated structural condition using only elementary integer arithmetic. These results provide a theoretical characterization of semiprimes with small prime gaps and offer a framework for identifying structurally weak RSA moduli. This method, given its high efficiency when the prime factors are close to each other, can be regarded as an alternative to Fermat’s factorization method. In particular, for semiprime integers with a small prime gap (i.e., |p−q| is small), the proposed approach exploits structural properties based on the proximity of square roots, thereby significantly accelerating the factorization process. Consequently, it not only aligns with the theoretical foundation of Fermat’s method but, under certain conditions, may also achieve comparable or even superior practical performance.

Zitieren

APA

Mukhamadiyev, A., Akhadova, U., Boykuziev, I., Abdurakhimov, B., Khujamatov, E. H., & Craciunescu, R. (2026). On Exact Totient Recovery in Semiprimes via Square-Root Proximity. Mathematics, 14(10), 1784. https://doi.org/10.3390/math14101784

Vancouver

Mukhamadiyev A, Akhadova U, Boykuziev I, Abdurakhimov B, Khujamatov EH, Craciunescu R. On Exact Totient Recovery in Semiprimes via Square-Root Proximity. Mathematics. 2026;14(10):1784. doi:10.3390/math14101784

BibTeX
@article{Mukhamadiyev2026,
  author = {Mukhamadiyev, Abdinabi and Akhadova, Ugiloy and Boykuziev, Ilkhom and Abdurakhimov, Bakhtiyor and Khujamatov, Ergashevich Halimjon and Craciunescu, Razvan},
  title = {On Exact Totient Recovery in Semiprimes via Square-Root Proximity},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {10},
  pages = {1784},
  doi = {10.3390/math14101784}
}
Kostenlos starten →