# A Simple Algorithm for Prime Factorization and Primality Testing

Authors: Kabenge Hamiss
Journal: Journal of Mathematics
 (2022)

---

## Abstract

We propose a new simple and faster algorithm to factor numbers based on the nature of the prime numbers contained in such composite numbers. It is well known that every composite number has a unique representation as a product of prime numbers. In this study, we focus mainly on composite numbers that contain a product of prime numbers that are greater than or equal to 5 which are of the form6k+1 or 6k+5. Therefore, we use the condition that every prime or composite P of primes greater than or equal to 5 satisfies P2≡1mod24. This algorithm is very fast especially when the difference in the prime components of a composite number (prime gap) is not so large. When the difference between the factors (prime gap) is not so large, it often requires just a single iteration to obtain the factors.


---

## Body

## 1. Introduction

An integerp is prime if p≥2 and has exactly two positive divisors, namely, 1 and p itself [1–5]. An integer n is called a composite if n≥2 and n have more than two positive divisors [6–9].Any composite number (integer) can be decomposed into smaller integers called prime factors, for which their multiplication produces the original integer. The process of decomposing such numbers is called integer factorization [7, 10–12].Over the years, the prime factorization of large numbers has drawn much attention due to its practical applications and the associated challenges [13, 14]. In computing applications, encryption algorithms such as the Rivest–Shamir–Adleman (RSA) cryptosystems are widely used for information security, where the keys (public and private) of the encryption code are represented using large prime factors [15–21]. Since prime factorization of large numbers is extremely hard, RSA cryptosystems take advantage of this property to ensure information security [10, 22, 23].Many efforts have been made to develop an effective method of factoring numbers and to know whether a number is prime or not [24, 25]. They include Sieve of Eratosthenes, Pollard’s Algorithm, special-purpose factorization algorithm, general-purpose, Special Generic Factorizations, Williams’ P+1 Method, and Lenstra’s Elliptic Curve Method, among others [2, 22, 26–30].


### 1.1. Congruences

We say thata divides b if there is some integer c such that b=ac. If a divides b, we write a∣b, and if a does not divide b we write a∤b.Ifm|a−b, we write(1)a≡bmodm,and say that a is congruent to b modulo m. The quantity m is called the modulus and all numbers congruent (or equivalent) to amodm are said to constitute a congruence (or equivalence) class [7, 31–33]. According to [34], an algorithm is a precise step-by-step series of rules that leads to a product or to the solution to a problem. Some steps in an algorithm depend on what happened or was learned in earlier steps.


## 1.1. Congruences

We say thata divides b if there is some integer c such that b=ac. If a divides b, we write a∣b, and if a does not divide b we write a∤b.Ifm|a−b, we write(1)a≡bmodm,and say that a is congruent to b modulo m. The quantity m is called the modulus and all numbers congruent (or equivalent) to amodm are said to constitute a congruence (or equivalence) class [7, 31–33]. According to [34], an algorithm is a precise step-by-step series of rules that leads to a product or to the solution to a problem. Some steps in an algorithm depend on what happened or was learned in earlier steps.


## 2. The Main Result

Letp and q be prime numbers greater than or equal to 5. Porras Ferreira and Willian De Jesus [35] proved that prime numbers p and q are representatives of 5mod6 or 1mod6 implying(2)p≡5mod6,q≡1mod6.Then, for some integerst and r,(3)p=6t+5,q=6r+1.Now, as it was earlier proven by Porras Ferreira and Willian De Jesus [35] that if m is a composite of primes greater or equal to 5, then m2≡1mod6.Theorem 1.
Letm be a composite containing at least one prime s<5; then,(4)m2≡s2kmod24,where k is a positive integer.Proof.
Letpi (where i = 1, 2, ..., n) be primes greater or equal to 5 and s be a prime less than 5 such that m=skp1k1p2k2…pnkn be a composite of primes.
Sincek and ki are positive integers, then(5)p12k1≡1mod24,p22k2≡1mod24,…,pn2kn≡1mod24.
From the property in [7] of multiplication, then multiplying pi2 in (5) together, we obtain(6)p12k1p22k2…pn2kn≡1mod24.
Multiplyings2k both side in (6), we obtain(7)s2kp12k1p22k2…pn2kn≡s2kmod24.
However,m2=s2kp12k1p22k2…pn2kn implying(8)m2≡s2kmod24.
Thus, the theorem is proven.
This indicates that any composite number that contains at least one prime less than 5 does not satisfy the condition of1mod24.
Therefore, from this point, we can analyze the conditions that will determine any integer to be a prime or a composite.


