Pith. sign in

REVIEW 4 major objections 4 minor 13 references

Approximating Euler Totient Function using Linear Regression on RSA moduli

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a single linear fit on the public modulus n approximates Euler's totient phi(n) closely enough to aid certain RSA attacks.

desk verdict A tautology dressed as cryptanalysis: the regression merely restates phi(n) = n - p - q + 1 with a fitted constant for p+q, and the claimed lower bound is contradicted by the paper's own numbers. read the letter →

arxiv 2507.06706 v1 pith:YMAMZ5VC submitted 2025-07-09 cs.CR

Gilda Rech Bansimba , Regis F. Babindamana , Beni Blaug N. Ibara This is my paper · ORCID
classification cs.CR MSC 94A6068T05
keywords EulertotientapproximationRSAmoduluslinearregressioncryptanalysismachinelearningsemiprimephilowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to show that Euler's totient function $\varphi(n)$ for RSA moduli $n=pq$ can be approximated accurately by a single linear fit on the public modulus $n$. Using a parameter $\varepsilon$ that satisfies $\varphi = 2(\varepsilon + 1)$, the authors fit predictors of the form $\varepsilon_{\text{pred}} = n/2 - \alpha_s$, where the slope is always $1/2$ and only the intercept $\alpha_s$ changes with bit size $s$. They report that on generated 64-, 128-, 256-, 512-, and 1024-bit moduli, the fit achieves $R^2 = 1$ and small mean absolute error, and they claim the lower bound $n_s - 2\alpha_s + 2 < \varphi(n_s)$. If correct, the claim would give an attacker who knows only $n$ a numerical estimate of $\varphi$, which could help in some RSA attacks.

What carries the argument

The central object is the hyperbola-derived parameter $\varepsilon$, introduced through the identities $X = 2(n-\varepsilon)(n+1)-(n-1)^2$ and $Y = 4n(n-\varepsilon)^2$, with the totient expressed as $\varphi_\varepsilon(n) = 2(\varepsilon + 1)$. The regression treats $\varepsilon$ as the target and $n$ as the only feature; the fitted predictors $\varepsilon_{\text{pred}} = n_s/2 - \alpha_s$ carry the argument, because they convert a public modulus directly into a lower-bound estimate of $\varphi$. The per-size intercept $\alpha_s$ is the entire learned content of the model, and the claimed lower bound $n_s - 2\alpha_s + 2 < \varphi(n_s)$ is what would give the approximation cryptanalytic value.

What would settle it

Generate a fresh set of $s$-bit RSA moduli with known prime factors, compute actual $\varepsilon = \varphi/2 - 1$, and compare it with $n_s/2 - \alpha_s$ for the paper's tabulated $\alpha_s$. If any modulus violates $n_s - 2\alpha_s + 2 < \varphi(n_s)$, or if the error $|p+q - 2\alpha_s + 1|$ grows with the spread of $p$ and $q$, the central claim is refuted. The paper does not report this worst-case check.

Watch

Extended reading notes

Core claim

The central claim is that for each bit size $s$ there exists a constant $\alpha_s$ such that $\varepsilon$ for every $s$-bit RSA modulus is bounded below by $n_s/2 - \alpha_s$, and since $\varphi = 2(\varepsilon + 1)$, this yields $n_s - 2\alpha_s + 2 < \varphi(n_s)$. The fitted $\alpha_s$ values are obtained by linear regression on one million generated semiprimes per size, with the parameter $\varepsilon$ taken from the paper's hyperbola construction rather than from $n$ directly. The paper reports that the slope of the regression is exactly $1/2$ for all sizes, so all size-specific information is carried by the intercept $\alpha_s$; the tabulated intercepts for 64 through 1024 bits appear in Section 3. The authors interpret the near-perfect $R^2$ scores and symmetric error distributions as evidence that the approximation is accurate on unseen moduli of the same bit size.

Load-bearing premise

The load-bearing premise is that a single fitted constant $\alpha_s$ can replace the value $(p+q+1)/2$ for every RSA modulus of size $s$, so that $\varepsilon$ is essentially $n/2 - \alpha_s$; if $\alpha_s$ does not track $p+q$ across moduli of the same size, the approximation error $|p+q - 2\alpha_s + 1|$ is uncontrolled and the claimed $\varphi$ bound fails.

Editorial extensions

