EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 17, No. 4, 2024, 2431-2447
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Semi-Primitive Roots and Irreducible Quadratic Forms

Marc Wolf1,∗, François Wolf1

1 Department of Mathematical Sciences at TSoftemail, France

Abstract. Modulo a prime number, we define semi-primitive roots as the square of primitive
roots. We present a method for calculating primitive roots from quadratic residues, including semi-
primitive roots. We then present progressions that generate primitive and semi-primitive roots,
and deduce an algorithm to obtain the full set of primitive roots without any gcd calculation.
Next, we present a method for determining irreducible quadratic forms with arbitrarily large con-
jectured asymptotic density of primes (after Shanks, [1][2]). To this end, we propose an algorithm
for calculating the square root modulo p, based on the Tonelli-Shanks algorithm [3].

2020 Mathematics Subject Classifications: 11A07, 68P05, 11B05

Key Words and Phrases: Primitive roots, semi-primitive roots, irreducible quadratic forms,
asymptotic density, Fermat’s theorem on sums of two squares

1. Introduction

1.1. Primitive root modulo N

Quadratic residues and non-residues, as well as primitive roots, have given rise to an
abundant literature in mathematics (group theory with Lagrange’s and Fermat’s theo-
rems, ring and field theory, etc.). They have many applications, including cryptography,
primality tests and integer factorisation.

We recall that the group of units of the ring Z/NZ, of order φ (N) (Euler’s totient of
N), is a cyclic group if and only if N = 2, N = 4, N = pk or N = 2pk with p ∈ P\ {2} and
k ∈ N∗. For such N , a primitive root modulo N is a generator of this group. There exist
φ (φ (N)) such integers modulo N , whose powers generate every element of (Z/NZ)×. The
usual method to compute one or more primitive roots requires the prime decomposition
of φ (N). In this article, we will focus on the case N = p ∈ P⧹ {2}.

In the first section, we define semi-primitive roots and study their relationship with
primitive roots modulo p. Using these results, we present a test on quadratic residues to
determine primitive roots. Then, using recursive sequences of primitive and semi-primitive

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5372

Email addresses: marc.wolf@tsoftemail.com (M. Wolf), francois.wolf@dbmail.com (F. Wolf)

https://www.ejpam.com 2431 Copyright: © 2024 The Author(s). (CC BY-NC 4.0)



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2432

roots, we describe an algorithm determining all primitive roots without any gcd compu-
tation.

In [2], we studied the density of primes of the form X2+ c, for a fixed c ∈ N∗, based on
Shanks’ conjecture [1], which we empirically corroborated.
In the second section of this article, we will continue this study and propose new results
generalised to irreducible quadratic forms.

1.2. Basic properties, definitions and notations

Definition 1. (i) We let D (x) := {d ∈ N∗ | d|x} the set of divisors of an integer x, for
E ⊂ Z we let D (E) :=

⋃
x∈E D (x) the set of divisors of at least one element of E.

We also define Dp (E) = D (E) ∩ P the set of prime divisors of E.

(ii) For (x, y) ∈ Z∗ × N∗ we let Px,y := {p ∈ P | p ≡ x [y]}.

(iii) Let p ∈ P⧹ {2}. A semi-primitive root modulo p is defined as the square of a
primitive root in (Z/pZ)× = F∗

p.

Proposition 1. g ∈ F∗
p is a semi-primitive root if and only if the order of ⟨g⟩ =

{
gk, k ∈ Z

}
is p−1

2 .
Proof. If g is a semi-primitive root, there exists a primitive root h such as g = h2.

Since p − 1 is even and the order of ⟨h⟩ is p − 1, we deduce that the order of ⟨g⟩ is p−1
2 .

Conversely, if the order of ⟨g⟩ is p−1
2 and if h is a primitive root, let k such that g = hk.

We know that the order of ⟨g⟩ equal to p−1
gcd(k,p−1) thus gcd (k, p− 1) = 2 , i.e. we can

write k = 2u with u and p − 1 coprime. We conclude that hu is a primitive root and
g = (hu)2.

Definition 2. Let p ∈ P⧹ {2}. GZ,p (respectively GS,p, GQR,p, GQNR,p) is the set of prim-
itive roots (respectively semi-primitive roots, quadratic residues, quadratic non-residues)
modulo p. When the value of p is unambiguous, this set is simply noted GZ (respectively
GS, GQR, GQNR).

Example 1. for p = 3, we have GS = GQR = {1} and GZ = GQNR = {2}.

Proposition 2. Let p ∈ P⧹ {2}. We have GZ ⊂ GQNR and GS ⊂ GQR.
Proof. The second inclusion is immediate, since a quadratic residue is defined as a

square modulo p, and a semi-primitive root is the square of a primitive root. Moreover,
g ∈ F∗

p is either a quadratic non-residue or a quadratic residue, i.e. if h is not a quadratic

non-residue, there exists k such that g = h2k. Thus, the order of ⟨g⟩ divides p−1
2 and g is

therefore not a primitive root, hence GZ ⊂ GQNR.

Definition 3. Let p ∈ P⧹ {2} and m ∈ Z/pZ. We denote by Rp (m) the set of square
roots of m i.e.:

Rp (m) =
{
g ∈ Z/pZ

∣∣ g2 ≡ m
}
.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2433

More generally, we recursively define the sequence
(
Rk

p (m)
)
k≥0

by:

R0
p (m) = {m} , Rk+1

p (m) =
⋃

g∈Rk
p(m)Rp (g)

so that Rp (m) = R1
p (m).

We will simply note R (m) and Rk (m) when the value of p is unambiguous.
We will also note Rk for Rk (1).

Proposition 3. Rk is a subgroup of F∗
p.

Proposition 4. let p ∈ P⧹ {2} and n the highest power of 2 dividing p − 1. For any
0 ≤ k ≤ n, we have: ∣∣Rk

∣∣ = 2k

and for any 1 ≤ k ≤ n :
Rk−1 ⊂ Rk,

∣∣Rk⧹Rk−1
∣∣ = 2k−1

For k > n, we have Rk = Rn.

Proof. If h is a primitive root, we note that Rk =
{
hk, k ∈ p−1

2k
Z
}
. The first two

points follow from this. Furthermore, for k > n, F∗
p contains no element of order 2k, thus

Rk = Rn.

2. Generators and semi-generators of F∗
p