### 2.1. Composite of the Form6k+1

As stated earlier, not all numbers of the form6k+1 are primes, now, we prove to back up the statement.Case 1.
Letm be a composite of at least two prime say of the form 6t+1 and 6r+1, that is, m=6t+16r+1:(9)m=36tr+6r+t+1,m=66rt+r+t+1.
Let6rt+r+t=k be an integer. Then,(10)m=6k+1.Case 2.
Letm be a composite of at least two primes of the form 6t+5 and 6r+5; that is, m=6t+56r+5:(11)m=36tr+30r+t+25,m=66tr+5r+t+4+1.
Letn=6tr+5r+t+4 an integer. Then,(12)m=6n+1.


### 2.2. Composite of the Form6k+5

Letm be a composite of at least two primes of the form 6t+5 and 6r+1; that is, m=6t+56r+1:(13)m=36tr+6t+30r+5,m=66tr+5r+t+5.Letk=6tr+5r+t an integer. Then,(14)m=6k+5.Equations (10), (12), and (14) really show that not all numbers of the form 6k+1 or 6k+5 are primes. Some of which are pseudoprimes and others just ordinary odd numbers.As we can observe from the above mentioned equations, the values ofr and t will determine whether the number is prime or not a prime.We also observe that it is difficult to distinguish between composites of the form6t+16r+1 and 6t+56r+5 because they both give the same result, that is, 6k+1.


### 2.3. Composites of the Form6k+1 and Their Factorization

Case 3.
P=6t+16r+1.Theorem 2.
Let(15)P=6t+16r+1.
Then, there exists some integerA such that(16)A≡r+tmod6.Proof.
From(17)P=6t+16r+1=66tr+r+t+1.
Then,(18)P−1=66tr+r+t.
Dividing through by 6, we obtain(19)P−16=r+t+6rt.
Now, letA=P−1/6 and u=rt implying that 20 becomes(20)A=r+t+6u.
Hence, we obtain(21)A≡r+tmod6.Lemma 1.
Ifr+t=A, then either r=A,t=0 or r=0,t=A is a solution (trivial solution) to (16).Proof.
Letr+t=A. We know that u=tr=0. Then, it implies that r=A−t:(22)tA−t=0.
Thus,t=0 or t=A.
Whent=0,r=A or when t=A,r=0, therefore, A and 0 is the trivial solution to (16).Corollary 1.
LetP be a number of the form 6k+1 for any integer k≥1; then, for some P is a prime, if and only if A=k and 0 (trivial solution) is the only solution to (16).Proof.
P=6k+1 can be written in the form 6t+16r+1 and clearly; if A and 0 is the only solution, then(23)P=6A+16⋅0+1=6P−16+11=P−1+11,P=P⋅1.
Conversely, letP=6k+1 be a prime. Clearly, P=6k+16⋅0+1; thus, A=k,0 is the solution.Corollary 2.
IfP=6t+16r+1 has at least one more integral solution other than the trivial, then P is a composite.Proof.
Suppose there exists a suitable value ofr+t say r+t=s≠A. Then, u=tr≠0.
Letrt=u; then, ts−t=u:(24)st−t2−u=0,t2−st+u=0.
We use the quadratic formula given by(25)t=s±s2−4u2.
If the integer numbers fort exist say t=s±s2−4u/2 are integers, then(26)m=6s+s2−4u2+16s−s2−4u2+1.
Thus, it is a composite.


### 2.4. Factorizing the Composite of Case3