If this is right

  • For an RSA modulus of bit size $s$, the paper claims $\varphi(n) > n - 2\alpha_s + 2$, so a public $n$ alone gives a lower bound once $\alpha_s$ is known.
  • Because $\varphi = 2(\varepsilon + 1)$, the absolute error in predicting $\varphi$ equals twice the absolute error in predicting $\varepsilon$; the reported MAE values are therefore the directly attack-relevant quantity.
  • Since the slope is fixed at $1/2$, the model cannot distinguish moduli of the same bit size except through their value of $n$; all variability in $p$ and $q$ is compressed into the intercept $\alpha_s$.
  • The reported $R^2 = 1$ indicates that within the generated datasets, a line explains essentially all variance in $\varepsilon$, meaning the remaining errors are tiny relative to $\varepsilon$'s size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A consequence the paper leaves implicit: $n - \varphi(n) + 1 = p + q$, so the same regression also estimates the prime sum, and the absolute error of that estimate is $|p + q - 2\alpha_s + 1|$; the method's usefulness for factoring hinges on this quantity being small.
  • One testable extension is to fit $\alpha_s$ on one subset of a size class and then check on held-out moduli whether $|p + q - 2\alpha_s + 1|$ stays bounded as $p$ and $q$ vary; the paper reports MAE for $\varepsilon$ but not this directly attack-relevant quantity.
  • If the claimed lower bound is true, it implies $\alpha_s < (p+q+1)/2$ for every $s$-bit modulus, a strong structural statement about the prime distribution that could be checked empirically and would be remarkable if it held at 1024 bits.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper claims that a linear regression model trained on RSA moduli, using the public modulus n as the only feature, can approximate Euler's totient function phi(n) with small relative error. The authors introduce a target epsilon = phi/2 - 1, fit a per-bit-size intercept alpha_s with slope fixed at 1/2, and assert the lower bound ns - 2*alpha_s + 2 < phi(ns). They report R^2 scores of 1 and small relative errors for 64-, 128-, 256-, and 512-bit moduli, and suggest that such approximations may aid RSA attacks. The paper includes a short algorithm for building predictors from training data and concludes that statistical learning could supplement cryptanalysis.

Significance. If the central lower-bound claim were correct, the paper would offer a genuinely surprising result: a public modulus alone would reveal a nontrivial lower bound on phi(n) with cryptanalytic value. However, the result does not survive scrutiny. The regression reduces to a single fitted constant per bit size, and the claimed bound is contradicted by the paper's own reported constants. The reported R^2 and relative errors are artifacts of the target's domination by n/2, and the absolute error is on the scale of p+q, which is not shown to aid any factorization attack. The paper's main strength is that it states explicit constants and a falsifiable claim, which makes direct verification straightforward; that transparency is valuable, but it also exposes the central error. No 1024-bit results are presented despite the abstract and data section promising them.

major comments (4)
  1. [Section 3] The regression predictor is epsilon_pred = n/2 - alpha_s, while epsilon = (n - p - q - 1)/2. Substituting gives phi_pred = n - 2*alpha_s + 2 and the per-modulus error |phi_pred - phi_true| = |p+q+1 - 2*alpha_s|. Since alpha_s is a single constant per bit size and p+q varies across moduli of the same size, the approximation error for a fresh modulus is exactly the deviation of that modulus's half-sum from alpha_s. The paper provides no proof or worst-case analysis that alpha_s tracks (p+q+1)/2; in fact, n alone admits many prime pairs whose p+q values differ by roughly sqrt(n). This is load-bearing because the claimed lower bound and any cryptanalytic application depend entirely on this unstated constancy assumption.
  2. [Section 3, displayed lower bound] The asserted inequality ns - 2*alpha_s + 2 < phi(ns) is contradicted by the paper's own constants for 64-bit moduli. For 64-bit RSA moduli generated from 32-bit primes, each prime is at least 2^31, so (p+q+1)/2 >= 2^31 + 0.5 > 1,637,177,340 = alpha_64. Hence phi_pred = n - 2*alpha_64 + 2 > phi_true for every such modulus, reversing the claimed direction. For 128-bit moduli, alpha_128 ~ 7.56e22 is several orders of magnitude larger than the expected half-sum of two 64-bit primes, so this fitted intercept is not a plausible center for p+q. These internal inconsistencies show that the central claim is unsupported by the manuscript's own reported numbers.
  3. [Section 4, Performance Evaluation] The reported R^2 = 1 and small relative errors in epsilon do not support the conclusion that phi is approximated usefully. Since epsilon is approximately n/2, a regression of n/2 - alpha_s against n will always achieve near-perfect R^2 regardless of the quality of alpha_s. The meaningful error is the absolute error in phi, which is |p+q+1 - 2*alpha_s| and is on the scale of the prime sum, i.e., roughly sqrt(n). For cryptographically relevant sizes, this is orders of magnitude too large to aid any known attack, and no attack is specified that could exploit such an approximation. The conclusion that approximation-based techniques 'could serve as a supplementary tool in cryptanalysis' is therefore unsupported.
  4. [Section 2 and Section 4] The abstract and Section 2 state that the dataset includes 1024-bit RSA moduli, but the performance evaluation in Section 4 reports results only for 64-, 128-, 256-, and 512-bit moduli, and the figures likewise stop at 512 bits. No 1024-bit results are presented anywhere. Additionally, the procedure in Section 6.1 trains on factor pairs with known epsilon values and then applies the fitted constant to new moduli; because epsilon and phi are derived from the same factorization, this is a fitted-constant prediction rather than an independent relationship between n and phi. The paper does not show how the predictor would generalize to a modulus whose factors are not in the training distribution.