In this section, we show that GZ can be obtained from quadratic residues. We give an
algorithm that generates GZ without computing any gcd.

2.1. Determining primitives

Let p ∈ P⧹ {2}. The number of generators of the cyclic group F∗
p is equal to φ (φ (p)) =

φ (p− 1). The following property gives a constructive method for determining primitive
or semi-primitive roots.

Proposition 5. We decompose into prime factors p − 1 =
∏

q∈P q
αq . Then g ∈ F∗

p is a
primitive root if and only if:

∀q ∈ P
(
αq ≥ 1 ⇒ g

p−1
q ̸≡ 1

)
In this case we have: GZ =

{
gk, 1 ≤ k ≤ p− 2, gcd (k, p− 1) = 1

}
Moreover if p ∈ P1,4:

g ∈ GS ⇔ g ∈ GQR and ∀q ∈ P
(
αq ≥ 1 ⇒ g

p−1
2q ̸≡ 1

)
⇔ ∅ ⊊ Rp (g) ⊂ GZ .

If p ∈ P3,4:

g ∈ GS ⇔ g
p−1
2 ≡ 1 and ∀q ∈ P⧹ {2}

(
αq ≥ 1 ⇒ g

p−1
2q ̸≡ 1

)
.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2434

In this second case, only one of the two square roots of any g ∈ GS is a primitive root.

Proof. Let us take g ∈ GZ . We know that the order of gk is p−1
gcd(k,p−1) . More specif-

ically, for any q ∈ P such that αq ≥ 1 (i.e. q dividing p − 1) the order of g
p−1
q is

p−1

gcd
(

p−1
q

,p−1
) = q so g

p−1
q ̸≡ 1. Furthermore, h ∈ GZ if and only if there is k coprime with

p− 1 such that h = gk.

Conversely, let g ∈ F∗
p such that for any prime q dividing p− 1, g

p−1
q ̸≡ 1. The order of g

divides p − 1. However, the hypothesis implies that it cannot be a strict divisor of p − 1,
thus g is a primitive root.
We now assume that p ∈ P1,4. By definition, g ∈ GS ⇔ ∃h ∈ GZ g = h2, i.e. g is in

GS if and only if there exists h such that g = h2 and ∀q ∈ P
(
αq ≥ 1 ⇒ h

p−1
q ̸≡ 1

)
.

Since p−1
q is always even (including when q = 2 because p− 1 is a multiple of 4), we have

h
p−1
q = g

p−1
2q hence:

g ∈ GS ⇔ g ∈ GQR and ∀q ∈ P
(
αq ≥ 1 ⇒ g

p−1
2q ̸≡ 1

)
.

Finally, g ∈ GS if and only it has two square roots h and −h, one of which at least (say
h) is an element of GZ . But then as for any prime q dividing p− 1, p−1

q is even, we have

(−h)
p−1
q = h

p−1
q ̸≡ 1, hence −h ∈ GZ too.

When p ∈ P3,4,
p−1
2 is odd and −1 is not a quadratic residue. If g ∈ GS then as in the pre-

vious paragraph, g ∈ GQR and ∀q ∈ P⧹ {2}
(
αq ≥ 1 ⇒ g

p−1
2q ̸≡ 1

)
. Conversely, assume

g = h2 and ∀q ∈ P⧹ {2}
(
αq ≥ 1 ⇒ g

p−1
2q ̸≡ 1

)
. Then ∀q ∈ P⧹ {2}

(
αq ≥ 1 ⇒ (±h)

p−1
q ̸≡ 1

)
and h

p−1
2 ∈ {±1} thus h

p−1
2 = −1 or (−h)

p−1
2 = −1. In all cases, either h or −h is a

primitive root, but never both.

2.2. Relationships between primitive and semi-primitive roots

2.2.1. Primitive roots obtained from residues

Definition 4. if h is an element of order d in a group and 0 ≤ x ≤ d we note ⟨h⟩(x) =
{h, . . . , hx}. It is a subset of the subgroup generated by h of cardinal x.
In this whole section, we let p ∈ P⧹ {2} and we write p− 1 = 2nz with z odd.

Proposition 6. Let g ∈ GQNR. For any 0 ≤ t ≤ n, the multiplicative order of g2
tz is

2n−t. In other words,
〈
g2

tz
〉
= R(n−t). Moreover, if we note b = g2

tz, with 0 < t ≤ n, for

any integer x, b2x ∈ R(n−t−1) and b2x+1 ∈ R(n−t)⧹R(n−t−1).
In particular, when t = 0, the odd powers of b are in GQNR and the even powers in GQR.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2435

Proof. The order of gz divides 2n. By Euler’s criterion, (gz)
p−1
2 ≡ (−1)z = −1, thus

gz is in GQNR and a generator of R(n). Hence, g2
tz is a generator of R(n−t). The other

assertions are immediate.

Corollary 1. Let m be a semi-primitive root. Then:
GQR = ⟨m⟩ = ⟨m⟩(z)R(n−1).

More generally, generators of GQR coincide with semi-primitive roots.

Proof. We know that GQR is the subgroup made of the roots of the polynomial
(
X

p−1
2 − 1

)
.

By definition, a semi-primitive root is of order equal to p−1
2 and thus a generator of this

subgroup, and conversely. Furthermore, we have ⟨m⟩(z) ⊂ GQR and R(n−1) ⊂ GQR hence

⟨m⟩(z)R(n−1) ⊂ GQR.

Moreover,
∣∣∣⟨m⟩(z)

∣∣∣ = z,
∣∣R(n−1)

∣∣ = 2n−1. If mkr ≡ mk
′
r
′
with 1 ≤ k ≤ k

′ ≤ z and

r, r
′ ∈ R(n−1) thus mk

′−kr
′ ≡ r hence m

2n−1
(
k
′−k

)
≡ 1. This implies k = k

′
and r ≡ r

′

follows. Thus, we have
∣∣∣⟨m⟩(z)

∣∣∣ . ∣∣R(n−1)
∣∣ = 2n−1z = p−1

2 distinct residues in ⟨m⟩(z)R(n−1)

hence ⟨m⟩(z)R(n−1) = GQR.

Proposition 7. For m a semi-primitive root, we have:
m

(
R(n)⧹R(n−1)

)
⊂ GZ .

Proof. Let r ∈ R(n)⧹R(n−1), and let us show that mr ∈ GZ . Let q be a prime factor
of p− 1 = 2nz.