SupposeP=6t+16r+1 is a composite with at least two prime factors; then, there exists some positive integer A such that A≡t+rmod6 as in (17). Let(27)t+r=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(28)rt=B−f,where B=A−ao/6.From (28) and (29), we obtain(29)t2−ao+6ft+B−f=0.Since we are interested in the positive integer solution, then(30)ao+6f2−4B−f≥0.By expanding, we obtain(31)36f2+12ao+4f−4B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (32). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (30).Substitutingfn=h+n in (30), we obtain(32)tn2−ao+6h+6ntn+B−h−n=0.However, we know thatP has at least one prime factor not exceeding P [36]. Then, 6t+1≤P, or t≤P−1/6. Substituting for t in (33) to determine the maximum value for n=η, we obtain(33)n≤P−12−6ao+6hP−1+36B−h36P≈P36.For maximumη, we choose the negative integer solution of f in (32).Supposeho is the negative value of f; then, we obtain(34)η≤P−12−6ao+6hoP−1+36B−ho36P≈P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η+ω iterations, where ω is the error in n.During the iterations, we may reach a point when we cannot obtain the integer solution fort, and as we reach tη, the values of t tend to converge to some real number say τ, and this requires us to do more iteration so that we can reach at least t=1. So, to reduce the iterations, we decide to simply list down the remaining values of t if tη=τ>1 right from 1 to τ−1 and do the trial divisions, and this is the error we assume to be ω.When we obtain exact integer solutions fort, then it implies that, at least one of the t values gives a prime or a number that divides P.Case 4.
P=6t+56r+5.Theorem 3.
Let(35)P=6t+56r+5.
Then, there exists some integerA such that(36)A≡5r+tmod6.Proof.
From(37)P=6t+56r+5=66tr+5r+t+25,then(38)P−25=66tr+5r+t.
Dividing through by 6, we obtain(39)P−256=5r+t+6rt.
Now, letA=P−25/6 and u=rt imply that (41) becomes(40)A=5r+t+6u.
Hence, we obtain(41)A≡5r+tmod6.Lemma 2.
If5r+t=A and A is divisible by 5, then P is divisible by 5.Proof.
Let5r+t=A. We know that u=tr=0. Then, it implies that r=A/5−t:(42)tA5−t=0.
Thus,t=0 or t=A/5.
Whent=0,r=A/5 or when t=A/5,r=0, since we know that 5 divides A, now, let ζ=A/5; substituting for either t or r in equation (37),(43)P=6ζ+56⋅0+5=6ζ+55.
Thus,P in (37) is divisible by 5, and therefore, P is not a prime.Corollary 3.
IfP=6t+56r+5 has at least a nonzero integer solution, then P is a composite.Proof.
Suppose there exists a suitable value of5r+t say 5r+t=s≠A. Then, u=tr≠0.
Letrt=u. Then, ts/5−t=u:(44)st−5t2−5u=0,5t2−st+5u=0.
We use the quadratic formula given by(45)t=s±s2−100u10,m=6s+s2−100u10+56s−s2−100u10+5.
Thus, a composite provided the values fort and r are integers.
Clearly, if the values oft and r are not integers, then P is a prime.


### 2.5. Factorizing the Composite of Case4

SupposeP=6t+56r+5 is a composite. Then, there exists some positive integer A such that A≡5t+rmod6 as in (38). Let(46)5t+r=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(47)rt=B−f,where B=A−ao/6From (48) and (49), we obtain(48)5t2−ao+6ft+5B−f=0.Since we are interested in the positive integer solution, then(49)ao+6f2−100B−f≥0.By expanding, we obtain(50)36f2+12ao+100f−100B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (52). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (50).Substitutingfn=h+n in (50), we obtain(51)5tn2−ao+6h+6ntn+5B−h−n=0.However, we know that6t+5≤P; then, t≤P−5/6. Substituting for t in (53) to determine the maximum value for n=η, we obtain(52)n≤5P−52−6ao+6hP−5+180B−h36P≈5P36.For maximumη, we choose the negative integer solution of f in (52).Supposeho is the negative value of f; then, we obtain(53)η≤5P−52−6ao+6hoP−5+180B−ho36P≈5P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η+ω iterations. When we obtain exact integer solutions for t, then it implies that at least one of the t values gives a prime or a number that divides P.


