Original Article

Essentials of Number Theory for Cryptography

 

 

INTRODUCTION

Natural numbers and in general the entire set of integers, has been a subject of study for millennia, unveiling a host of algebraic properties possessing bewilderingly elegant structures. The quest for finding these properties shrouded in right earnest began with the notings of Pierre de Fermat (CE 1601-1665), Euler (CE 1707-1783), Gauss (CE 1777-1855), and numerous other famous mathematicians, continuing to the present era. The subject however remained a special topic in text books of Higher Algebra, such as those by Chrystal (1906) and Bernard and Child (1965) in English language, but the topic gained limelight with the appearance of the tome by Hardy and Wright (1938)followed by a number of other books. Until the mid-nineteen seventies, the subject remained a fancied subject of puree. mathematicians devoid of any practical application.

 The invention of the digital computer heralded first as a number crunching machine and then as a coded text editor post 1975 followed by their communication from one computer to another over long distances in a secure manner avoiding any corruption, led to discovering the means of encryption. The subject of Cryptography thus came in to being at that juncture, and as a tool of encryption of stored and transmitted data, the vast knowledge of Number Theory at last found a very effective application; the essential reason for this development being discreteness of digital data.

  At present the development of the cryptographic methods are treated in several books. Their presentations can be broadly categorised in to two types. Firstly, excellent introductory texts on Cryptography are those by Paar and Pelzl (2010), McAndrew (2011), Hoffstein et al. (2008). and by Buchmann (2002). These books begin with introductory Number Theory, freely employing its special tools, in order to develop various cryptographic methods, many of which employed in practice. Yet the reading such texts is exhausting because of the special features of the Number Theoretic Algebra. The second category of books are on Number Theory, succinctly presenting some Cryptographic methods. Notable among these texts are those by Rosen (2005) and by Niven et al. (1991). The array of the elegant Number Theoretic results are then applied to special Cryptographic methods. As an aid for easily following the literature on Cryptography, the present survey presents the essentials of Number Theory that may be useful as as a ready reference, The details of this presentation is kept as simple as possible as the goal is to understand the cryptographic methods.

The Theory of Numbers exclusively deals with whole numbers or integers consisting of the natural numbers  the number , and the negative integers . These numbers form the integer set

 

 

The theory develops the special properties of these numbers, in particular those of the natural numbers. Algebraically the elements of the set  will be denoted by the symbols such as  etc. The methods and properties of addition, subtraction and multiplication are employed in the usual manner, but that ofdivision is of special attenti0n in the theory. The properties of the prime numbers defined in section 3, dealt comprehensibly in Number Theory, plays a central role in Cryptography. Their properties are presented here keeping in view the Cryptographic applications. The properties of difficulty of factorising large numbers, or taking their discrete logarithms, or selecting them from elliptic curves defined in section 11, are presented in a succint manner. These properties are central to the Cryptographic methods, and presented here in clear terms, using only elementary algebra.

 

DIVISIBILITY

Definition: Let  and  be integers. Then  is said to be divisible by  if , where  is an integer. In brief this definition is written as  (meaning  divides ).

 Examples.  since . (ii)  since , (iii)  since

Theorem 2.1

 If  then .

(ii) If  and  then

(iii) If  and  then  for integers  and .

Proof.  and  are self evident. For  Let  and  where  and  are integers. Therefore , that is .

Theorem 2.2 (Division Algorithm). Given two integers  such that ; then there exists unique inegers such that

 

                                                                               (2.1)

 

Moreover if  does not divide  then .

Proof. Consider the sequence in Arithmetic Progression

 

 

Any integer  (positive, negative, or zero) is an element of the sequence or it lies between two conseqcutive elements. Thus, two numbers q and r can be determined uniquely so that , where . If  does not divide , then .

Examples.  Let  then  (ii) Let  then  

 

Greatest Common Divisor

Let  and . then  is a common divisor of  and . Since there is only a finite number of divisors of any nonzero integer, there can only be a finite number of common divisors of  and . The greatest among the divisors is called the Greatest Common Divisors denoted as .  is also known as Greatest Common Measure (GCM), or as Highest Common Factor (HCF). Evidently, .