minor comments (4)
  1. [Abstract] The abstract contains a grammatically incomplete sentence: 'Although deriving phi(n) deterministically remains computationally infeasible for cryptographically relevant bit lengths, and machine learning presents a promising alternative...' The main clause is missing.
  2. [Section 3 / Section 5] The constants alpha_s are typeset inconsistently; for 256-bit and 512-bit sizes the digits are broken across lines in a way that makes the values hard to verify. The figure captions also contain typos such as '512-buts' instead of '512-bit'.
  3. [Section 6] The text refers to 'Figure 6' for the error distribution but the figure is labeled Figure 3. Several references to figures are ambiguous because multiple figures share the same number.
  4. [Section 2] The data generation description reports '1 million prime pairs for each of five bit sizes (32 to 512 bits)' but the manuscript does not specify the full bit-length list, the exact ranges of p and q, or how the pairs were sampled; these details are needed to reproduce the experiments.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regression approximation is an empirical fit with out-of-sample predictions, and the cited identity is elementary and independently verifiable.

full rationale

The paper's central identity, phi_epsilon(n)=2(epsilon+1) (Section 3), is an exact algebraic relation for RSA moduli and is cited to the authors' prior work [3]. This is not load-bearing circularity: for n=pq and epsilon=(n-p-q-1)/2, the identity is directly verifiable and equivalent to the standard formula phi(n)=n-p-q+1. The regression intercepts alpha_s are fitted to the training portion of the epsilon labels; the displayed epsilon_pred=n/2-alpha_s is then evaluated on a held-out test set, which is ordinary out-of-sample prediction rather than a restatement of the training labels. The conversion from the fitted predictor to the claimed lower bound n-2alpha_s+2<phi(n) is a rearrangement of the same equation, but a model's prediction being a function of its fitted parameters is not circularity. Whether the lower bound actually holds for all moduli of a given bit size is a correctness/generalization question, not a definitional equivalence. The self-citation to [3] supplies no uniqueness theorem and no fitted ansatz; the relation is elementary. No step reduces to its own input by construction.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The only fitted quantity is the per-bit-size intercept alpha_s. The paper relies on elementary totient identities and on the self-cited parametrization from [3]. The key ad hoc assumption is that a single constant can represent (p+q+1)/2 for all moduli of a fixed size, which makes the approximation trivial and not cryptographically useful.

free parameters (1)
  • alpha_s (per-bit-size intercept) = 64-bit: 1637177340; 128-bit: 75557863700000000704512; 256-bit and 512-bit values in Section 3
    Fitted via linear regression to epsilon, the target variable. The final approximation phi=n-2alpha+2 depends directly on these fitted values.
assumptions (4)
  • standard math For n=pq with odd primes, phi(n)=n-p-q+1.
    Elementary totient identity underlying the linear model; not stated explicitly but used throughout.
  • standard math phi(n)=2(epsilon+1), with epsilon an odd integer, imported from the authors' earlier paper [3].
    Equivalent to the totient identity; imported from self-cited prior work [3].
  • ad hoc to paper Within each modulus size s, (p+q+1)/2 is approximately constant, so epsilon is linear in n with fixed intercept alpha_s.
    This is the modeling assumption that makes the regression and the lower bound work. No proof or range analysis is provided, and the assumption is false in general.
  • domain assumption Randomly generated prime pairs from the Rabin-Miller test are representative of all RSA moduli of a given size.
    Used to claim generalization from 1 million samples per size to all RSA moduli; no distributional or worst-case argument is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating Euler Totient Function using Linear Regression on RSA moduli." pith.science (2026). https://pith.science/paper/YMAMZ5VC

@misc{pith2026250706706,
  author       = {Pith},
  title        = {Pith review of: Approximating Euler Totient Function using Linear Regression on RSA moduli},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YMAMZ5VC}},
  note         = {Machine review of arXiv:2507.06706}
}
read the original abstract

