A Summation-Based Algorithm For Integer Factorization

• URL: http://arxiv.org/abs/2504.21168v1
• Date: Tue, 29 Apr 2025 20:35:43 GMT
• Title: A Summation-Based Algorithm For Integer Factorization
• Authors: Justin Friedlander,
• Abstract summary: This paper introduces a new method that converts an integer into a sum in base-2.<n>It plays a crucial role in modern cryptography, notably, in the security of RSA encryption.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Numerous methods have been considered to create a fast integer factorization algorithm. Despite its apparent simplicity, the difficulty to find such an algorithm plays a crucial role in modern cryptography, notably, in the security of RSA encryption. Some approaches to factoring integers quickly include the Trial Division method, Pollard's Rho and p-1 methods, and various Sieve algorithms. This paper introduces a new method that converts an integer into a sum in base-2. By combining a base-10 and base-2 representation of the integer, an algorithm on the order of $\sqrt{n}$ time complexity can convert that sum to a product of two integers, thus factoring the original number.

Related papers

• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals. The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting.<n>Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• The Evolution of Cryptography through Number Theory [55.2480439325792]
  cryptography began around 100 years ago, its roots trace back to ancient civilizations like Mesopotamia and Egypt.<n>This paper explores the link between early information hiding techniques and modern cryptographic algorithms like RSA.
  arXiv  Detail & Related papers  (2024-11-11T16:27:57Z)
• SAT and Lattice Reduction for Integer Factorization [5.035245337299788]
  We describe a new hybrid SAT and computer algebra approach to solve random leaked-bit factorization problems. Our implementation solves random leaked-bit factorization problems significantly faster than either a pure SAT or pure computer algebra approach.
  arXiv  Detail & Related papers  (2024-06-28T17:30:20Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  We provide efficient algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell [STOC 2022]
  arXiv  Detail & Related papers  (2024-02-21T15:06:51Z)
• Low-Complexity Integer Divider Architecture for Homomorphic Encryption [5.857929080874288]
  Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided.
  arXiv  Detail & Related papers  (2024-01-19T23:53:59Z)
• A new lightweight additive homomorphic encryption algorithm [0.0]
  This article describes a lightweight additive homomorphic algorithm with the same encryption and decryption keys. It reduces the computational cost of encryption and decryption from modular exponentiation to modular multiplication.
  arXiv  Detail & Related papers  (2023-12-12T05:12:20Z)
• Fast multiplication by two's complement addition of numbers represented as a set of polynomial radix 2 indexes, stored as an integer list for massively parallel computation [0.0]
  The 'polynomial integer index multiplication' method is a set of algorithms implemented in python code. We demonstrate the method to be faster than both the Number Theoretic Transform (NTT) and Karatsuba for multiplication within a certain bit range.
  arXiv  Detail & Related papers  (2023-11-16T14:21:13Z)
• Integer Factorisation, Fermat & Machine Learning on a Classical Computer [0.0]
  We use Lawrence's extension of Fermat's factorisation algorithm to reduce the integer factorisation problem to a binary classification problem. To address the classification problem, based on the ease of generating large pseudo--random primes, a corpus of training data, as large as needed, is synthetically generated.
  arXiv  Detail & Related papers  (2023-07-16T22:39:00Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.