Lemma. Let  be integers then

 

                                                                 (2.2)

 

Proof. Actually all of the common divisors of  and  are exactly the same as those of  and . For, let  be a common divisor of  and , then  and e | b. Now by Theorem 2.1  it means that  or , that is  is a common divisor of  as well as that of . Hence for the greatest divisor

Theorem 2.3 (Euclidean Algorithm). Given integers  and , then by repeated application of the Division Algorithm,

 

                                                               (2.3)

    

in which  Since the number of remainders  is limted, a stage  will come when  and    

Proof. From the result of the Lemma given above

 

 

 The theorem was also stated independently by Aryabhat in verse form as was the custom in Sanskrit literature. This algorithm is particularly useful for calculating the gcd of large integers.

Example. Find  

By division using a calculator

 

 

Hence .

The following theorem is also useful.

Theorem 2.4 (Extended Euclidean Theorem). If the numbers  and  are not both zero and  the there exist integers  such that

 

                                                                                (2.4)

 

Proof. Consider the linear combination , then it is negative, zero (when ) or positive. Let d be the least positive value of  for  and ; then . Let , then it follows that  and . For, by division algorithm

 

or                                         

 

which is a linear combination of  and . Since  and  is the least positive combination of  and , it follows that , and so . In a similar manner .

 In order to show that , consider a number e such that  and . Hence according to Theorem 2.1  that is , so that . Hence .

 

 

PRIME NUMBERS

 Prime numbers are also known as Primes.

Definition: A positive integer which has no divisors except itself and  is called a Prime Number. Numbers which are not prime are called Composite Numbers.

 Thus, for example,  and  are prime numbers where as  and are composite numbers.

Definition: Two integers  and  are called prime to each other or coprime if  

Theorem 3.1 A prime number  is prime to every number which is not a multiple of .

Proof. Let  be a number which is not a multiple of . Hence if  is divided by , then according to the division algorithm , where . Now  and  are the only divisors of , and as , the only common divisors of  and  is  that is,  or by Lemma of section 2.1, , that is,  and  are prime to each other.

Theorem 3.2 Every composite number  has at least one prime divisor.

Proof. Since  is a composite number and not a prime, it has a divisor  which is not greater than any other divisor. Then  must be a prime; for otherwise it would have a divisor less than itself and greater than . The latter divisor would be a divisor of . This contradicts the hypothesis that n is not greater than any other divisor.

Theorem 3.3 Every composite integer  greater than  can be expressed as a product of primes.

Proof. Since  has at least one prime factor , , where . If  is not a prime, it has at least one prime factor  such that , where . Thus , and so on. But the numbers less than  are limited and  · Therefore the set  must finally end in a prime. Hence  can be expressed as , where  are all primes not necessarily all different.

 Thus, in general, a composite number  can be written as

 

                                                                            (3.1)

 

Theorem 3.4 (Fundamental Theorem of Arithmetic) The factorisation of a composite number  is unique.

Proof. Let  have two different factorings:

 

 

where  are primes not necessarily distinct, but no prime on the left-hand side occurs on the right side. This means that , that is,  is a divisor of at least one of the , which means that  equals at least one of the , contradicting the hypothesis.

Theorem 3.5 There are infinitely many primes.

Proof. Let  be the largest prime. Then the number  is greater than  and is not divisible by  or any smaller value of . If  is not a prime, it must have a prime factor greater than . Hence, in either case, a prime number greater than  exists.

Theorem 3.6 If  is a composite integer, then  has a prime factor less than or equal to .

Proof. Let , where  is a prime and , then , so that .

Example 1. Find all the primes less than .

Here  and . Now the only primes less than or equal to  are  and . Hence, rejecting all the whole numbers up  that are divisible by  and  yield the prime numbers

 and .

Example 2. Find all the primes less than  

Here  and . The primes less than  are  and  Hence checking allthe integers up to  for divisibility by  and rejecting the divisible ones yield the primes

 

 