## 2.1. Composite of the Form6k+1

As stated earlier, not all numbers of the form6k+1 are primes, now, we prove to back up the statement.Case 1.
Letm be a composite of at least two prime say of the form 6t+1 and 6r+1, that is, m=6t+16r+1:(9)m=36tr+6r+t+1,m=66rt+r+t+1.
Let6rt+r+t=k be an integer. Then,(10)m=6k+1.Case 2.
Letm be a composite of at least two primes of the form 6t+5 and 6r+5; that is, m=6t+56r+5:(11)m=36tr+30r+t+25,m=66tr+5r+t+4+1.
Letn=6tr+5r+t+4 an integer. Then,(12)m=6n+1.


## 2.2. Composite of the Form6k+5

Letm be a composite of at least two primes of the form 6t+5 and 6r+1; that is, m=6t+56r+1:(13)m=36tr+6t+30r+5,m=66tr+5r+t+5.Letk=6tr+5r+t an integer. Then,(14)m=6k+5.Equations (10), (12), and (14) really show that not all numbers of the form 6k+1 or 6k+5 are primes. Some of which are pseudoprimes and others just ordinary odd numbers.As we can observe from the above mentioned equations, the values ofr and t will determine whether the number is prime or not a prime.We also observe that it is difficult to distinguish between composites of the form6t+16r+1 and 6t+56r+5 because they both give the same result, that is, 6k+1.


## 2.3. Composites of the Form6k+1 and Their Factorization

Case 3.
P=6t+16r+1.Theorem 2.
Let(15)P=6t+16r+1.
Then, there exists some integerA such that(16)A≡r+tmod6.Proof.
From(17)P=6t+16r+1=66tr+r+t+1.
Then,(18)P−1=66tr+r+t.
Dividing through by 6, we obtain(19)P−16=r+t+6rt.
Now, letA=P−1/6 and u=rt implying that 20 becomes(20)A=r+t+6u.
Hence, we obtain(21)A≡r+tmod6.Lemma 1.
Ifr+t=A, then either r=A,t=0 or r=0,t=A is a solution (trivial solution) to (16).Proof.
Letr+t=A. We know that u=tr=0. Then, it implies that r=A−t:(22)tA−t=0.
Thus,t=0 or t=A.
Whent=0,r=A or when t=A,r=0, therefore, A and 0 is the trivial solution to (16).Corollary 1.
LetP be a number of the form 6k+1 for any integer k≥1; then, for some P is a prime, if and only if A=k and 0 (trivial solution) is the only solution to (16).Proof.
P=6k+1 can be written in the form 6t+16r+1 and clearly; if A and 0 is the only solution, then(23)P=6A+16⋅0+1=6P−16+11=P−1+11,P=P⋅1.
Conversely, letP=6k+1 be a prime. Clearly, P=6k+16⋅0+1; thus, A=k,0 is the solution.Corollary 2.
IfP=6t+16r+1 has at least one more integral solution other than the trivial, then P is a composite.Proof.
Suppose there exists a suitable value ofr+t say r+t=s≠A. Then, u=tr≠0.
Letrt=u; then, ts−t=u:(24)st−t2−u=0,t2−st+u=0.
We use the quadratic formula given by(25)t=s±s2−4u2.
If the integer numbers fort exist say t=s±s2−4u/2 are integers, then(26)m=6s+s2−4u2+16s−s2−4u2+1.
Thus, it is a composite.


## 2.4. Factorizing the Composite of Case3

