Search for polynominals
Inhaltsverzeichnis

Development of
Algorithmic Constructions
11:05:11
DeutschEnglish
18.Apr 2024

Prime generators on quadric irreducible polynomials

This is a collection of different polynomials of the form f(x)=ax^2+c .
The searched polynomials should fulfill the following conditions:
  1. The term b resp. bx should be equal 0, so that the parabel is symmetrical to the y-axis
  2. The polynomial should be irreducible.
  3. gcd (a,c) should be equal 1.
  4. c should be a prime number or equal 1, so that f(0) is not a composite value.
  5. a*c should be a prime number or equal 1, so that the discriminant D=-4ac is a prime after dividing by the quadrat 4 as often as possible.
  6. Every polynomial should construct a special sequence of primes by the following described algorithm,
    where at least the sequence of the sieved prime numbers is infinite.
    The sieved out primes appear in an non arising order in opposite to the sieve of Eratosthenes.

The algorithm

The following described algorithm is the simplest algorithm which calculate an infinite sequence of primes.
The algorithm can be improved of course by several means, but for the understanding the algorithm is limited to this simple form:
  1. All sequences start with x=0 and f(0)=|c| should be a prime number or equal 1.
  2. All values f(x)=ax^2+c for x=0 up to n_max with x element N are precalculated.
  3. If f(0) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  4. If f(1) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  5. If f(2) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  6. Step for step the primes at the position f(x) with increasing x are eliminated in the sequence,
    so that only primes either as result of the function or either as reducible primes respectively as rest of divisions remain.

Calculation and sort order

  1. The following loop for a, c was made:

    for a={1, 2, 3, 4}
       for c={1, -1, 2, -2, 3, -3, 5, -5 for all primes up to 100, -100}
        calculate the discriminant of f(x)=ax^2+c
       end_for;
    end_for;

    The discriminant=-4ac was calculated and all suitable polynomials were choosen.
    For other values no suitable polynomials were found.

Normally every prime p(x) sieves twice the following values of the polynomial for the values x+k*p and p-x+k*p.
Dependent on the discriminant there are two possibilites:

  1. The discriminant is of the form -4^n. All primes sieve twice the values of the polynomial
  2. The discriminant is of the form -4^n multiply by a prime. This prime sieves only one time the values of the polynominal, all other primes sieve twice the values of the polynomial

Results

There are 19 different polynomials with 14 different discriminants.
Every polynomial creates a sequence which includes half of the primes depending on the discriminant of the polynomial.

There are :
4 polynomials with a=1,
2 polynomials with a=2,
1 polynomials with a=3,
12 polynomials with a=4.

You will find an implementation in pseudo code of the algorithm, some mathematical proofs and the distribution of the primes by following the link of the polynomial.

In the following table you find all polynomials listed and the according reduced discriminant (divided by 4 as often as possible).


reduced original polynomial
discriminant; discriminant;

-2

-8

x²+2

-1

-4

x²+1

2

8

x²-2

3

12

x²-3


-2

-8

2x²+1

2

8

2x²-1


3

12

3x²-1

-7

-112

4x²+7

-3

-48

4x²+3

-1

-16

4x²+1

3

48

4x²-3

5

80

4x²-5

7

112

4x²-7

11

176

4x²-11

17

272

4x²-17

23

368

4x²-23

47

752

4x²-47

83

1328

4x²-83

167

2672

4x²-167