Examples 1 and 2 illustrate the Seive of Eratosthenes for generating prime numbers.

 The prime numbers appear to be distributed randomly. Estimation of their distribution was a major problem which was finally resolved by Chebyshev as stated below.

Theorem 3.7 (Prime Number Theorem). Let  denote the number of primes less than or equal to a real number , then

 

                                                                                                                                                                         (3.2)

 

or,                                                                  as

 

The proof of this theorem is very technical and outside the scope of this article.

 

CONGRUENCE

Definition: Let  be any positive integer, called modulus. If  and  are any two integers positive or negative such that , then  and  are said to be congruent with respect to modulus , and each of  and  is said to be the residue of the other. This is expressed by writing

 

                                                                     (4.1)

 

where  stands for “congruent with”.

Theorem 4.1  if and only if there is an integer  such that  

Proof. If  and therefore there exists an integer , such that  or . Conversely if  then,  and so  

 Thus, letting  to have the values  one gets the arithmetic progression

 

 

 called the residue class modulo , or alternatively the congruence class modulo .

Example 1. Let  (as with a clock), then and . For, , and . Hence  and  from which the two results follow.

Example 2. Let  (as with the  letters A, B, C, D, · · · · · · , X, Y, Z), then , and .

Theorem 4.2 If  is the remainder when  is divided by , then

 

 and                                                                        (4.2)

 

Proof. By the division algorithm Eq. (2.2) if  is the quotient when  is divided by  where . Hence,  so that  with . The expression in (3.2) is then an alternative way of expressing the division algorithm. Evidently,  is a member of the set  to which a is congruent. In this sense this set of elements is called the complete set of residues modulo .

Theorem 4.3 Let  and , then

 

 

 

(iv) If  and  are divisible by  which is prime to , then  

Proof. By hypothesis  and . Thus,

 

 or,

 

which proves  and . For  

 

 

in which  and  and so . For  so that  where  is an integer. By hypothesis, , that is . But  and  are prime to each other, hence , which means that  is an integer. Now,  and therefore .

Remark. In particular, if  where  is a prime and  is any common divisor of  and , then  except when . Thus, there is a close analogy between congruence to a prime modulus and equalities.

 To summarise, in dealing with integers modulo , we are essentially performing the operations of arithmetic, but are disregarding multiples of .

Theorem 4.4 If  is a prime number and  are any integers, then

 

                                                                                  (4.3)

 

Proof. By the binomial theorem

 

 

 

or,                                                   

 

The binomial coefficient on the right-hand side isa multiple of  which can not be divided by . This means that the product  is divisible by  as the binomial coefficients are all integers. Hence the congruence (4.3) from the above equation.

Remark. The above theorem can be easily generalised to any number of terms  as

 

                                                 (4.4)

 

by successively increasing the number of terms to  

 From the above theorem follows one of the most basic theorem of number theory’

Theorem 4.5 (Fermat’s Little Theorem) If  is prime and  is an integer prime to , then    

  

                                                                             (4.5)

 

Proof. Partitioning  in to , let  (  terms), then by Eq. (4.4)

 

 

where there are  terms in the sums on both sides of the cogruence. Hence,

 

                                                                                (4.6)

 

Dividing by  and applying Theorem 4.3  we obtain (4.5).

Remark. The theorem can also be stated as the congruence (4.6).

Theorem 4.6 If  is prime and  is prime to , then

 

 

Proof.  is divisible by  according to congruance (4.5). Therefore  or, . Hence,

 

   or

 

that is, , which establishes the theorem.

 

EULER’S PHI FUNCTION

Euler generalised Fermat’s little theorem for any integer , which may be a composite number

Definition. Let  be a positive integer. Euler’s phi function  is defined as the number of integers less than  that are prime to , with the stipulation that  is regarded as prime which is prime to every number such that . Thus,

 etc.

 

Theorem 5.1 If  is prime to , the number of terms of the arithmetic progression

 

 

 that are prime to  is  

Proof. Let these numbers be divided by , then the remainders are  (Theorem 4.2), taken in a certain order. Now, if a number is prime to , so also its remainder. Consequently, as many terms in the progression are prime to  as there are numbers less than  and prime to it, that is  

