New algorithms for finding irreducible polynomials over finite fields
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 283-290
- https://doi.org/10.1109/sfcs.1988.21944
Abstract
An algorithm is presented for finding an irreducible polynomial of specified degree over a finite field. It is deterministic and runs in polynomial time for fields of small characteristics. A proof is given of the stronger result, that the problem of finding irreducible polynomials of specified degree over a finite field K is deterministic-polynomial-time reducible to the problem of factoring polynomials over the prime field of K.Keywords
This publication has 13 references indexed in Scilit:
- A knapsack-type public key cryptosystem based on arithmetic in finite fieldsIEEE Transactions on Information Theory, 1988
- A time-randomness tradeoff for oblivious routingPublished by Association for Computing Machinery (ACM) ,1988
- Randomized algorithms and pseudorandom numbersPublished by Association for Computing Machinery (ACM) ,1988
- Factoring polynomials and primitive elements for special primesTheoretical Computer Science, 1987
- Realistic analysis of some randomized algorithmsPublished by Association for Computing Machinery (ACM) ,1987
- Factorization of multivariate polynomials over finite fieldsMathematics of Computation, 1985
- Riemann hypothesis and finding roots over finite fieldsPublished by Association for Computing Machinery (ACM) ,1985
- Probabilistic Algorithms in Finite FieldsSIAM Journal on Computing, 1980
- Schnelle Multiplikation von Polynomen ber K rpern der Charakteristik 2Acta Informatica, 1977
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970