If q = 2, we have (mr)
p−1
q ≡ m2n−1zr2

n−1z ≡ r2
n−1z ̸≡ 1 because rz ∈ R(n)⧹R(n−1) since

z is odd.

If q ̸= 2, we have (mr)
p−1
q ≡ m

2nz
q r

2nz
q ≡ m

2nz
q ̸≡ 1 because 2n−1z does not divide 2nz

q .
Thus, using proposition 5, we deduce that mr ∈ GZ .

Proposition 8. If p ∈ P3,4, there are as many semi-primitive roots as primitive roots,
and if p ∈ P1,4 there are half as many.

Proof. We know that there are φ (p− 1) primitive roots and, by corollary 1, φ
(
p−1
2

)
semi-primitive roots modulo p. We also know that φ (ab) = φ (a)φ (b) if a, b are coprime
and φ

(
2k
)
= 2k−1.

If p ≡ 3 [4] then n = 1 i.e. p−1
2 is odd and φ (p− 1) = φ (2)φ

(
p−1
2

)
= φ

(
p−1
2

)
.

If p ≡ 1 [4] then n ≥ 2 and φ (p− 1) = φ (2n)φ (z) = 2n−1φ (z) whereas φ
(
p−1
2

)
=

φ
(
2n−1

)
φ (z) = 2n−2φ (z).

Proposition 9. We assume p ∈ P1,4. Let m be a semi-primitive root. Then:
−m

(
R(n)⧹R(n−1)

)
⊂ GZ

Moreover, −m ∈ GS if and only if p ∈ P1,8.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2436

Proof. Let r ∈ R(n)⧹R(n−1), and let us show that −mr ∈ GZ like in proposition 7
Let q be a prime factor of p − 1 = 2nz. As p ∈ P1,4, we have n ≥ 2 so in all cases

(−mr)
p−1
q ≡ (mr)

p−1
q ̸≡ 1, because mr ∈ GZ . Therefore −mr ∈ GZ .

Moreover −m ∈ GS if and only if (−m)
p−1
2q ̸≡ 1 for any prime factor q of p−1, which is true

when n ≥ 3, because then (−m)
p−1
2q ≡ m

p−1
2q . Otherwise m

p−1
4 ≡ −1 thus (−m)

p−1
4 ≡ 1

i.e. −m /∈ GS. We hence proved that −m ∈ GS if and only if p ∈ P1,8.

Proposition 10. Let m be a semi-primitive root. We first assume p ∈ P3,4. Then
m2 ∈ GS and in particular:

m2
(
R(n)⧹R(n−1)

)
⊂ GZ

We now assume p ∈ P1,4. Then:

±m2
(
R(n)⧹R(n−1)

)
⊂ GZ

if p ∈ P1,8 then ±m2 /∈ GS. If p ∈ P5,8 then m2 /∈ GS and −m2 ∈ GS. In the last case, we
identify −GS to the set of squares of GS.

Proof. When p ∈ P3,4, n = 1 so R(n)⧹R(n−1) = {−1}. By proposition 6 we have
−m ∈ GZ hence m2 ∈ GS.

When p ∈ P1,4 i.e. n ≥ 2, let us take r ∈ R(n)⧹R(n−1) and focus on
(
±m2r

) p−1
q =(

m2r
) p−1

q with q dividing p− 1.

If q = 2 we have
(
m2r

) p−1
2 = r2

n−1z ̸≡ 1 because rz ∈ R(n)⧹R(n−1).

If q ̸= 2 we have
(
m2r

) p−1
q = m

2(p−1)
q ̸≡ 1 because p−1

2 does not divide 2(p−1)
q .

We thus proved that ±m2
(
R(n)⧹R(n−1)

)
⊂ GZ .

If p ∈ P1,8 then
(
±m2

) p−1
4 ≡ 1 and ±m2 /∈ GS.

If p ∈ P5,8 then n = 2 and
(
m2

) p−1
4 ≡ 1,

(
−m2

) p−1
4 ≡ (−1)z

(
m2

) p−1
4 ≡ −1 thus m2 /∈ GS

and −m2 ∈ GS (checking the other powers is immediate). Similarly, if m ∈ GS, −m /∈ GS

thus the square function is injective on GS, which shows that −GS is equal to the set of
squares of GS.

Propositions 9 and 10 allow to build primitive roots from semi-primitive roots and ele-
ments of R(n)⧹R(n−1).

Definition 5. For some r ∈ R(n)⧹R(n−1), we define the set G′
Z := rGZ .

Proposition 11. G′
Z is independent of the choice of r and contains GS. It has same size

as GZ and we have GZ = rG′
Z for any r ∈ R(n)⧹R(n−1). Moreover, if for k ∈ N∗ we define

GS
(k) =

{
mk, m ∈ GS

}
:

• when p ∈ P3,4, G
′
Z = GS = GS

(2) whereas GZ = −G′
Z .



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2437

• when p ∈ P5,8, G
′
Z = GS ⊔ −GS = GS ⊔ GS

(2).

• when p ∈ P9,16, G
′
Z = GS ⊔

(
GS

(2) ⊔ −GS
(2)

)
• for any p, we have:

G′
Z =

⋃n−1
t=0 GS

(2t) =
{
g ∈ F∗

p

∣∣∣ ∀q ∈ P⧹ {2}
(
q|p− 1 ⇒ g

p−1
2q ̸≡ 1

)}
.

Proof. To prove that G′
Z does not depend on r, it is enough to observe that if r, r

′ ∈
R(n)⧹R(n−1) and g ∈ GZ , we have rr

′
g ∈ GZ . This can be done using Proposition 5: we

know that r
p−1
2 ≡ r

′ p−1
2 ≡ −1 whereas if q is an odd prime factor of p−1, r

p−1
q ≡ r

′ p−1
q ≡ 1.

Proposition 7 ensures that GS ⊂ G′
Z . It is also clear that G′

Z and GZ have the same size
and that GZ = rG′

Z for any r ∈ R(n)⧹R(n−1).
Finally:

• If p ∈ P3,4, since from proposition 11 the two sets have the same size, G′
Z = GS.

Proposition 10 also ensures that GS
(2) ⊂ GS and since −1 /∈ GS the square function is

injective from GS to GS
(2) thus GS

(2) = GS. In this case we know that R(n)⧹R(n−1) =
{−1}, proposition 7 ensures GZ = −G′

Z .

• If p ∈ P5,8, proposition 10 ensures that −GS = GS
(2) is disjoint of GS and included

in G′
Z hence a cardinality argument ensures G′

Z = GS ⊔ −GS = GS ⊔ GS
(2).

• If p ∈ P1,8, proposition 5 shows that GS = −GS thus the size of GS
(2) is half that

of GS. Proposition 10 ensures GS ⊔
(
GS

(2) ∪ −GS
(2)

)
⊂ G′

Z . Remains to show that

GS
(2) is disjoint of −GS

(2) if and only if p ∈ P9,16 i.e. n = 3. If GS
(2) is not disjoint

of −GS
(2), there exists g ∈ GZ and k coprime to p − 1 such that g4k ≡ −g4, hence,

by taking odd powers coprime to p − 1, GS
(2) = −GS

(2) while on the other hand(
g

k−1
2

)8
≡ −1 ≡ (gz)2

n−1

which implies n ≥ 4. Conversely if n ≥ 4, then −1 has a

square root which leaves GS stable, thus GS
(2) = −GS

(2).

• In general, similarly to previous items, for any t ≤ n−1, GS
(2t) is the set of elements

of order p−1
2t+1 , and if moreover t ̸= n − 1 then GS

(2t) = −GS
(2t) thus by induction∣∣∣GS

(2t)
∣∣∣ = 1

2t |GS | = 1
2t+1 |GZ |. For t = n − 1 we have −GS

(2n−1) ∩ GS
(2n−1) = ∅

hence
∣∣∣GS

(2n−1)
∣∣∣ = 1

2n−1 |GZ |. We deduce that the sets
(
GS

(2t)
)
0≤t≤n−1

are pairwise

disjoint and their union has the same cardinal as GZ . Proposition 5 shows that if

r ∈ R(n)⧹R(n−1), rGS
(2t) ⊂ GZ . We must then have G′

Z =
⋃n−1

t=0 GS
(2t). Proposition

5 also shows that G′
Z =

{
g ∈ F∗

p

∣∣∣ ∀q ∈ P⧹ {2}
(
q|p− 1 ⇒ g

p−1
2q ̸≡ 1

)}
.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2438

Theorem 1. We have:

• g ∈ GZ if and only if there exists m ∈ GQR such that ∀q ∈ P⧹ {2} q|p−1 ⇒ m
p−1
2q ̸≡ 1

and r ∈ R(n)⧹R(n−1) such that g = mr.

• g ∈ GZ if and only if g ∈ GQNR and ∀q ∈ P⧹ {2} q|p− 1 ⇒ g
p−1
q ̸≡ 1.

Proof. We just need to prove the first item, the second one has already been established
in proposition 5.
The Chinese theorem identifies F∗

p to (Z/2nZ) × (Z/zZ). A primitive root g corresponds
to a pair (x, y) with x odd and y coprime to z. Let m be the element corresponding to
(2x, y) and r the element corresponding to (−x, 0). Then it is clear that g = mr but r is
of order 2n so in

(
R(n)⧹R(n−1)

)
, while the order of m is 2n−1z i.e. m is a semi-primitive

root and in particular m ∈ GQR hence ∀q ∈ P⧹ {2} q|p− 1 ⇒ m
p−1
2q ̸≡ 1.

Conversely, using this identification, m corresponds to (x, y) with x even and y coprime
to z, and r corresponds to (t, 0) with t odd. Thus mr corresponds to (x+ t, y) which is
indeed a generator of (Z/2nZ)× (Z/zZ) because x+ t is odd and y coprime to z.

2.2.2. A sequence of primitive and semi-primitive roots

Knowing a single primitive root allows to obtain every element of GZ by exponentiation.
Knowing a semi-primitive root and an element of R(n)⧹R(n−1) also allows to find one
thus every primitive root. We describe here an alternative method for generating primitive
roots.

Corollary 2. Let m ∈ GS and r ∈ R(n)⧹R(n−1) fixed, then:

∀k ∈ N∗ ∀a ∈ P⧹Dp (z) makr ∈ Gz.

Proof. We apply the first item of theorem 1. If q ∈ P⧹ {2} divides p − 1, then

m
ak(p−1)

2q ̸≡ 1 otherwise p−1
2 would divide ak(p−1)

2q , hence by Gauss’s theorem p−1
2 would

divide p−1
2q which is impossible.

Definition 6. Let a ∈ P coprime to z, the discrete logarithm of 1 to the base a modulo z,
denoted by logda (1, z) , is the multiplicative order of a modulo z, i.e. the smallest integer
k such that ak ≡ 1 [z].

Proposition 12. Let m ∈ GS, b = m2n−1
and k = logd2 (1, z) . Then:

b2
k ≡ b [p] .

Proof. By definition 2k ≡ 1 [z]. We also know that b = m2n−1
is of order z modulo p,

so b2
k ≡ b1 ≡ b.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2439

Remark 1.

• There are several algorithms to calculate the discrete logarithm, all of which take sub-
exponential time. See for example Pollard’s rho algorithm, Pohlig-Hellman algorithm
or the general number field sieve (GNFS).

• Searching for the discrete logarithm to the base 2 is adapted to the binary system
used by the computer.

Proposition 13. Let a be coprime to z. Then we have:

logda (1, z) ≤ lcm
q∈Dp(p−1)

qαq−1 (q − 1) .

Proof. The Chinese theorem gives Z/zZ ≃
∏

q∈Dp(p−1) Z/qαqZ. Therefore the unit

group (Z/zZ)× can be identified to
∏

q∈Dp(p−1) (Z/qαqZ)× and any element of this group

is of order at most lcmq∈Dp(p−1)

∣∣(Z/qαqZ)×
∣∣ = lcmq∈Dp(p−1) q

αq−1 (q − 1) . The same
applies to logda (1, z) which is the multiplicative order of a in Z/zZ.

Proposition 14. If m ∈ GZ (respectively GS, GQR, GNQR) then mp−2 ∈ GZ (respectively
GS, GQR, GNQR).

Proof. mp−2 is the multiplicative inverse of m in F∗
p. As the inverse of a generator

is a generator, GZ and GS are stable by conversion to the inverse. Moreover, GQR is a
multiplicative subgroup and GNQR its complementary, so it’s the same for these two sets.

