Factoring integers with elliptic curves
This paper gives a factorization method, which uses the multiplicative groups of elliptic curves over finite fields. The factorization method is probabilistic, with a conjectured expected running time for the factorization of n to be at most \((\log n)^ 2 \exp ((1+o(1))\sqrt{\log n\quad \log \log n}),\) for \(n\to \infty\). If the smallest prime factor of n is much smaller than \(\sqrt{n}\), the running time is expected to be shorter. The elliptic curve factoring method is inspired by Pollard's (p-1) factoring method. Instead of using the multiplicative group ( \({\mathbb{Z}}/n{\mathbb{Z}})^*\) in the Pollard method, the multiplicative group of an elliptic curve over \({\mathbb{Z}}/n{\mathbb{Z}}\) is used. Since the author does not want (and does not need) to go into the details of elliptic curves over finite rings he treats only elliptic curves over finite fields. In fact he only needs results for fields with a prime number of elements. Let \({\mathbb{F}}_ p\) be the finite field with p elements. The paper gives facts about the number of elliptic curves, over \({\mathbb{F}}_ p\), whose number of points is in a given subset of \({\mathbb{N}}\). Moreover he computes how many numbers in a given interval of \({\mathbb{N}}\) are completely composed of small prime factors. These results are combined to compute the expected run time of the algorithm. Unfortunately in this computation an unproven conjecture from analytic number theory was needed. However, it seems that the conjecture is true. At the end of the paper a comparison is made between the elliptic curve method and other factoring methods. One of the advantages of the elliptic curve method is that the storage requirements are much less than those for other methods of the same expected run time. It appears that the elliptic curve method is the fastest factorization method, with an exception for the quadratic sieve, for numbers composed of two prime numbers of about the same size. In addition, it seems favorable to use the elliptic curve method as a subroutine for other factoring methods.
- scientific article; zbMATH DE number 3959522
- Elliptic curve and integer factorization
- scientific article; zbMATH DE number 515378
- scientific article; zbMATH DE number 1916745
- scientific article; zbMATH DE number 5281877
- Integer factoring problem and elliptic curves over the ring \(\mathbb Z_n\)
- Factoring N = pq^2 with the elliptic curve method
- scientific article; zbMATH DE number 527349
- scientific article; zbMATH DE number 475434
- Elliptic curve implementation of zero-knowledge blobs
- Efficient randomized generation of optimal algorithms for multiplication in certain finite fields
- Cyclicity statistics for elliptic curves over finite fields
- Modifications to the number field sieve
- Integers without large prime factors
- Zeta functions, one-way functions, and pseudorandom number generators.
- Factoring RSA moduli with primes sharing bits in the middle
- Elliptic curves in isogeny classes
- RSA: a number of formulas to improve the search for p+q
- An elliptic curve analogue to the Fermat numbers
- Use of SIMD-based data parallelism to speed up sieving in integer-factoring algorithms
- Rigorous analysis of a randomised number field sieve
- CRT-based fully homomorphic encryption over the integers
- Metrics on the sets of nonsupersingular elliptic curves in simplified Weierstrass form over finite fields of characteristic two
- Average Frobenius distributions for elliptic curves with 3-torsion
- Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
- Approximating rings of integers in number fields
- Fast group operations on elliptic curves in Maple
- Prime-number algorithm for public-key systems
- Factoring with the quadratic sieve on large vector computers
- On counting and generating curves over small finite fields
- Some computational problems of cryptographic significance concerning elliptic curves over rings
- Fast generation of prime numbers and secure public-key cryptographic parameters.
- On the oracle complexity of factoring integers
- The distribution of the number of points modulo an integer on elliptic curves over finite fields
- Generic hardness of inversion on ring and its relation to self-bilinear map
- Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields
- Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices
- A new public key cryptosystem based on Edwards curves
- On the representation of the number of integral points of an elliptic curve modulo a prime number
- New number-theoretic cryptographic primitives
- Factoring with hints
- Strongly nonzero points and elliptic pseudoprimes
- Faster cofactorization with ECM using mixed representations
- Arithmetic statistics and noncommutative Iwasawa theory
- Strong pseudoprimes to base 2
- Modular curves over number fields and ECM
- Elliptic curve and integer factorization
- Variations in the distribution of principally polarized abelian varieties among isogeny classes
- On the elliptic curve y^2= x^3-2rDx and factoring integers
- Realistic analysis of some randomized algorithms
- One-way permutations on elliptic curves
- An improved parallel block Lanczos algorithm over GF(2) for integer factorization
- Refined analysis to the extended tower number field sieve
- Sieve algorithms for perfect power testing
- Elliptic curves with large torsion and positive rank over number fields of small degree and ECM factorization
- Sums of Euler products and statistics of elliptic curves
- Computing the endomorphism ring of an ordinary abelian surface over a finite field
- Elliptic curve cryptography: the serpentine course of a paradigm shift
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Cryptanalysis of ISO/IEC 9796-1
- Constructing elliptic curves over finite fields using double eta-quotients
- Index calculation attacks on RSA signature and encryption
- On RSA moduli with prescribed bit patterns
- On computing ord\(_{N}(2)\) and its application
- Recovering Fourier coefficients of some functions and factorization of integer numbers
- Some remarks on primality proving and elliptic curves
- Smoothness testing of polynomials over finite fields
- Arithmetic of the level four theta model of elliptic curves
- Statistics about elliptic curves over finite prime fields
- The distribution of class groups of function fields
- Revisiting prime power RSA
- Factoring \(n\) and the number of points of Kummer hypersurfaces \(\bmod n\)
- Distribution of elliptic twin primes in isogeny and isomorphism classes
- Sato-Tate, cyclicity, and divisibility statistics on average for elliptic curves of small height
- Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting)
- On oracle factoring of integers
- Elliptic curve factorization using a ``partially oblivious function
- Special prime numbers and discrete logs in finite prime fields
- A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
- Quadratic sieving
- Large-order multiple recursive generators with modulus \(2^{31}-1\)
- A new attack on three variants of the RSA cryptosystem
- Adversary-dependent lossy trapdoor function from hardness of factoring semi-smooth RSA subgroup moduli
- Extended tower number field sieve: a new complexity for the medium prime case
- On the Sato-Tate conjecture on average for some families of elliptic curves
- Average Frobenius distribution for the degree two primes of a number field
- An integer factoring algorithm based on elliptic divisibility sequences
- Factoring multi-power RSA moduli with primes sharing least or most significant bits
- An efficient deterministic test for Kloosterman sum zeros
- On group structures realized by elliptic curves over a fixed finite field
- Crypto galore!
- Computational Number Theory and Cryptography
- Amicable pairs and aliquot cycles on average
- Lang-Trotter and Sato-Tate distributions in single and double parametric families of elliptic curves
- Subgroup security in pairing-based cryptography
- New Attacks on RSA with Moduli N = p r q
- Factoring RSA moduli with weak prime factors
- Small discriminants of complex multiplication fields of elliptic curves over finite fields
- Finding ECM-friendly curves through a study of Galois properties
- JKL-ECM: an implementation of ECM using Hessian curves
- Average Frobenius distribution for elliptic curves defined over finite Galois extensions of the rationals
- An exploration of affine group laws for elliptic curves
- A p-adic algorithm to compute the Hilbert class polynomial
- A generic approach to searching for Jacobians
- On the asymptotic effectiveness of Weil descent attacks
- Binary Huff Curves
- Information and computation: Classical and quantum aspects
- Sufficient conditions for factoring a class of large integers
- Computing Hilbert class polynomials with the Chinese remainder theorem
This page was built for publication: Factoring integers with elliptic curves
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093665)