Theorem 5.2 If  is prime to , then

 

 (multiplication property)                                                      (5.1)

 

Proof. Let the numbers  be arranged in an array of  columns and  rows as follows:

 

 

Since  is prime to , the numbers prime to  are prime to both  and . Consider the   column. If for this column  is prime to , then the elements of the column headed by  are prime to  and hence are members of . It follows that in the contrary case of  not prime to , that column must be ignored. Now the elements of a desired column are  in which  is prime to , These elements being in arithmetic progression, the number of terms prime to  is . Hence the total count of elements prime to  is , that is .

Remark. The theorem can evidently be extended to any number of terms .

 

Theorem 5.3 (Euler’s Theorem) If  is any number prime to , then

 

                               (5.2)

 

Proof. Let  be the numbers in ascending order less than n and prime to it. Consider the products

 

 

If these products are divided by , the remainders are all different. For, if  and  give the same remainder, then  would be divisible by . This is impossible since  is prime to  and . Also, the remainders are all prime to , for the factors  and  are all prime to . Hence, by the product theorem 4.3  

 

 

Dividing by  which is prime to , .

Remark. Let  be a prime and  be a number prime to , then the arithmetic progression  are all prime to . For this arithmetic progression  and so , which is Fermat’s theorem.

Theorem 5.4 If  is prime, then

 

                                                         (5.3)

 

Proof. When , the numbers  are all prime to . Hence . When , since  is prime; of the numbers  those which are not prime to  are  which are  in number. all the rest are prime to  and their number is .

Theorem 5.5 If any number  are the prime factors of , then

 

 

Proof.  are prime to one another and so the theorem follows from Theorem 5.4 and the Remark after 5.2.

Theorem 5.6 (Wilson’s Theorem) If  is a prime number, then

 

                                                     (5.5)

 

Proof. Let  be any one of the numbers . If the products  are divided by , the remainders are  (by theorem 4,2) in a certain order. Hence for every  there is a unique number  such that  is divided by  leaves the remainder , that is, . If now , then  must be divisible by , which means that  or  is divisible by the prime . Since , it follows that either  or . If then,  it can not be equal to . Now, these  even numbers can be arranged in  pairs, such that the product of each is congruent to . Hence,

or                                                                         

 

which proves the result (5.5).

Remark. The theorem is true only when  is prime. For otherwise assume that  has a factor , which must be less than  and therefore must divide . Hence  is not a multiple of  and therefore not a multiple of .

 

FAST EXPONENTIATION

In Cryptography the raising of power of a number (or exponentiation) as in Fermat’s and Euler’s theorem for large values of the power is common place. In such cases straight forward calculation even with the aid of a computer becomes prohibitive. To overcome this difficulty, a Fast Exponentiation algorithm has been developed, which is described below.

 Suppose one has to calculate  where  is large. Expressing the exponent  in binary digits to the base , one can express  as a polynomial in this base number as

 

                            (6.1)

 

where  with . As for example, let , then one can write

Thus,  can be written as

 

 

Now the sequence  can be easily computed  by recursion. Let

which yields

 

                                (6.2)

 

in which the product on the right-hand side of (6.2) can be computed by at most  multiplications, as any exponent  will contribute only  as a factor.

 

LINEAR CONGRUENCE

Definition: A congruence of the form

 

                                                                                     (7.1)

where  is an unknown integer is called a linear congruence in one variable.

 In a linear congruence, it is to be noted that if  is a solution of (7.1), and if , then  so that  is also a solution of (7.1). Hence if one member of a congruence class modulo  is a solution, then all members of this class are also solutions. Hence, one may seek incongruent solutions modulo  of (7.1).

Theorem 7.1 If  and  be relatively prime integers with  and  an integer, then the linear congruence  has a unique solution .

Proof. With modulo  the integers are the terms of the arithmetic progression . If divided by , since  is prime to , the remainders are  in a certain order, and by the division algorithm (theorem 4.2) , the latter set is also the set when  is divided by . Hence, there exists just one such that  where .

