Bridging Number-Theoretic Primality Testing And Algorithmic Optimization: An Adaptive Cryptographic Framework

Tran Minh Thanh; Vo Hoai Viet

cs.CROct 22, 2026

Bridging Number-Theoretic Primality Testing And Algorithmic Optimization: An Adaptive Cryptographic Framework

Authors: Tran Minh Thanh, Vo Hoai Viet

Organizations: Faculty of Information Technology, University of Science, Ho Chi Minh City, Vietnam · Vietnam National University, Ho Chi Minh City, Vietnam

Abstract

The security of modern public-key cryptographic systems, such as RSA, Diffie-Hellman, and ECC, depends entirely on the computational intractability of the integer factorization and discrete logarithm problems. For these asymmetric algorithms to operate, a core requirement is that the system must be capable of generating, testing, and simultaneously proving the primality of extraordinarily large numbers. To meet those requirements, this study proposes a comprehensive framework, bridging clas- sical number theory with modern machine learning models and optimization algorithms. Specifically, the paper delineates an adaptive, arbitrary-precision architecture dedicated exclusively to primality testing. Concurrently, the research deeply analyzes the theoretical foundations of testing methods (both deterministic and probabilistic), hardware-level optimization techniques, and the application of quantum-secured entropy sources, while providing rigorous mathematical proofs to guarantee security even when the prime distribution is biased.

Figures & tables

Figure 1: Complexity explosion and feasibility limits of the trial division algorithm.

Figure 2: Theoretical operational scaling and complexity boundaries of primality testing frameworks (analytical operation count plotted as a function of candidate bit length), illustrating the combinatorial explosion of Trial Division $O(\sqrt{N})$ against polynomial-time alternatives such as Miller-Rabin and FastECPP.

Algorithm Framework	Time Complexity	Error Probability	Cryptographic Advantages	Vulnerabilities / Drawbacks
Fermat Test	$O(k\log^{3}N)$	1 for Carmichael numbers	Simple baseline implementation	Utterly defeated by Carmichael numbers AbuDaqa et al. (2020) .
Solovay-Strassen	$O(k\log^{3}N)$	$<(1/2)^{k}$	Resolves Carmichael flaw	High overhead computing Jacobi symbols AbuDaqa et al. (2020) .
Miller-Rabin	$O(k\log^{3}N)$	$<(1/4)^{k}$	Extremely fast, tunable certainty	Requires multiple bases for absolute security AbuDaqa et al. (2020) .
Baillie-PSW	$O(k\log^{3}N)$	0 for $N<2^{64}$	No known pseudoprimes exist	Heuristic; lacks formal mathematical proof for all $N$ AbuDaqa et al. (2020) .

Table 1: Comparison of Cryptographic Primality Testing Algorithms

Figure 3: Recursive ECPP proof chain. Starting from the candidate

N_{0}

, each step reduces the proof to a smaller probable prime

q_{i}

until a small prime is verified directly by trial division. Bit lengths are illustrative only.

Figure 4: Hardware-aware memory architecture for the Segmented Sieve of Eratosthenes. The search space is dynamically partitioned into intervals of size $\Delta$ , tuned to fit within the L1 Cache (e.g., 32KB) to eliminate cache-miss penalties.

Figure 5: Comparison of Optimization Landscapes: Continuous Standard Convex vs. Modular Arithmetic Space. The high-frequency oscillation in modular arithmetic creates the "Barren Plateau" phenomenon where gradient information is effectively lost.

Figure 6: Empirical verification of the cryptographic optimization framework: (a) Runtime performance under scaling cryptographic constraints (

N=500

), contrasting the operational variance and lower mean execution time of the Miller-Rabin test against the Solovay-Strassen baseline; (b) Computational overhead verification demonstrating compliance with the core architectural boundary condition, where the proposed ML infrastructure remains significantly cheaper than a single hardware modular exponentiation.

Optimization Paradigm	Cryptographic Application	Mechanism of Action	Constraint / Limitation
Gradient Descent (Adam, RMSprop)	Neural Cryptanalysis	Continuous weight updates	Fails due to barren plateaus in high-frequency modular arithmetic Takhanov et al. (2023) .
Bayesian Optimization	Search Grid Tuning	Surrogate probabilistic models	Computationally expensive scaling GP models for massive sample budgets.
Policy Gradients ( Sutton et al., 2000 )	Dynamic Cache & Buffer Tuning	Reinforcement over execution telemetry	Requires continuous statistical sampling and validation of state transitions ( Alabed, 2019 ) .
Supervised Machine Learning	Intelligent Witness Selection	Predictive targeting of prime bases	Classifier overhead must remain smaller than modular exponentiation cost.

Table 2: Optimization Paradigms in Algorithmic Number Theory

Figure 7: Global Architectural Flowchart of the hybridized, adaptive primality testing framework. The diagram illustrates the quantum-anchored generation phase and the dynamic selection of algorithmic pathways based on input topology and hardware constraints.

Cybersecurity

Cybersecurity develops methods to protect digital and cyber-physical systems from attacks, vulnerabilities, data loss, and misuse.

See all 355 papers

Piercing Gilbreath's Conjecture: From Deep Number Theory Insights to Fintech and Cybersecurity
Jul 5, 2026Vincent Granville
AI-Driven Adaptive Adversaries and the Erosion of Cryptographic Trust in Public Key Systems
May 23, 2026Petar RadanlievAdversarial Attacks Cybersecurity
Department of Computer Sciences, University of Oxford, Wolfson Building, Parks Rd, Oxford OX1 3QG · The Alan Turing Institute, British Library, 96 Euston Rd., London NW1 2DB
Prime Fourier Embeddings: A Principled Basis for Modular Arithmetic
Jun 22, 2026Hyunsang Hwang, Suhyun Bae, Donghun LeeFourier Feature Embeddings Representation Learning
Department of Mathematics, Korea University, Seoul, South Korea.

Jul 5, 2026J/K move · Enter open · S save

Piercing Gilbreath's Conjecture: From Deep Number Theory Insights to Fintech and Cybersecurity

Vincent Granville

Open paper AskPDF arXiv

I propose a new methodology to attack the fascinating Gilbreath's conjecture about prime numbers, first posted in 1878 and unsolved to this day. The problem statement is rudimentary: kids can understand it. However, despite decades of research, almost no progress has been made. This paper changes the game by presenting a new approach based on sieving, a number of new results with proof, a precise path to the solution, and solid references. It also introduces the concept of reverse sieving, along with applications to testing randomness, pattern and fraud detection, cybersecurity, synthetic data, sequence categorization and normalization, or to detect and quantify a new type of chaos in time series including Brownian motions. Magic primes, forbidden prime number constellations, cellular automata, and reduction via classes of equivalent sequences, are some of the innovative and promising topics discussed in the paper.

Abstract

Cybersecurity

Explore similar work

Piercing Gilbreath's Conjecture: From Deep Number Theory Insights to Fintech and Cybersecurity

AI-Driven Adaptive Adversaries and the Erosion of Cryptographic Trust in Public Key Systems

Prime Fourier Embeddings: A Principled Basis for Modular Arithmetic