I have studied a random method to generate an irreducible polynomial of degree $d$ over $\Bbb{F}_p$. Now I am reading a paper in which they study a deterministic method to find such an irreducible polynomial.

With deterministic it is meant that it will always output the same polynomial (not random), and we won't try a bunch of polynomials in a certain order until we find one that is irreducible.

Now I am wondering, why are mathematicians interested in a deterministic method? Is it faster ? Are there certain benefits of the result not being random ? Another reason ?

  • 1
    $\begingroup$ A determinsitic method is guqranteed to deliver a result in finite time. But when you ask why we are interested in a deterministic method to solve problem X when you yourself study probabilistic methods to solve problem X - isn't the first question: Why are we inerested in solving problem X at all? $\endgroup$ May 4, 2017 at 10:50

1 Answer 1


Any random method can be made deterministic in the sense that it always produces the same output by choosing a specific pseudorandom number generator and seeding it in a consistent manner.

However, determinism has another property: it always finishes in a bounded finite time. With a probabilistic method you can theoretically get unlucky and take an incredibly long time to find the answer.

  • $\begingroup$ If you use a pseudo random generator with the same seed then in fact you are just going over a bunch of polynomials in a 'certain order', which is as stated, not what we want. $\endgroup$ May 4, 2017 at 11:04
  • $\begingroup$ @JannesBraet I also specifically mentioned that there are multiple aspects of determinism, and that bounded time is another aspect that the fixed random number generator cannot provide. $\endgroup$
    – orlp
    May 4, 2017 at 11:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .