A deterministic version of Pollard’s $p-1$ algorithm
From MaRDI portal
Publication:3584788
DOI10.1090/S0025-5718-09-02262-5zbMath1227.11125arXiv0707.4102MaRDI QIDQ3584788
Publication date: 30 August 2010
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0707.4102
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Number-theoretic algorithms; complexity (11Y16) Factorization (11Y05)
Related Items
Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝 ⋮ New Characterization of the Factor Refinement Algorithm with Applications ⋮ Deterministic factoring with oracles ⋮ On reducing factorization to the discrete logarithm problem modulo a composite ⋮ An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient ⋮ Integer factoring and compositeness witnesses
Cites Work
- On a problem of Oppenheim concerning Factorisatio Numerorum
- Factoring integers with elliptic curves
- Some remarks on computing the square parts of integers
- Probabilistic algorithm for testing primality
- Factoring polynomials with rational coefficients
- Self-witnessing polynomial-time complexity and prime factorization
- Riemann's hypothesis and tests for primality
- Some results on computational complexity
- PRIMES is in P
- Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝
- Explicit Bounds for Primality Testing and Related Problems
- Sums of Divisors, Perfect Numbers and Factoring
- Factoring with Cyclotomic Polynomials
- A p + 1 Method of Factoring
- A method for obtaining digital signatures and public-key cryptosystems
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- The average least witness is 2
- Divisors in residue classes, constructively
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