SupposeP=6t+16r+1 is a composite with at least two prime factors; then, there exists some positive integer A such that A≡t+rmod6 as in (17). Let(27)t+r=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(28)rt=B−f,where B=A−ao/6.From (28) and (29), we obtain(29)t2−ao+6ft+B−f=0.Since we are interested in the positive integer solution, then(30)ao+6f2−4B−f≥0.By expanding, we obtain(31)36f2+12ao+4f−4B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (32). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (30).Substitutingfn=h+n in (30), we obtain(32)tn2−ao+6h+6ntn+B−h−n=0.However, we know thatP has at least one prime factor not exceeding P [36]. Then, 6t+1≤P, or t≤P−1/6. Substituting for t in (33) to determine the maximum value for n=η, we obtain(33)n≤P−12−6ao+6hP−1+36B−h36P≈P36.For maximumη, we choose the negative integer solution of f in (32).Supposeho is the negative value of f; then, we obtain(34)η≤P−12−6ao+6hoP−1+36B−ho36P≈P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η+ω iterations, where ω is the error in n.During the iterations, we may reach a point when we cannot obtain the integer solution fort, and as we reach tη, the values of t tend to converge to some real number say τ, and this requires us to do more iteration so that we can reach at least t=1. So, to reduce the iterations, we decide to simply list down the remaining values of t if tη=τ>1 right from 1 to τ−1 and do the trial divisions, and this is the error we assume to be ω.When we obtain exact integer solutions fort, then it implies that, at least one of the t values gives a prime or a number that divides P.Case 4.
P=6t+56r+5.Theorem 3.
Let(35)P=6t+56r+5.
Then, there exists some integerA such that(36)A≡5r+tmod6.Proof.
From(37)P=6t+56r+5=66tr+5r+t+25,then(38)P−25=66tr+5r+t.
Dividing through by 6, we obtain(39)P−256=5r+t+6rt.
Now, letA=P−25/6 and u=rt imply that (41) becomes(40)A=5r+t+6u.
Hence, we obtain(41)A≡5r+tmod6.Lemma 2.
If5r+t=A and A is divisible by 5, then P is divisible by 5.Proof.
Let5r+t=A. We know that u=tr=0. Then, it implies that r=A/5−t:(42)tA5−t=0.
Thus,t=0 or t=A/5.
Whent=0,r=A/5 or when t=A/5,r=0, since we know that 5 divides A, now, let ζ=A/5; substituting for either t or r in equation (37),(43)P=6ζ+56⋅0+5=6ζ+55.
Thus,P in (37) is divisible by 5, and therefore, P is not a prime.Corollary 3.
IfP=6t+56r+5 has at least a nonzero integer solution, then P is a composite.Proof.
Suppose there exists a suitable value of5r+t say 5r+t=s≠A. Then, u=tr≠0.
Letrt=u. Then, ts/5−t=u:(44)st−5t2−5u=0,5t2−st+5u=0.
We use the quadratic formula given by(45)t=s±s2−100u10,m=6s+s2−100u10+56s−s2−100u10+5.
Thus, a composite provided the values fort and r are integers.
Clearly, if the values oft and r are not integers, then P is a prime.


## 2.5. Factorizing the Composite of Case4

SupposeP=6t+56r+5 is a composite. Then, there exists some positive integer A such that A≡5t+rmod6 as in (38). Let(46)5t+r=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(47)rt=B−f,where B=A−ao/6From (48) and (49), we obtain(48)5t2−ao+6ft+5B−f=0.Since we are interested in the positive integer solution, then(49)ao+6f2−100B−f≥0.By expanding, we obtain(50)36f2+12ao+100f−100B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (52). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (50).Substitutingfn=h+n in (50), we obtain(51)5tn2−ao+6h+6ntn+5B−h−n=0.However, we know that6t+5≤P; then, t≤P−5/6. Substituting for t in (53) to determine the maximum value for n=η, we obtain(52)n≤5P−52−6ao+6hP−5+180B−h36P≈5P36.For maximumη, we choose the negative integer solution of f in (52).Supposeho is the negative value of f; then, we obtain(53)η≤5P−52−6ao+6hoP−5+180B−ho36P≈5P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η+ω iterations. When we obtain exact integer solutions for t, then it implies that at least one of the t values gives a prime or a number that divides P.