Corollary 3. For t ∈ {0, .., n− 1}, we let at = 2n−tz − 1. For any m ∈ GZ , m2a0 ≡
m2a1 ,m2a2 , . . . ,m2an−1 are n− 1 distinct semi-primitives roots.

Proof. Clearly at is odd and coprime to z, thus also to p−1. We deduce that mat ∈ GZ

hence m2at ∈ GS. Moreover, 2 ≤ 2 × (2z − 1) = 2an−1 < · · · < 2a1 = 2 ×
(
2n−1z − 1

)
=

p− 3 so m2a1 . . .m2an−1 are pairwise distinct. Finally, 2a0 = 2p− 4 = p− 1 + p− 3 and
mp−1 ≡ 1 therefore we have m2a0 ≡ m2a1.

The following proposition gives a family of sequences of semi-generators and generators,
as well as a method to obtain each element of the sets GS and GZ .

Proposition 15. Let g ∈ GS and m
′ ∈ R(n)⧹R(n−1) fixed such that gzm

′2z ≡ 1. We
define the sequence (Ux) by:

U0 = g, Ux+1 =
(
m

′
Ux

)2

For all x ∈ N, Ux ∈ GS and m
′
Ux ∈ GZ . Moreover if 0 ≤ x < y < logd2 (1, z) , Ux ̸≡ Uy

and (Ux) is periodic of period logd2 (1, z) .
Proof. In the identification of F∗

p to (Z/2nZ)× (Z/zZ) , any element of GS corresponds

to a pair (2k, l) with k odd and l coprime to z while any elements of R(n)⧹R(n−1) corre-

spond to a pair (i, 0) with i odd. From this and the equation gzm
′2z ≡ 1, we deduce that

there is k0 odd and l0 coprime to z such that g corresponds to (2k0, l0) and m
′
to (−k0, 0).



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2440

Thus, by recurrence, we note that Ux corresponds to (2kx, lx) = (2k0, 2
xl0) where 2xl0 is

still coprime to z, so Ux ∈ GS. Similarly, m
′
Ux corresponds to (k0, 2

xl0) and we have
m

′
Ux ∈ GZ . Moreover, by definition of logd2 (1, z) , the elements of Ux are pairwise

distinct for 0 ≤ x < logd2 (1, z) and Ulogd2(1,z)
= U0 which implies the periodicity of

(Ux).

Remark 2. We verify that Ux = g2
x
m

′2(2x−1)
. In general, the elements

(
m

′
Ux

)
form

a strict subset of GZ . However, for any generator h ∈ GZ there exists a coprime to

p − 1 such that h =
(
m

′
g
)a

. We can also choose a to be prime. Thus, if we take

a ∈ P⧹D (p− 1) such that gam
′a

has not already been generated then the logd2 (1, z) first

terms U
(a)
x := g2

xam
′2a(2x−1)

will all be new elements of GZ . We deduce that there exists
a set A of φ(p−1)

logd2(1,z)
primes, odd and coprime to z, and such that:

GZ =

{
g2

xam
′(2x+1−1)a

, (a, x) ∈ ({1} ∪A)× [[0, logd2 (1, z) − 1 ]]

}
Proof. By construction we have Ux = g2

x
m

′2+···+2x
= g2

x
m

′2(2x−1)
. If h ∈ GZ , we

know that m
′
g ∈ GZ so there exists a coprime to p − 1 (i.e. odd and coprime to z) such

that h =
(
m

′
g
)a

. Dirichlet’s theorem ensures that we can choose a to be prime, even if it

means adding it a multiple of p− 1.

Identifying F∗
p to (Z/2nZ) × (Z/zZ) as in the proof of the previous results, m

′a
U

(a)
x cor-

respond to (ak0, 2
xal0). Let a, b, x, y be such that (ak0, 2

xal0) = (bk0, 2
ybl0). In particular

a. (−k0, 0) = b. (−k0, 0) thus m
′a ≡ m

′b
hence for any k ∈ N, U (a)

x+k = U
(b)
y+k from which

it follows by periodicity of these sequences that m
′b
U

(b)
0 is equal to one of the terms of(

m
′a
U

(a)
x

)
. Therefore, if we construct A recursively in such a way that m

′a
U

(a)
0 is not

among the generators already constructed, we keep adding chunks of logd2 (1, z) genera-
tors, which will eventually cover the entire set GZ .

Remark 3. For each value of a ∈ {1} ∪ A, we obtain logd2 (1, z) pairwise distinct gen-
erators. We deduce that logda (1, z) divides |GZ | = φ (p− 1) = φ (2n)φ (z). In fact, since
logd2 (1, z) is the (multiplicative) order of 2 modulo z, we know that it divides φ (z), the
order of the group (Z/zZ)×.
Remark also that logd2 (1, z) > log2 (z) since necessarily 2logd2(1,z) > z.

Corollary 4. We have logd2 (1, z) ≤ φ (z) ≤
⌊

z
logd2(1,z)

⌋
logd2 (1, z) .

Proof. As stated in the remark 3, we know that logd2 (1, z) divides φ (z). Therefore
logd2 (1, z) ≤ φ (z) and

φ (z) = φ(z)
logd2(1,z)

logd2 (1, z) ≤
⌊

z
logd2(1,z)

⌋
logd2 (1, z) .



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2441

Proposition 16. Let g and m
′
be as in proposition 15. There exists a set A of

φ( p−1
2 )

logd2(1,z)
primes, odd and coprime to z, such that:

GS =

{
g2

xam
′(2x+1−2)a

, (a, x) ∈ ({1} ∪A)× [[0, logd2 (1, z) − 1 ]]

}

If p ∈ P3,4, GZ =

{
g2

xam
′(2x+1−1)a

, (a, x) ∈ ({1} ∪A)× [[0, logd2 (1, z) − 1 ]]

}
.

If p ∈ P1,4, GZ =

{
±g2

xam
′(2x+1−1)a

, (a, x) ∈ ({1} ∪A)× [[0, logd2 (1, z) − 1 ]]

}
.

Proof. A can be constructed by induction as in remark 2, by ensuring that U
(a)
0 is a new

element of GS. Using the identification of F∗
p to (Z/2nZ) × (Z/zZ) and a, b ∈ ({1} ∪A)

distinct, suppose (2ak0, 2
xal0) = (2bk0, 2

ybl0). This means that 2xal0 ≡ 2ybl0 [z] thus,

