Find "prime polynomials" for a user's given prime, bounds, and degree

Question

Very amateur programmer and first-time poster here.

The program I wrote asks the user for a prime number, a lower and upper bound, and a degree (all of these are integers). I want to generate a list of polynomials, represented by its coefficients (see example). Each polynomial \$P(x)\$ satisfies the following conditions:

1. \$P(x) + p\$ is prime for \$1 \le x \le p - 2\$ (where \$x\$ is an integer), and \$P(0) = 0\$.

2. Each coefficient is an integer and is confined by the user's bounds inclusively (i.e., the coefficient may equal a bound but may not be less/greater than it).

3. The highest degree a polynomial can have is the user's given degree. (The user may choose to include just polynomials with this degree or polynomials with lower degrees in the final list).

The program then finds each polynomial with these conditions and prints a list of primes that it generates.

Example:

Enter the prime number you want to find a poly for: 11 

Enter the lower bound: -3

Enter the higher bound: 3

Enter the degree of the polynomial: 3

Press n if you do not want to include lower degree polynomials: n

possible combos (including constant func): 
215

################################################

poly generating finished

[[11, -2, 0, 2]]

List of primes that [11, -2, 0, 2] generates: 
[11, 11, 23, 59, 131, 251, 431, 683, 1019, 1451]

There are 1 good polynomials for 11 with bounds -3  to 3 inclusive up to degree 3

Here, \$[11, -2, 0, 2]\$ represents \$p=11\$ with the polynomial \$- 2x + 2x^3\$.

The general idea is that we start with a polynomial where every coefficient is the lower bound, check if the polynomial is a "good" or "prime" polynomial (satisfies the first condition), and add it to the list of prime polynomials if it is. Repeat with the next polynomial (list of numbers) until every combination has been exhausted.

from math import sqrt; from itertools import count, islice
import itertools
from itertools import product


#is n prime?
def isPrime(n):
    #https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

#find P(x) using the polyList to represent the polynomial
def findSingleValue(polyList, x):

    #https://stackoverflow.com/questions/18093509/how-can-i-create-functions-that-handle-polynomials
    return sum((a*x**i for i,a in enumerate(polyList)))



#is the polynomial prime for x <= p - 1?
def isPolyPrime(polyList, prime):
    #polyValue = 0
    for x in range(prime - 1):
        polyValue = sum((a*x**i for i,a in enumerate(polyList)))
        if not isPrime(polyValue):
            return False

    return True

#generate the next combo, given the previous combo
def genCombo(combo, LB, HB):
    deg = len(combo)
    combo = list(combo)
    index = deg - 1
    while index >= 0:
        if combo[index] < HB:
            combo[index] += 1
            index = -1
        elif combo[index] == HB:
            combo[index] = LB
        index -= 1
    combo = tuple(combo)
    return combo



#main function
def verifyPrime():

    prime = int(input("Enter the prime number you want to find a poly for: "))
    LB = int(input("Enter the lower bound: "))
    HB = int(input("Enter the higher bound: "))
    deg = int(input("Enter the degree of the polynomial: "))
    lowDegPoly= input("Press n if you do not want to include lower degree polynomials: ")

    allCombosNum = (abs(HB - LB))**deg - 1



    #creates list of all possible tuples that represent a poly


    print("possible combos (including constant func): ")
    print(allCombosNum)

    goodPolyList = []

    combo = ()

    #create the first combo - this is used as the basis to generate more combos
    for x in range(deg):
        combo += (LB,)



    for x in range(allCombosNum):
        polyList = []
        polyList.append(prime)
        for coef in combo:
            polyList.append(coef)
        #now has a list of the prime and coefs; p + a1*x + a2*x^2 + ...
        isGoodPoly = isPolyPrime(polyList, prime)
        if isGoodPoly and not(lowDegPoly == "n" and combo[deg - 1] == 0):
            goodPolyList.append(polyList)


        #personal usage: keeps track of how many more combos it needs to go through
        numLeft = allCombosNum - x
        if (numLeft % 100000) == 0:
            print(numLeft)


        #create the next combo
        combo = genCombo(combo, LB, HB)


    print("################################################")
    print("poly generating finished")
    print()
    print(goodPolyList)

    #bonus stuff

    #goes over items in the goodPolyList and shows what primes each generates

    for item in goodPolyList: 

        primeList = []
        for x in range(prime - 1):
            primeList.append(findSingleValue(item, x))
        print()
        print("List of primes that" , item, "generates: ")
        print(primeList)

    print()

    print("There are" , len(goodPolyList) , "good polynomials for", prime ,
         "with bounds" , LB , " to" , HB, "inclusive up to degree" , deg)

    verifyPrime()

