Analysis of a Degree Compatibility Test for Polynomial Irreducibility.

Abstract

Polynomials with integer coefficients can often be proved irreducible by considering the degrees of factors obtained modulo several different primes. This paper presents an algorithm based on this idea and analyzes the number of primes, N, required. The results show that mean (N) grows very slowly with n and is less than 5 for all < or = 200.

Document Details

Document Type
Technical Report
Publication Date
May 01, 1975
Accession Number
ADA016100

Entities

People

  • David R. Musser

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Polynomials

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • International Relations and European Studies