multiplying by 2logd2(1,z) −y, U
(b)
0 is one of the

(
U

(a)
x

)
, which is impossible.

If p ∈ P3,4, remember that in this case GS and GZ have the same size. Thus, once we have
GS, we also get GZ by multiplying all elements by the suitable power of m

′
, which is −1

anyway.

When p ∈ P1,4, let us show that elements ±g2
xam

′(2x+1−1)a
are pairwise distinct. Suppose

that m
′a
U

(a)
x = ±m

′b
U

(b)
y . Then, taking the square yields that U

(a)
x+1 = U

(b)
y+1, which again

is impossible.

Remark 4. When z is a prime number, all non-residues g not in R(n) are generators. If,
additionally, p ∈ P3,4 and logd2 (1, z) = z − 1 = φ (p− 1) then A = ∅ for both remark 2
and proposition 16.

Remark 5. When p > 3 and z = 1, any of the 2n−1 non-residues is a generator, and the

sequences
(
U

(a)
x

)
are constants. Therefore we need a set A of size 2n−2 − 1 to enumerate

all the generators using Proposition 16. For example, for p = 257, we need 63 primes,
which means that we must choose primes greater than p.

Remark 6. For each generator found, proposition 14 also gives potential new genera-
tors, which can reduce the number of primes needed in remark 2 or proposition 16. This
approach is left to the reader as it seems less predictable but could prove interesting for
values of p greater than those we have tested and such that logd2 (1, z) is small, since the
density of primes goes asymptotically towards 0. Alternatively, we could “sieve” the set
{k ∈ [[1, p− 2]] | gcd (k, p− 1) = 1} by eliminating multiples of prime factors of p− 1.

2.2.3. Algorithm to obtain the set of primitive roots

The general idea of the algorithm is to search for a semi-primitive root g ∈ GS and the

associated r in R(n)
p \R(n−1)

p such that gzr2z ≡ 1. Following the proof of proposition 16, we
then construct a set A of primes to obtain the full set GZ . Let us describe the algorithm
a bit more in details below.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2442

Algorithm 1. Description: We still write p − 1 = 2nz with z odd. Q := Dp ({z}), the
set of prime divisors of z, is also assumed to be known, allowing to calculate φ (z).

(i) We iterate over the elements m in [[2, p− 2]]. For each iteration, two tests are
performed, and we go to the next step as soon as one succeeds:

• If m ∈ GQR and ∀q ∈ Q⧹ {2} m
φ(p)
2q ̸≡ 1 then (Proposition 11) m ∈ G′

Z and
we get an element r ∈ GQNR (possibly a value r < m on which we have already
performed the test). We then set gz ≡ m.rz and g ≡ gz

2.

• Otherwise m ∈ GQNR and if, in addition, ∀q ∈ Q m
φ(p)
q ̸≡ 1 then (Proposition

5) m ∈ GZ and we set gz = m and g = gz
2.

(ii) We iterate over R(n)
p \R(n−1)

p =
{
±(gz

z)2k+1, 0 ≤ k < 2n−1
}
, searching for a value

m
′
of R(n)

p \R(n−1)
p such that gzm

′2z ≡ 1.

(iii) We determine logd2 (1, z) by calculating the first terms of the sequence (Ux) (propo-
sition 11). The first value of x ≥ 1 such that Ux ≡ g is indeed x = logd2 (1, z) .

(iv) We generate odd prime numbers a1 . . . aN /∈ Dp ({z}) such that

U
(aK)
0 /∈

{
U

(ak)
x , x ∈ N, k ∈ [[0,K − 1]]

}
(where by convention U

(a0)
x := Ux) and

N =
(
φ
(
p−1
2

)
/logd2 (1, z)

)
− 1. For example, these numbers can be obtained from

Atkin’s algorithm [4] by rejecting those that are not suitable.

(v) We have thus recursively constructed GS =
{
U

(ak)
x , x ∈ N, k ∈ [[0,K − 1]]

}
and GZ ={

m
′ak

U
(ak)
x

}
when p ∈ P1,4, GZ =

{
±m

′ak
U

(ak)
x

}
otherwise.

3. Irreducible quadratic forms

In [2], we studied the density of primes in Ec =
{
X2 + c, X ∈ 2N+r

}
, with c ∈ N∗ and

r ∈ {0, 1} such that r ≡ 1− c [2]. We empirically corroborated Shanks’ conjecture, which
gives the asymptotic density of primes in Ec:

dP|Ec
(x) ∼ hc

2ln(x)

with hc =
∏

p∈P
p−tp(c)
p−1 < ∞ and tp (c) =


0 if p /∈ Dp (Ec)
1 if p|c
2 otherwise.

Here, we extend the definition of hc to integer quadratic forms by letting, for Q = aX2 +

bX + c : tp (Q) = |{x ∈ Fp | Q (x) ≡ 0 [p]}| , hQ =
∏

p∈P⧹{2}
p−tp(Q)

p−1 .
This definition extends that of hc i.e. hc = h(2X+r)2+c.
We continue this study here and present several results about hQ.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2443

3.1. Application of Fermat’s sum of two squares theorem

Theorem 2. Let c be the square of a non-zero integer. We have:

Dp (Ec) = P1,4 ∪ Dp ({c}) = P1,4 ⊔ (P3,4 ∩ Dp ({c}))

Proof. Let us write c = y2. Let p ∈ Dp (Ec), and x ∈ N such that p divides x2 + y2.
We deduce that p divides y or that −1 is a square modulo p. But −1 is a square modulo
p if and only if p ∈ P1,4, thus we have p ∈ P1,4 ∪ Dp ({y}) = P1,4 ⊔ (P3,4 ∩ Dp ({y})).
Conversely, let p ∈ P1,4 ∪ Dp ({y}). If p ∈ Dp ({y}) it is clear that p divides 02 + y2 ∈ Ec

so p ∈ Ec. Now assume p ∈ P1,4. Fermat’s sum of two squares theorem [5] ensures that
there exist a, b ∈ N∗ coprime such that p = a2 + b2. But then we note that p

(
c2 + d2

)
=

(ac− bd)2+(ad+ bc)2. Since a and b are coprime, there exist c, d ∈ Z such that ad+bc = y,
thus by letting x = |ac− bd| we obtain that x2 + y2 is a multiple of p, hence p ∈ Ec.