## 3. Composites of the Form6k+5 and Their Factorization

Theorem 4.
LetP=6t+56r+1; then, there exist some integer A such that(54)A≡5r+tmod6.Proof.
From(55)P=6t+56r+1=66tr+5r+t+5,then(56)P−5=65r+t+6tr.
Dividing through by 6, we obtain(57)P−56=5r+t+6tr.
LetA=P−5/6 and k=tr; then,(58)A=5r+t+6k,implying(59)A≡5r+tmod6.Lemma 3.
If5r+t=A, then either r=A/5,t=0 or r=0,t=A is a trivial solution to (56).Proof.
Let(60)5r+t=A.
Then,(61)rt=0,implying that(62)r=A−t5⇒tA−t5=0.
Thus,t=0 or t=A, when t=0,r=A/5 and when t=A,r=0.Corollary 4.
When the trivial solution in Lemma3 is the only solution to (56), then P is either prime or divisible by 5.Proof.
From (56), we need to show that P is either divisible by 5 or has exactly two divisors that is 1 and P itself:(63)P=6r+16t+5.
Whent=0,r=A/5, then(64)P=6A5+16⋅0+5=6P−530+15.
Then,P is divisible by 5, provided 5 divides A.
Or whent=A,r=0, then(65)P=6⋅0+16A+5=1⋅6P−56+5,P=1⋅P.
Implying if (56) has only a trivial solution, then 1 and P are the only divisors of P.Corollary 5.
If there exists one more solution (nontrivial solution) of (56), then P is a multiple of primes greater than or equal to 5.Proof.
Lets≠A and u≠0 be the suitable integers such that 5r+t=s and tr=u; then,(66)r=s−t5,⇒s−t5t−u=0,t2−st+5u=0.
Applying quadratic formula, we obtain(67)t=s±s2−20u2.
The solution is eithers+s2−20u/2 or s−s2−20u/2.
Substituting the solution in (56), we obtain(68)P=6s+s2−20u2+56s−s2−20u10+1or(69)P=6s−s2−20u2+56s+s2−20u10+1.
Thus,P is a composite provided s+s2−20u/2 and s−s2−20u/2 are integers.


### 3.1. Factorizing the CompositeP=6t+56r+1

SupposeP=6t+56r+1 is a composite. Then, there exists some positive integer A such that A≡5r+tmod6 as in (56).Let(70)5r+t=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(71)rt=B−f,where B=A−ao/6.From (72) and (73), we obtain(72)t2−ao+6ft+5B−f=0.Since we are interested in the positive integer solution, then(73)ao+6f2−20B−f≥0.By expanding, we obtain(74)36f2+12ao+20f−20B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (76). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (75). Substituting fn=h+n in (75), we obtain(75)tn2−ao+6h+6ntn+5B−h−n=0.However, we know from [7] that 6t+5≤P; then, t≤P−5/6. Substituting for t in (77) to determine the maximum value for n=η, we obtain(76)n≤P−52−6ao+6hP−5+180B−h36P≈P36.For maximumη, we choose the negative integer solution of f in (76).Supposeho is the negative value of f; then, we obtain(77)η≤P−52−6ao+6hoP−5+180B−ho36P≈P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η iterations. When we obtain exact integer solutions for t, then it implies that at least one of the t values gives a prime or a number that divides P.


## 3.1. Factorizing the CompositeP=6t+56r+1

