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
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(N) against polynomial-time alternatives such as Miller-Rabin and FastECPP.
Algorithm Framework
Time Complexity
Error Probability
Cryptographic Advantages
Vulnerabilities / Drawbacks
Fermat Test
O(klog3N)
1 for Carmichael numbers
Simple baseline implementation
Utterly defeated by Carmichael numbers AbuDaqa et al. (2020) .
Solovay-Strassen
O(klog3N)
<(1/2)k
Resolves Carmichael flaw
High overhead computing Jacobi symbols AbuDaqa et al. (2020) .
Miller-Rabin
O(klog3N)
<(1/4)k
Extremely fast, tunable certainty
Requires multiple bases for absolute security AbuDaqa et al. (2020) .
Baillie-PSW
O(klog3N)
0 for N<264
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 N0 , each step reduces the proof to a smaller probable prime qi 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 Δ , 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.
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.
This paper examines the erosion of Public Key Cryptography (PKC) security under adaptive adversarial optimisation driven by artificial intelligence. The problem addressed is the growing mismatch between algorithm-centric cryptographic security models and operational attack realities, where adversaries exploit implementation-level observability rather than breaking cryptographic primitives.
Petar Radanliev
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
Numbers have algebraic structure that standard neural embeddings often fail to expose. We introduce Prime Fourier Embeddings (PFE), which encode integers as prime-indexed (cos, sin) pairs derived from the harmonic analysis of Q, providing a pre-structured representation in which modular arithmetic reduces to selecting the relevant prime channel rather than discovering algebraic structure from scratch. We prove that any linear map equivariant with respect to the product group action on PFE must be block-diagonal with one independent block per prime -- a consequence of Schur's lemma applied to the resulting character decomposition. For square-free composite moduli, the Chinese Remainder Theorem predicts which prime channels are task-relevant. Both predictions are confirmed empirically: ablation studies show specialization ratios exceeding 500x between task-relevant and task-irrelevant channels, with perfect in-distribution test accuracy across all square-free composite moduli tested.
Hyunsang Hwang, Suhyun Bae, Donghun Lee
Department of Mathematics, Korea University, Seoul, South Korea.