Proposition 17. If c is a non-zero square, we have:

hc = h1

 ∏
p∈P3,4∩Dp({c})

p− 1

p

 ∏
p∈P1,4∩Dp({c})

p− 1

p− 2


Proof. We recall that hc =

∏
p∈P⧹{2}

p−tp(c)
p−1 . Thus by theorem 2,

h1 = limn→∞

∏
p ∈ P3,4

p ≤ n

p
p−1

×

∏
p ∈ P1,4

p ≤ n

p−2
p−1


and

hc = limn→∞

∏
p ∈ P3,4\D (c)

p ≤ n

p
p−1

×

∏
p ∈ P1,4\D (c)

p ≤ n

p−2
p−1

 .

which shows indeed that hc
h1

=
(∏

p∈P3,4∩Dp({c})
p−1
p

)(∏
p∈P1,4∩Dp({c})

p−1
p−2

)
.

Corollary 5. Let h ̸= h1 ∈ R+. If there is a square c such that hc = h then there exists
an infinity of such c.

Proof. Since the formula in proposition 17 depends only on Dp ({c}) ̸= ∅, it suffices to
observe that there is an infinity of c which share the same set of prime factors.

Remark: If we choose all the prime factors of c in P1,4, then hc ≥ h1.

Proposition 18. Let a, b ∈ N such that Dp ({a}) ⊂ Dp ({c}) and b ≡ r [2]. Let Q =
(2aX + b)2+ c and EQ = {Q (x) , x ∈ N}. We assume that Dp ({c})∩Dp (EQ) = ∅. Then:

hQ = limn→∞

∏
p ∈ P⧹Dp (EQ)

p ≤ n

p
p−1

×

∏
p ∈ Dp (EQ)

p ≤ n

p−2
p−1





M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2444

Proof. We must show that tp (Q) = 2 when p ∈ Dp (EQ). As by construction EQ ⊂ Ec

and Dp ({c}) ∩ Dp (EQ) = ∅, p ∈ Dp (EQ) implies tp (c) = 2. Furthermore, Dp ({a}) ⊂
Dp ({c}) implies that 2a is invertible modulo p, so tp (Q) = 2 too.

Corollary 6. Let c ≥ 2 a square such that P1,4 ∩ Dp ({c}) = ∅. Let F = Dp ({c}) and

α ∈ (N∗)F . We set pαF =
∏

p∈F pαp, then for any b ∈ [[1, pαF − 1]] coprime to elements

of F and of opposite parity to c, the quadratic form: Qc,α,b = (2pαFX + b)2 + c verifies
hQc,α,b

= h1. Moreover if b ̸= b
′
then the terms of Qc,α,b are disjoint from those of Qc,α,b′ .

Proof. Let Q = Qc,α,b. Proposition 17 and the assumption P1,4 ∩ Dp ({c}) = ∅ yield
Dp (Ec)⧹Dp ({c}) = P1,4. However, by construction we also have
Dp (Ec)⧹Dp ({c}) = Dp (EQ), thus proposition 18 yields hQ = h1.
Assume that there exists b

′ ∈ [[1, pαF − 1]] and x, y ∈ Z such that Q (x) = Qc,α, b′ (y). We

deduce 2pαF (x± y) = −
(
b± b

′
)
which implies b = b

′
and x = y. The terms of Qc,α,b and

Qc,α,b′ are hence disjoint.

Theorem 3. There are infinitely many quadratic forms Q with disjoint terms and the
same value hQ, which can also be assumed to be arbitrarily close to any value h ≥ h1.
Two proofs of this theorem are given.

Proof.
First proof: Proposition 17 and its corollary yield that, for any subset F of P1,4, there are

infinitely many odd squares such that: hc = h1

(∏
p∈F

p−1
p−2

)
If c = y2, c

′
= y

′2 are such perfect squares then the equality x2 + y2 = x
′2 + y

′2 im-

plies
(
x− x

′
)(

x+ x
′
)

= y
′2 − y2 hence necessary x and x

′
are smaller than y

′2 − y2.

Thus we can construct quadratic forms Qk = (2X +mk)
2 + ck such that hQk

= hck =

h1

(∏
p∈F

p−1
p−2

)
.

Moreover the series
∑

p∈P1,4

1
p diverge: indeed Chebotarev’s theorem states that dP|4N+1 (x) ∼

1
2ln(x) , so

Tn :=
∑

p ∈ P1,4

en < p ≤ en+1

1
p ≥ e−(n+1)

[⌊
en+1

⌋
dP|4N+1

(
en+1

)
− ⌊en⌋ dP|4N+1 (e

n)
]
∼ e−1

2ne is

a divergent series, which implies that
∑

p∈P1,4

1
p diverges too. Additionally, 1

p→p→∞0.

Thus, we can choose F such that
(∏

p∈F
p−1
p−2

)
be arbitrarily close to h ≥ h1 fixed.

Remark: Similarly, if we choose F ⊂ P3,4 we can also make hQ arbitrarily close to
any h ∈ [0, h1].

Second proof: As in corollary 6, for any subset F of P⧹ {2} and for any square c such

that Dp ({c}) ⊂ F , we can get a, b such that: h(2aX+b)2+c = h1

(∏
p∈F∩P1,4

p−1
p−2

)
.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2445

We conclude as in the first proof: we can either take an infinity of values for c as in the
first proof, or build a sequence (ak, bk) such that ak+1 is a multiple of ak and for any l ≤ k,
bl ̸≡ bk+1 [al].

Remark: If p ∈ F ∩ P1,4⧹Dp ({c}), to ”eliminate” it, we need to determine the
solutions of X2 ≡ −c [p]. This equation is discussed in the next section.

By analogy with Shanks’ conjecture, hQ can be conjectured to be linked with the density
of prime numbers of the form Q (x) as in the following generalisation:

Assumption 1. Let Q be an irreducible quadratic form and EQ = {Q (x) , x ∈ N}. Then:

dP|EQ
(x) =

hQ

ln(x) + o
(

1
ln(x)

)
where dP|EQ

is the density of primes in EQ (see [2] for a

formal definition).

3.2. Tonelli-Shanks algorithm

There are several algorithms to calculate the square root of an integer modulo p, e.g.
Tonelli-Shanks [3][6], Cipolla [7] and Daniel Bernstein [8] algorithms. In this section, we
rewrite the Tonelli-Shanks algorithm [3][6] to solve equation (3.2) x2 + c ≡ 0 [p] simulta-
neously for several values of c.