Theorem 7.2 Let  be not prime to , such that , and  an integer. If  does not divide , then  has no solution. If  divides  then the equation has exactly  incongruent solutions modulo .

Proof. Let  and  so that  is prime to . We require that  is divisible by . Hence, if  does not divide , there is no solution. Next suppose that  divides , that is , then  is divisible by if . Since  is prime to , the last congruence has exactly one solution  and  incongruent solutions  which are distinct roots of

Theorem 7.3 (Simultaneous Congruences: Chinese Remainder Theorem) Let  be prime to , then the solution of the simultaneous congruences

 

                                                        (7.2)

 

is given by the solution of , where .

Proof. From the first congruence relation of (7.2), one gets . Substituting in the second congruence relation, one has  Since  and  are relatively prime, this congruence has a unique solution  modulo , so that . Thus, the general solution is

 

 

where , and . Hence the theorem.

Remark. The theorem can be generalised to three, four. · · · · · · congruences in steps and in general to  congruences as follows. Let,

 

                      (7.3)

 

where  are mutually prime to each other, the solution of (7.3) is the same as that of  where .

 

PRIMALITY TESTING

In Cryptography testing a given number , often very large, is of paramount importance. We proceed to study some of the testing methods with their merits and demerits.

 

Trial Division

According to theorem 3.6, if  is a composite number, then it has a prime divisor . If no such prime divisors are found then  is a prime number.

Example. Test  and  for primality.

In the first case using a calculator  and in the second case  which means that the integral part . Now the prime numbers less than or equal to  are  and . From this set  and therefore  is a composite number. But none from the set divides  and so  is a prime number.

Remark. In the RSA cryptosystems employed in practice, primes greater than  are required, that entails following the prime number theorem at least  divisions for the test, which is an impossible task.

 

Fermat Test

According to Fermat’s little theorem (Theorem 4.5), if for an integer  prime to  can be found, such that

 

 

                                       (8.1)

 

then  is likely a prime number. The statement “likely” is emphasised because the converse of the theorem is not always true.

The smallest number which shows the inadequacy of the Fermat test is  For

 

 

 Worst is the case of , with arbitrary  prime to , showing that . This is proved in three steps.

First Step; Modulo 3: If  is prime to , then by Fermat’s littele theorem

 

 and so

 

Second Step; Modulo 11: If  is prime to , then similarly

 

 

Third Step; Modulo 17: If  is prime to , then

 

 

Hence by the Chinese remainder theorem 7.3 for all  satisfying  

 

 

 Numbers such as  are called Carmichael Numbers. Such special numbers are rare. For instance, there are only  Carmichael numbers less than .

Theorem 8.1 If  is a product of distinct primes, such that  for all , then  is a Carmichael number.

Proof. Let  be an integer prime to  and  a prime divisor of . Then, . Therefore,  as  is a multiple of . Hence by the Chinese remainder theorem,

 

Miller-Rabin Test

Here Fermat’s theorem is so modified as to exclude the possibility of Carmichael numbers.

Theorem 8.2 Let  be prime such that  where  is odd. Let  be any number prime to , then either  , or

 

 One of

 

Proof. By Fermat’s theorem, , in which . Consider therefore the sequence

 

                                                                     

 

which form elements of a sequence of the previous powers. Hence

 For the first element , or

 Some number in the list is not congruent to 1 modulo p. But when it is squared, it becomes congruent to   . But the only number satisfying both  and  is . So one of the numbers in the list is . This proves the theorem.

 This test is often used in practice.

Example. Show that  is composite.

The number  is prime to , so let . Therefore  (odd) for , using a calculator. Therefore

 

                                                                     

                                                                   

                                                                     

                                                                     

 

None of the above values equal  and so  is composite.

 

AKS Test

The Agrawal, Kayal, Saxena test was discovered in recent years (2022). It is based on Theorem 3.4 in the form that if  is any integer and  is prime to the prime number , that is to say , then

 

 

by Fermat’s little theorem (4.6). It was shown that the modulus  can be further reduced to

 

 