verifyPrime()

(As you see I've used a couple snippets of code from stackoverflow. Admittedly this is for simplicity's sake as I don't quite understand them.)

I am mostly concerned with speed since I intend to go through a very high amount of polynomials. However, since I am still very new at this, any feedback is appreciated, particularly in keeping code clean, comments/variable names -- basic stuff (but again, any feedback is fine). If it matters, this code will be for my personal use and not for any school assignment/project.

Answer 1

Firstly, on documentation: the standard term for the object you're searching for is prime-generating polynomial. "Prime polynomial" is often used as a synonym for "irreducible polynomial", and while there is a relationship between reducibility and generation of primes it's best to use standard terms in documentation where possible.

---

from math import sqrt; from itertools import count, islice
import itertools
from itertools import product

This looks a bit untidy. It's not very Pythonic to put multiple statements on a line separated by ;. The import itertools is unnecessary, because you explicitly import all of the itertools methods that you use. The two from itertools import statements can be combined into one.

---

#is n prime?
def isPrime(n):
    #https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

This is a reasonable way to check a single number for primality if the number isn't too large, but since you're checking lots of numbers and you mention this as a performance concern, I would suggest that you think about building a sieve of Eratosphenes for smallish numbers (up to say 10 million or 100 million) and using probabilistic primality testing for numbers larger than that. Perhaps BPSW.

---

#find P(x) using the polyList to represent the polynomial
def findSingleValue(polyList, x):

    #https://stackoverflow.com/questions/18093509/how-can-i-create-functions-that-handle-polynomials
    return sum((a*x**i for i,a in enumerate(polyList)))

The name suggests a search, but it's actually an evaluation. I'd call it something like evalPoly(coeffs, x). The evaluation can be made more efficient using Horner's method, which can be written as a reduce call.

It would be worth adding a docstring to document the order of the coefficients: constant term first (a_0, ..., a_n) or last (a_n, ..., a_0).

---

#is the polynomial prime for x <= p - 1?
def isPolyPrime(polyList, prime):
    #polyValue = 0
    for x in range(prime - 1):
        polyValue = sum((a*x**i for i,a in enumerate(polyList)))

Why is this duplicating the contents of findSingleValue rather than calling it?

        if not isPrime(polyValue):
            return False

    return True

Why not use all(...)?

---

#generate the next combo, given the previous combo
def genCombo(combo, LB, HB):
    deg = len(combo)
    combo = list(combo)
    index = deg - 1
    while index >= 0:
        if combo[index] < HB:
            combo[index] += 1
            index = -1
        elif combo[index] == HB:
            combo[index] = LB
        index -= 1
    combo = tuple(combo)
    return combo

I'd half expect permtools to have a built-in method for this. Alternatively it can be done with (untested code) itertools.product(range(LB, HB+1), deg).

---

#main function
def verifyPrime():

    prime = int(input("Enter the prime number you want to find a poly for: "))
    LB = int(input("Enter the lower bound: "))
    HB = int(input("Enter the higher bound: "))
    deg = int(input("Enter the degree of the polynomial: "))
    lowDegPoly= input("Press n if you do not want to include lower degree polynomials: ")

This could use a refactor: one method to do the work, and then the main method just does the I/O.

---

    allCombosNum = (abs(HB - LB))**deg - 1

I think this has an out-by-one error.

---

    combo = ()

    #create the first combo - this is used as the basis to generate more combos
    for x in range(deg):
        combo += (LB,)

My suggestion above would make this unnecessary, but... tuple(repeat(LB, deg))?

---

        polyList = []
        polyList.append(prime)
        for coef in combo:
            polyList.append(coef)

I think this is polyList = [prime] + list(combo)

---

        #now has a list of the prime and coefs; p + a1*x + a2*x^2 + ...
        isGoodPoly = isPolyPrime(polyList, prime)
        if isGoodPoly and not(lowDegPoly == "n" and combo[deg - 1] == 0):
            goodPolyList.append(polyList)

There's a potential performance improvement here. If lowDegPoly == "n" then it's more efficient to avoid generating and testing polynomials of lower degree.

---

        primeList = []
        for x in range(prime - 1):
            primeList.append(findSingleValue(item, x))

primeList = [findSingleValue(item, x) for x in range(prime - 1)]

---

    verifyPrime()

verifyPrime()

That recursive call is rather inelegant, and the direct invocation of the main method is not considered best practice. It would be better to replace these lines with

if __name__ == "__main__":
    while True:
        verifyPrime()