Proposition 19. As in section 2, let us write p− 1 = 2nz with z odd. If m is a quadratic
residue, there exists r ∈ R(n) such that:(

m
p−z
2 r

)2
≡ m

The square roots of m are thus ±m
p−z
2 r and m

p−z
2 r is a quadratic residue if and only if r

also is.
Proof. We still identify F∗

p to (Z/2nZ)×(Z/zZ). m is a quadratic residue and therefore
corresponds to an element in form (2k, l). We know that p−z = 1+(2n − 1) z is even and
p− z ≡ 1 [z] hence p−z

2 × 2 ≡ 1 [z]. On the other hand, modulo 2n, p−z
2 .2k ≡ (p− z) k ≡

(1− z) k. Let r ∈ F∗
p which corresponds to (zk, 0). Then m

p−z
2 r corresponds to

(
k, p−z

2 l
)
,

so its square is so equal to m. Moreover, m
p−z
2 r is a quadratic residue if and only if k is

even, which is equivalent to zk being even, i.e. to r being quadratic residue.

Remark 7. If p ∈ P1,4, we can also write the square root of m as m
p+1−2z

4 r. Indeed, on
one hand p+1

2 and z are both odd with z ≤ p−1
4 < p+1

2 so p+1−2z
4 ∈ N∗, and on the other

hand:
(
m

p+1−2z
4 r

)2
≡ m

p−1
2 mp−zr2 ≡ 1×

(
m

p−z
2 r

)2
≡ m [p].

Corollary 7. If p ∈ P3,4 and m ∈ GQR, then its square roots are ±m
p+1
4 .

Proof. This follows directly from proposition 19, since then r = ±1 and p − z = p+1
2 .

We can also verify directly m
p+1
2 = m

p−1
2

+1 = m by Euler’s criterion, since m ∈ GQR.



M. Wolf, F. Wolf / Eur. J. Pure Appl. Math, 17 (4) (2024), 2431-2447 2446

Searching for the roots of X2 + c modulo p allows us to obtain, if it exists, the smallest
multiple of p in Ec. We describe such an algorithm below.

Algorithm 2. Description: Search for (x1 . . . xn) such that xk is the smallest non-
negative integer verifying x2k + ck ≡ 0 [p] with xk and c of opposite parity (i.e. x2k + ck is
the smallest multiple of p in Eck), for a n-uplet (c1 . . . cn) ∈ (N∗)n and p ∈ P⧹ {2} fixed.
We write p − 1 = 2nz with z odd. By convention, we let xk = ∞ if X2 + ck has no root
modulo p.

(i) If p ∈ P3,4, for each value of ck, we compute c
p−1
2

k modulo p. If c
p−1
2

k ≡ 1 [p], we
set xk = ∞, otherwise we set xk the smallest positive integer with parity opposite to

that of ck and such that xk ≡ ±c
p+1
4

k [p].

(ii) If p ∈ P1,4, we set g = 2 and increase it until g ∈ GQNR (i.e. by Euler criterion

g
p−1
2 ≡ −1) then:

• We enumerate R(n−1)
p =

{
±(gz)2k [p] , 1 ≤ k ≤ 2n−2

}
.

• For each value ck:

(a) If c
p−1
2

k ≡ −1 [p], we set xk = ∞.

(b) Otherwise for each element r of R(n−1)
p , we test if (−c)

p+1−2z
2 r2 ≡ −c [p]

modulo p. If true, we set xk the smallest positive integer with parity opposite

to that of ck and such that xk ≡ ±(−ck)
p+1−2z

4 r.

4. Conclusion

Based on the study of primitive roots (GZ) and semi-primitive roots (GS) modulo
p ∈ P⧹ {2}, and in particular thanks to recursive sequences of elements of GZ and GS , we
proposed an original algorithm returning these two sets in full, which is based on a prime
number generator algorithm rather than on gcd calculations.

We then came back to Shanks’ conjecture, which we generalised to irreducible quadratic
forms, and showed that the conjectured asymptotic density constant could be well con-
trolled. To this end, we rewrote the Tonelli-Shanks algorithm for solving the equation
X2 + c ≡ 0 [p].

Acknowledgements

We would like to thank François-Xavier VILLEMIN for his attentive comments and
suggestions.



REFERENCES 2447

References

[1] Shanks Daniel. On the conjecture of hardy and littlewood concerning the number of
primes of the form n2 + a. Mathematics of Computation, Vol. 14(No. 72):pp. 321–332,
1960. https://doi.org/10.2307/2003891.

[2] Marc Wolf François Wolf. On the density of primes of the form x2+c. Transac-
tions on Machine Learning and Artificial Intelligence, Vol. 11(No. 6):pp. 80–105, 2023.
https://doi.org/10.14738/tecs.116.15890.

[3] Tonelli Alberto. Bemerkung über die auflösung quadratischer congruenzen.
Nachrichten von der Königl. Gesellschaft der Wissenschaften und der Georg-Augusts-
Universität zu Göttingen, Vol. 1891(No. 6):pp. 344–346, 1891. https://gdz.sub.uni-
goettingen.de/id/PPN2524570721891?tify =

[4] Marc WOLF François WOLF. Primality test and primes enumeration using odd num-
bers indexation. Transactions on Machine Learning and Artificial Intelligence, Vol.
8(No. 2):pp. 11–41, 2020. https://doi.org/10.14738/tmlai.82.8054.

[5] Herbert S. Zuckerman Ivan Niven. Improved incremental prime number sieves. Algo-
rithmic Number Theory. ANTS 1994. Lecture Notes in Computer Science, Vol. 270(No.
6):pp. 540, 1994. https://doi.org/10.1016/0016-0032(60)90676-1.

[6] Shanks Daniel. Five number-theoretic algorithms. Proceedings of the Second Manitoba
Conference on Numerical Mathematics, Congressus Numerantium, Vol. 1(No. VII):pp.
51–70, 1973.

[7] Michel Cipolla. Un metodo per la risoluzione della congruenza di secondo grado. Napoli
Rend, Vol. 9:pp. 154–163, 1903.

[8] Daniel J. Bernstein. Faster square roots in annoying finite fields. In ., 2007.
https://api.semanticscholar.org/CorpusID:247863028.