when , showing that when  is below a certain limit, then  is a prime. The method consists of the following procedure:

1)    Find the smallest power  such that .

2)    Find the smallest  such that  

3)    If  for some , then  is COMPOSITE

4)    If , then  is PRIME; stop.

5)    For  from  to  do:

    if  

    then  is COMPOSITE; stop. Otherwise

6)     is PRIME

 The Proof of this method is given in Dietzfellinger (2004). Although the method appears quite intricate, it has been shown that its algorithm has a polynomial complexity.

 

FACTORISING

Given a composite number , it is required to find the prime factors  and  of ,

 

Poallard’s p-1 Method

Since  is prime,  is an even number. Assume that  has only small prime factors, and let  be a multiple of , that is, . Hence,

 

                                                                                         (9.1)

 

by Fermat’s theorem, in which  is randomly chosen. The above congruence means that . As , it then means that

 

                                                                                                                          (9.2)

 

in which  is a multiple of  and is even.

 In practice  is usually chosen as . If the  equals , then a different  is chosen. The value of  is taken as  , where  are primes. It transpires that the selection of  is practically possible when  and  have small values, and so if  and  are large, the factorisation is very hard. Once the value of  is found,  is obtained as .

Example. Factorise  (the second Carmichael number).

Choose  

If , and .

If , and .

Hence . Therefore .

If  and .

If , and .

Hence,  and therefore . Thus,  

 

Pollard’s Rho Method

Let  as before. The Rho method is based on generating a suitably large sequence of pseudo-random numbers by congruence modulo . Let the sequence be generated iteratively according to the iteration

 

                                                                                  (9.3)

 

with seed , and  a nonlinear function. It has been found empirically that

       

                                                                                f                                                                                   (9.4)

 

generates the required type of sequence from (9.3).

 This sequence is cyclic composed of  distinct elements. Now, if  be an integer such that

 

                                                                                                                           (9.5)

 

and                                                                                                                                                    (9.6)

 

then the sequence is also cyclic modulo ; because

 

                                                                                  (9.7)

 

The length of the sub-cycle is  To illustrate this point, consider the case of , then the sequence according to (9.3) is

 

 

in which the sub-cycle is underlined for identification.

 In order to detect the sub-cycle , consider the sequence

 

                                                                                                      (9.8)

 

The cycle for  is given by

 

                                                                                                       (9.9)

 

Alternatively, one may consider the iteration generated by the sequence  according to

 

                                                           (9.10)

 

and consider the  (9.9) to yield the value of .

 The other factor  is given by .

 The method has been found to be of practical use when  is less than ten digits long.

 

DISCRETE LOGARITHM

Let  and  be two elements of a cyclic group of  elements , which recur repeatedly in a chain. If  is the smallest nonnegative integer  of the set such that

 

                                                                                                                                (10.1)

 

then  is called the discrete logarithm of  to the base , written as . In cryptographic applications, the existence of  is typically guarenteed.

 A very simple but expensive method of finding  is by enumeration, testing  to test whether  equals . As soon as an  value is found the testing is stopped, yielding the value of the logarithm. However, better methods have been devised as presented below.

 

Shank’s Baby Step - Giant Step Method

In this method, the upper integer part of  is set as

 

                                                                                                                 (10.2)

 

where  is the (lower) integer part of . The unknown discrete logarithm  is then represented as

 

                                                                                                      (10.3)

 

by the division algorithm, in which  and  are respectively the quotient and the remainder when  is divided by m. Thus,

 

                                                                                                                                                                 (10.4)

 

or,                                                                                                                                 (10.5)

 

In the above Eq. (10.5), compute the set of baby steps:

 

                                                                                                       (10.6)

 

Now, in the set  look for a pair , then , or , and thus .

If in the set  the pair  is not found, set  and test for  the remainder . If this number is the first component of an element in , that is, , then

 

                                                                                (10.7)

 

so that , and the discrete logarithm is . The steps  are called giant steps.

Example. Find .

Here with . We therefore form a table for B:

 

None of the values in the second column equals . The baby steps do not yield the required logarithm. Hence set  for the giant step. Hence, we form the table