The security of the RSA cryptosystem is based on the intractability of computing Euler's totient function phi(n) for large integers n. Although deriving phi(n) deterministically remains computationally infeasible for cryptographically relevant bit lengths, and machine learning presents a promising alternative for constructing efficient approximations. In this work, we explore a machine learning approach to approximate Euler's totient function phi using linear regression models. We consider a dataset of RSA moduli of 64, 128, 256, 512 and 1024 bits along with their corresponding totient values. The regression model is trained to capture the relationship between the modulus and its totient, and tested on unseen samples to evaluate its prediction accuracy. Preliminary results suggest that phi can be approximated within a small relative error margin, which may be sufficient to aid in certain classes of RSA attacks. This research opens a direction for integrating statistical learning techniques into cryptanalysis, providing insights into the feasibility of attacking cryptosystems using approximation based strategies.

Figures

Figures reproduced from arXiv: 2507.06706 by the authors.

Figure 1
Figure 1. linear relation 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Performance of the model 6 Error Distribution [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. distribution of errors 6.1 Discussion It follows from our machine learning approach that one should consider custom predictors of size x bits depending on the size of the modulus to be attacked following the algorithm: Algorithme 1 : Predictor : Input : n Output : P redictor 1 Initialization: x ← number of bits of n 2 Generate a dataset of x bits RSA modulus with known factors with their ε values 3 Train a model to … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages

  1. [1]

    Babindamana, Gilda R

    Regis F. Babindamana, Gilda R. Bansimba, Basile G. R. Bossoto, Lattice Points on the Fermat Factorization Method, Journal of Mathematics, vol. 2022, Article ID 6360264, 18 pages, 2022. https://doi.org/10.1155/2022/6360264

    doi:10.1155/2022/6360264 2022

  2. [2]

    Bansimba, Regis F

    Gilda R. Bansimba, Regis F. Babindamana, Basile G. R. Bossoto. Some Arithmetical properties on Hyperbola, JP Journal of Algebra, Number Theory and Applications, Vol. 50, no. 1, P. 45- 100, 2021

    work page 2021

  3. [3]

    Bansimba, Regis Freguin Babindamana, Basile Guy R

    Gilda R. Bansimba, Regis Freguin Babindamana, Basile Guy R. Bossoto A New Hyperbola based Approach to factoring Integers [math.NT], https://doi.org/10.48550/arXiv.2304.07474

    arXiv doi:10.48550/arxiv.2304.07474

  4. [4]

    R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public- key cryptosystems, Communications of the ACM , vol. 21, no. 2, pp. 120–126, 1978

    work page 1978

  5. [5]

    ”Machine Learning in Cryptanalysis: A Survey.” Journal of Cybersecurity Advances, vol

    Alabaichi, A., et al. ”Machine Learning in Cryptanalysis: A Survey.” Journal of Cybersecurity Advances, vol. 5, no. 2, 2023, pp. 45–67

    work page 2023

  6. [6]

    ”Reinforcement Learning for Automated Cipher Design.” Proc

    Pandey, S., and Kumar, R. ”Reinforcement Learning for Automated Cipher Design.” Proc. of IEEE Symposium on Security & Privacy , 2024, pp. 112–130

    work page 2024

  7. [7]

    Benadjila, R., Prouff, E., Strullu, R., Cagli, E., & Dumas, C. (2020). Deep Learning for Side- Channel Analysis and Introduction to ASCAD Database. Journal of Cryptographic Engineering, 10(2), 163-188. DOI: 10.1007/s13389-019-00220-8

    work page doi:10.1007/s13389-019-00220-8 2020

  8. [8]

    Timon, B. (2019). Non-profiled Deep Learning-based Side-channel Attacks with Sensitiv- ity Analysis . In Proceedings of the 7th International Workshop on Constructive Side- Channel Analysis and Secure Design (COSADE 2019) (pp. 45-66). Springer. DOI: 10.1007/978-3-030-16350-1 3

    work page doi:10.1007/978-3-030-16350-1 2019

Show all 13 references
  1. [9]

    Gohr, A. (2019). Improving Attacks on Round-Reduced Speck32/64 Using Deep Learn- ing. In Advances in Cryptology - CRYPTO 2019 (pp. 150-179). Springer. DOI: 10.1007/978-3-030-26948-7 6

    2019 doi

  2. [10]

    W. F. Sierpinski, Elementary Theory of Numbers, Warsawa : North-Holland PWN-Polish Sci- entific Publishers, 1964

    1964

  3. [11]

    D. G. Kendall and H. B. Osborn, Two Simple Lower Bounds for Euler’s Function , vol. 17, Texas Journal of Science, 1965 8

    1965

  4. [12]

    Hatalova and T

    H. Hatalova and T. Salat, Remarks on two results in the elementary theory of numbers , Acta. FacRer. Natur Univ Comenian. Math., no. 20, pp. 113–117, 1969

    1969

  5. [13]

    Fang and C

    J. Fang and C. Liu, A Generalize Estimating the ϕ(n) of Upper/Lower Bound to RSA Public Key Cryptosystem , International Journal of Network Security, Vol.20, No.2, PP.332-336, Mar. 2018. 9

    2018

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.