Factoring with Cyclotomic Polynomials
The authors generalize several methods for factoring \(N=pq\dots\) by algorithms of the ``\(p-1\) type. Take the \(k\)-cyclotomic field determined by the polynomial \(\Phi(x)\) so \(x^k-1=\Phi (x)\Psi(x)\) (for the ``\(p-1\) type, \(k=1\) and \(\Phi =x-1)\). Choose a ``lucky \(t\) in a subfield of prime order, and hope that for some \(i\) \((\le k)\) we can find \(p\) as the gcd of \(N\) and the coefficients of \(t^{\Psi (\sigma^i)E}-1,\) for \(\sigma\) the Frobenius symbol. Here \(E\) is a ``small factorial, just large enough to be divisible by \(\Phi(p)\), with more luck. An analysis made by the ERH shows that the luck is polynomially viable in a probabilistic sense, and it is better to have \(t\) in a higher field than \(\mathbb Q\), because we can expect different Artin residue symbols for \(p,q,\ldots\) to produce a gcd which will split the different factors in \(N\). The method is illustrated for \(k=6\), \(\Phi =x^2-x+1\), and it requires an algebraic system (MACSYMA) to handle the polynomials modulo \(N\) involved in calculating powers of \(t\) in \(\mathbb Q(t)\). [See \textit{H. C. Williams} and \textit{J. S. Judd}, Math. Comput. 30, 867--886 (1976; Zbl 0342.10007)].
- scientific article; zbMATH DE number 4069018
- scientific article; zbMATH DE number 4069025
- Factoring Multivariate Polynomials over Algebraic Number Fields
- scientific article; zbMATH DE number 4165009
- Factoring Polynomials over Algebraic Number Fields
- Factoring polynomials over finite fields
- scientific article; zbMATH DE number 3749093
- Factoring polynomials over p-adic fields
- Factoring N=p^rq for large r
- scientific article; zbMATH DE number 1222138
- A bound for the least prime ideal in the Chebotarev density theorem
- A generalization of Lehmer's functions
- A Monte Carlo Factoring Algorithm With Linear Storage
- A p + 1 Method of Factoring
- Algebraic coding theory
- Determination of the Primality of N by Using Factors of N 2 ± 1
- Factoring integers with elliptic curves
- Factorization and Primality Tests
- Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers
- scientific article; zbMATH DE number 3460351 (Why is no real title available?)
- scientific article; zbMATH DE number 3563269 (Why is no real title available?)
- scientific article; zbMATH DE number 3221502 (Why is no real title available?)
- scientific article; zbMATH DE number 3245597 (Why is no real title available?)
- scientific article; zbMATH DE number 3307642 (Why is no real title available?)
- scientific article; zbMATH DE number 3335234 (Why is no real title available?)
- Introduction to cyclotomic fields
- Moderne Algebra. Unter Benutzung von Vorlesungen von E. Artin und E. Noether, Teil 1. 3. verb. Aufl
- Number fields
- Riemann's hypothesis and tests for primality
- Some Algorithms for Prime Testing Using Generalized Lehmer Function
- Some effective cases of the Brauer-Siegel theorem
- Sums of Divisors, Perfect Numbers and Factoring
- What is a Reciprocity Law?
- Algorithms for exponentiation in finite fields
- Prime-number algorithm for public-key systems
- Sequences of numbers generated by addition in formal groups and new primality and factorization tests
- Fast generation of prime numbers and secure public-key cryptographic parameters.
- Mathematical problems in cryptology
- On the oracle complexity of factoring integers
- Sieve algorithms for perfect power testing
- A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
- On Computing Factors of Cyclotomic Polynomials
- scientific article; zbMATH DE number 3889669 (Why is no real title available?)
- Diffie-Hellman Oracles
- Explicit Bounds for Primality Testing and Related Problems
- A deterministic version of Pollard's p-1 algorithm
- scientific article; zbMATH DE number 4079497 (Why is no real title available?)
- scientific article; zbMATH DE number 107574 (Why is no real title available?)
- scientific article; zbMATH DE number 165169 (Why is no real title available?)
- Newman cyclotomic polynomials, refinable splines and the Euler binary partition function
- Explicit bounds for primes in residue classes
- Counting the Integers Factorable via Cyclotomic Methods
- Constructing nonresidues in finite fields and the extended Riemann hypothesis
- Using number fields to compute logarithms in finite fields
- A method to solve cyclotomic norm equations f f
- Factoring polynomials over special finite fields
- Abelian groups, Gauss periods, and normal bases
- Fast norm computation in smooth-degree abelian number fields
- Factoring integers and oracles for elliptic and hyperelliptic curves
- Factorization, malleability and equivalent problems
- Optimal strong primes
This page was built for publication: Factoring with Cyclotomic Polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3809851)