2

 

Therefore, the solution is . Hence,

 

Pohlig - Hellman Method

In this method in order to find , where  is an element of the cyclic group of  elements  so that , let  be factored in to primes (Theorem 3.3) as

 

                                                                                                                                               (10.8)

 

Also, for each prime divisor  of , let

 

                                                                                                                                             (10.9)

 

then it follows that  is an element of a cyclic group of  elements, and so

 

                                                                                                                                                        (10.10)

 

exists,

 Now consider the simultaneous congruences

 

                                                                                                                          (10.11)

 

whose solution by the Chinese Remainder Theorem is of modulus  or . We assert that the solution of the system (10.11) is , since

 

                                                                        for some                                                                            (10.12)

 

Hence,

                                                                              

                                                                                          

                                                                                          

or,

                                                                                                                                                (10.12)

 

Now, the number

 

                                                                            

 

have no common factor except , that is their . Hence by the extended Euclidean algorithm (Theorem 2.4), integers  exist such that

 

                                                                                                                                 (10.13)

 

Thus, multiplying both sides of (10.12) by  and sum over , one obtains

 

                                                                                                (10.14)

 

or, . The problem therefore reduces to solution of the system of congruences (10.11), by say Shank’s baby step giant step method.

Remark. In the above method, if , it is possible to further reduce the modulus from  to . As a generic form consider the solution of

 

                                                                                                                                                                  (10.15)

 

to find . For that purpose express integer  to the base  (instead of decimal ) by writing

 

                                                                                                                         (10.16)

 

where , and . Therefore,

 

                                                                                        

                                                                                       

                                                                                       

and so,                                                                                                                                      (10.17)

 

Similarly,                                                               

 

or,                                                                                                                           (10.18)

 

and in general,

                                                                                              (10.19)

 

The iterations  may be determined by Shank’s baby - step giant - step method, determining x given by Eq. (10.16) in modulus .

 

ELLIPTIC CURVES IN REAL DOMAIN

The number theoretic applications of elliptic curves have far reaching consequences like the historic proof of Fermat’s Last Theorem by Andrew Wiles in 1995. It provides a powerful tool in Cryptography. The genesis of the study of these curves lies in the development of the elliptic function  by KarlWeierstrass as the solution of the differential equation

 

                                                                                                                                                           (11.1)

 

in the complex domain. Instead of dwelling in that subject, there arises the study of Elliptic Curves in the  domain as the solution of the algebraic equation

 

                                                                                                                                              (11.2)

 

From the Theory of Equations, if , only one of the zeros of the cubic on the right-hand side of Eq. (11.2) is real, and the curve has a symmetrical form as shown in figure 1.

In order to construct an algebra of points , the coordinates are viewed as a paired number associated with . For such formalism, it is at first convenient to express the equation of  in homogeneous coordinates  in the form

 

                                                                                                                                          (11.3)

 

 

so that  and . This form of the equation has the advantage that the point at infinity is also taken in to account. For that point  and so  from Eq. (11.3) The arbitrary value of  is chosen as  to set the coordinates of the point as . The other points in the finite domain are . The points therefore form the set

 

                                                                                               (11.4)

 

For brevity   will be written as  and  as .

 The algebra of points (or number pairs) on the elliptic curve is developed in the following manner. Let  and  be two points on the curve. Their sum  is defined as the reflection  of the point of intersection  of the chord joining  and . Let the equation of the chord be ; then since it passes through  in which  is the slope of the chord viz.

 

                                                                             if                                                                                     (11.5)

 

In the particular case  equals  at the point , Hence from Eq. (11.2)

 

                                                                               

 

or,                                                                                 

and therefore

 

                                                                          if                                                                                     (11.6)

 

In order to find the coordinates of , substituting  in Eq. (11.2)

 

                                                                           

 

or,                                                             

 

whose roots are  and . Hence,

 

                                        

 

                                                           

 

Equating the coefficients of  on the two sides of the above identity

 

 

or,                                                                                                                         (11.7)

 

Eq. (11.7) gives the value of . The value of , keeping in mind the reflection of  about the -axis leads to

 

 