SupposeP=6t+56r+1 is a composite. Then, there exists some positive integer A such that A≡5r+tmod6 as in (56).Let(70)5r+t=ao+6f,such that A−ao is divisible by 6, where f=0,1,2,…,n and ao is the smallest positive residue. Then,(71)rt=B−f,where B=A−ao/6.From (72) and (73), we obtain(72)t2−ao+6ft+5B−f=0.Since we are interested in the positive integer solution, then(73)ao+6f2−20B−f≥0.By expanding, we obtain(74)36f2+12ao+20f−20B+ao2≥0.Then, leth be the least positive integer solution for f satisfying (76). Then, fn=h+n, where n=0,1,…,η. This implies that fmin=h for the real solution in (75). Substituting fn=h+n in (75), we obtain(75)tn2−ao+6h+6ntn+5B−h−n=0.However, we know from [7] that 6t+5≤P; then, t≤P−5/6. Substituting for t in (77) to determine the maximum value for n=η, we obtain(76)n≤P−52−6ao+6hP−5+180B−h36P≈P36.For maximumη, we choose the negative integer solution of f in (76).Supposeho is the negative value of f; then, we obtain(77)η≤P−52−6ao+6hoP−5+180B−ho36P≈P36.Then, we can now obtain the exact integer solution fort recursively in simply ≤η iterations. When we obtain exact integer solutions for t, then it implies that at least one of the t values gives a prime or a number that divides P.


## 4. General Outline of the Algorithm

We outline the steps of factorizing primes based on the proofs above.Given an integerP(1)
Check ifP satisfies P2≡1mod24.(2)
Does (1) hold? If so, do step (4), and if not, do step (3).(3)
Check if it is either divisible by 2 or by 3 and reduced it by dividing by 2 or 3 until the Quotient is no longer divisible by 2 or 3. If the resulting Quotient is greater than 3, we can call itP and do step (4).(4)
Check ifP is either of the form 6k+1 or 6k+5 by subtracting 1 or 5 from P and check if the difference is divisible by 6.(5)
IfP is of the form 6k+1, thenEither Case 3(i)
We determine integerA from A=P−1/6.(ii)
We write down the congruence:(78)A≡r+tmod6.(iii)
We determineB and ao, where ao is the least positive residue such that B=A−ao/6 is a positive integer(iv)
We obtain the least positive integerfmin=h such thatt2−ao+6ft+B−f=0 has a real solution.This is obtained fromao+6f2−4B−f≥0.(v)
We obtain the integern from n=η≤P/36, where ho=−h.(vi)
n=0,1,2,…,η, fo=h, fn=h+n, and to=ao+6h±ao+6h2−4B−h/2.If the integer solution does not exist atn=0, we do step (vii)(vii)
We perform at mostη iterations to obtain the integer solutions for t from(79)tn=ao+6h+6n±ao+6h+6n2−4B−h−n2.Remark: If the values oft seem to converge at some point on a real line, then it is better to list the integer values of t from the point of convergence (integer value of convergence) to as small as 1; that is, if the integer value of convergence of t is τ, then we list them such that t=τ−1,…,1 and do the trial divisions from P/6t+1.If there is no integer value oft such that P/6t+1 is an integer, then we try Case 4.OR Case 4(i)
We determine integerA from A=P−25/6.(ii)
We write down the congruence:(80)A≡5r+tmod6.(iii)
We determineB and ao, where ao is the least positive residue such that B=A−ao/6 is a positive integer.(iv)
We obtain the least positive integerfmin=h such that5t2−ao+6ft+5B−f=0 has a real solution.This is obtained fromao+6f2−100B−f≥0.(v)
We obtain the integern from n=η≤5P/36, where ho=−h.(vi)
n=0,1,2,…,η, fo=h, fn=h+n, and to=ao+6h±ao+6h2−100B−h/10.If the integer solution does not exist atn=0, we do step (vii).(vii)
We perform at mostη iterations to obtain the integer solutions for t from(81)tn=ao+6h+6n±ao+6h+6n2−100B−h−n10.Remark: If the values oft seem to converge at some point on a real line, then it is better to list the integer values of t from the point of convergence (integer value of convergence) to as small as 1; that is, if the integer value of convergence of t is τ, then we list them such that t=τ−1,…,1 and do the trial divisions from P/6t+5.If there is no integer value oft such that P/6t+5 is an integer, then P is a prime.(6)
IfP is of the form 6k+5, then(i)
We determine integerA from A=P−5/6.(ii)
We write down the congruence:(82)A≡5r+tmod6.(iii)
We determineB and ao, where ao is the least positive residue such that B=A−ao/6 is a positive integer.(iv)
We obtain the least positive integerfmin=h such thatt2−ao+6ft+5B−f=0 has a real solution.This is obtained fromao+6f2−4B−f≥0.(v)
We obtain the integern from n=η≤P/36, where ho=−h.(vi)
n=0,1,2,…,η, fo=h, fn=h+n, and to=ao+6h±ao+6h2−20B−h/2.If the integer solution does not exist atn=0, we do step (vii).(vii)
We perform at mostη iterations to obtain the integer solutions for t from(83)tn=ao+6h+6n±ao+6h+6n2−20B−h−n2.Remark: if the values oft seem to converge at some point on a real line, then it is better to list the integer values of t from the point of convergence (integer value of convergence) to as small as 1; that is, if the integer value of convergence of t is τ, then we list them such that t=τ−1,…,1 and do the trial divisions from P/6t+5.If there is no integer value oft such that P/6t+5 is an integer, then P is a prime.Example 1.
We consider the factorizing of number 1099551473989:(84)A=183258578994,183258578994≡5t+rmod6,B=30543096499,ao=0,5t2−6ft+530543096499−f=0.
For real solution fort, we obtain 36f2+100f−3054309649900≥0:(85)fmin=h=291275,⇒ho=−291275.
Usingnmax=η≤5P−52−6ao+6hoP−5+180B−ho/36P, then n=0,1,2,…,582550.
Fromto=ao+6ho±ao+6ho2−100B−ho/10, we obtain(86)to=6×291275±10010.
Then,to=174766 or to=174764, and therefore, the prime divisors of 1099551473989 are 1048601 and 1048589.
The above procedures (general outline) can be summarized by the flowcharts in Figures1–3, respectively.Figure 1
Algorithm for numbers of the form 6k + 1: Case 3.Figure 2
Algorithm for numbers of the form 6k + 1: Case 4.Figure 3
Algorithm for numbers of the form 6k + 5.


### 4.1. Algorithm for Numbers of the Form6k+1: Case 3

P, A=P−1/6, B=A−ao/6, ao+6fo2−4B−fo≥0, ho=−fo, η≤P/36


### 4.2. Algorithm for Numbers of the Form6k+1: Case 4

P, A=P−25/6, B=A−ao/6ao+6fo2−100B−fo≥0, ho=−fo,η≤5P/36


### 4.3. Algorithm for Numbers of the Form6k+5: Case 4

P, A=P−5/6, B=A−ao/6ao+6fo2−20B−fo≥0, ho=−fo,η≤P/36


## 4.1. Algorithm for Numbers of the Form6k+1: Case 3

P, A=P−1/6, B=A−ao/6, ao+6fo2−4B−fo≥0, ho=−fo, η≤P/36


## 4.2. Algorithm for Numbers of the Form6k+1: Case 4

P, A=P−25/6, B=A−ao/6ao+6fo2−100B−fo≥0, ho=−fo,η≤5P/36


## 4.3. Algorithm for Numbers of the Form6k+5: Case 4

P, A=P−5/6, B=A−ao/6ao+6fo2−20B−fo≥0, ho=−fo,η≤P/36


## 5. Conclusion and Recommendations

This method is good especially when the difference (prime gap) between the prime divisors if relatively small.Remark 1.
Normally, when the prime divisors are close to each other, values ofto are integer solutions. However, this may not guarantee for all such problems.
The algorithm is effective in prime factorization and primality testing, especially when dealing with relatively large numbers. However, there is need for a way of differentiating numbers of the form 6t+16r+1 from numbers of the form 6t+56r+5 because the end result is of the form 6k+1 which makes it difficult to choose which algorithm is suitable for such numbers. This forces one to randomly select either Case 3 formula or Case 4 which makes it more tiresome in case the first algorithm does not produce any result so you turn to another case before making any conclusion about the given problem.
In addition, this algorithm requires a computer program so that it carries a greater impact in the field of cryptography and mathematics.



---

*Source: 7034529-2022-12-15.xml*