or,                                                                                                                                                        (11.8)

 

which yields the value of .

 In the above construct, if  and , then according to Eq. (11.6), the chord is parallel to the -axis and  is a point at infinity, that is . In this case , which is rewritten as . This means that since  and . Thus  acts like zero for elliptic curves and so .

 

Finite Field Elliptic Curves

The algebraic construct of the elliptic curves in the domain of real numbers can be restricted to a finite field  of integers by considering only the points belonging to such restricted set of numbers in which addition is interpreted as a modulo  sum. Thus, an elliptic curve on the prime field  is the set

 

                                                                                                        (11.9)

 

with the algebraic properties that

   for

   for  and  

 If  and then,

                                      

where , and

 

 

It can also be shown that the addition law is a associative, that is . The proof of this property is intricate and omitted here.

Example. Find the set of points in  of  

The points can be found by setting  and checking for which values the quantity  is a square modulo 7.

For  which has no   solution.

For , which has no  solution.

For  and  

For , which has no  solution.

For  and  

Proceeding in this manner, for  and  there is no solution. Hence,

 

                                                                           

 

In general, it is clear that the set of points  is finite, since there can only be finitely many possibilities for the  and . To be precise, there are  possibilities for  and then for each value of , the equation of the elliptic curve can yield only two possibilities for . Adding the extra point , the number of points   can at most be  A tighter limit is however given by Hasse’s theorem according to which

 

                                                                                                                                                        (11.10)

 

where . The proof of this theorem is also omitted here because of further technicalities involved.

 It can be foreseen that the complicated way of deciphering the number pairs of an elliptic curve in prime field  makes it eminently suitable for Cryptography.

 

Conclusion

Cryptographic methods for securing digital data is heavily dependent on some Number Theoretic results. This survey article presents the essentials of this algebraic topic in a simple, clear manner, in aid of studying the subject of Cryptography. In summary, the algebra of congruences, prime numbers and several theorems related to them are covered. These topics include, representation of the division algorithm as a congruence, Euclid’s algorithm for calculating GCD, properties of prime numbers leading to the theorems of Fermat and Euler, developing the properties of the latter’s phi function, linear congruences and the Chinese remainder theorem; primality tests, factorisation of composite numbers and discrete logarithms. Finally, a description of the elliptic curve prime field is presented, which has lately come in to prominence. A quick study of this survey, it is hoped will be a useful aid for a prospective reader of the subject of Cryptography.  

  

ACKNOWLEDGMENTS

The author is sincerely thankful to Ajijul Hoque, Department of Mathematics, IIT Kharagpur for helping preparation of this article.

 

Declarations

There are no conflicts of interest in the research reported in this paper. And no data were generated or analysed by AI or otherwise in the presented research.

 

REFERENCES

Bernard, S., and Child, G. M. (1965). Higher Algebra. Macmillan.  

Buchmann, J. A. (2002). Introduction to Cryptography. Springer.  https://doi.org/10.1007/978-1-4684-0496-8   

Chrystal, G. (1906). Algebra: An Elementary Text-Book, Part II. Adam and Charles Black.  

Dietzfellinger, M. (2004). Primality Testing in Polynomial Time (Lecture Notes in Computer Science, Vol. 3000). Springer-Verlag. https://doi.org/10.1007/b12334   

Hardy, G. H., and Wright, E. M. (1938). An Introduction to the Theory of Numbers. Clarendon Press. 

Hoffstein, J., Pipher, J., and Silverman, J. H. (2008). An Introduction to Mathematical Cryptography. Springer. 

McAndrew, A. (2011). Introduction to Cryptography with Open Source Software. CRC Press.  

Niven, I., Zuckerman, H. S., and Montgomery, H. L. (1991). An Introduction to the Theory of numbers. John Wiley and Sons.  

Paar, C., and Pelzl, J. (2010). Understanding Cryptography. Springer. https://doi.org/10.1007/978-3-642-04101-3   

Rosen, K. H. (2005). Elementary Number Theory and its Applications. Pearson/Addison Wesley.