This is a textbook in cryptography with emphasis on algebraic methods. It is supported by many exercises with answers making it appropriate for a course in mathematics or computer science. Overall, this is an excellent expository text, and will be very useful to both the student and researcher. I think this book is a very inspiring book on cryptography. It goes beyond the traditional topics most of the cryptosystems presented here are first time in a textbook, some of Patarin's work is not published yet.
This way the reader has the feeling how easy to suggest a cryptosystem, how easy to break a safe looking system and hence how hard to trust one. The interested readers are forced to think together with their researchers and feel the joy of discovering new ideas.
At the same time the importance of "hardcore" mathematics is emphasized and hopefully some application driven students will be motivated to study theory. Overall, the book is highly recommended to everyone who has the requisite mathematical sophistication. It goes beyond the traditional topics most of the cryptosystems presented here are first time in a textbook, some of Paturi's work is not published yet.
The interested readers are forced to think together with ther researchers and feel the joy of discovering new ideas. Der Autor, der Skip to main content Skip to table of contents. After only n applications of the algorithm, you will have found a nontrivial factor of N. So the algorithm for the decision problem has been converted into an algorithm for the corresponding search problem.
First question to algorithm: Does 9 1 have a factor between 2 and 63? Answer: YES. Second question: Does 9 1 have a factor between 2 and 3 1? Third question: Does 9 1 have a factor between 2 and 1 5? Fourth question: Does 9 1 have a factor between 2 and 7?
Fifth question: Does 9 1 have a factor between 2 and 3? Answer: NO. Sixth question: Does 91 have a factor between 2 and 5? Seventh question: Does 91 have a factor between 2 and 6? We conclude that 7 is a nontrivial factor of 9 1. Note that this method of binary search using an algorithm for the Integer Factorization decision problem will always lead to the smallest nontrivial factor of N.
Thus, from the standpoint of computer science, there is often no loss of gener ality in working with decision problems rather than search problems. Notice the close relation between Definitions 4. Definition 4.
It is not a priori clear that P is the right class to take for this. For instance, an algorithm with running time n , where n is the input length, is slower than one with running time e 1 n until n is greater than about ten million, even though the first algorithm is polynomial time and the second one is exponential time. In this connection see 7.
However, the experience has been that if a problem of practical interest i s i n P, then there is an algorithm for it whose running time is bounded by a small power of the input length. Sometimes a problem that is in P or is believed to be in P has a practical, efficient algorithm that is not polynomial time. If the so-called "Extended Riemann Hypothesis" is true, then an algorithm in [Miller 1 ] will answer this question in polynomial time.
Alternatively, we could define "time" to be the number of bit operations required to carry out the algorithm. There is an algorithm due to Atkin that is much more efficient in practice, but no one can prove a rigorous bound on its running time; in particular, Atkin's algorithm is not known to be polynomial time. Thus, empirically it seems that the problems in P that are of practical interest all have efficient algorithms, although in some cases the most efficient algorithms are different from the polynomial time algorithms and in other cases they are not the ones that lend themselves to a rigorous analysis of the running time.
A decision problem P is in the class NP if, given any instance of. P, a person with unlimited computing power not only can answer the question, but in the case that the answer is "yes", she can supply evidence that another person could use to verify the correctness of the answer in polynomial time. Her demonstration that her "yes" answer is correct is called a "certificate" more precisely, a polynomial time certificate.
A decision problem P is said to be in the class co-NP if the above condition holds with "yes" replaced by "no". That is, for any instance having a "no" answer there must exist a polynomial time certificate that the "no" answer is correct. Consider the above decision version of Integer Factorization:.
This problem is almost certainly not in P. However, it is in NP. Namely, suppose that an all-powerful person such as God or an advanced extraterrestrial being factors N and finds that it has a factor NJ E [2, k]. After this person tells you that the answer is "yes", she supplies NJ, from which you can verify the correctness of her answer in polynomial time, simply by dividing M into N.
The Integer Factorization problem is also in co-NP, although to see this requires more thought. If the answer to the above question is "no", the extraterrestrial gives you the complete prime factorization of N, from which you can immediately see that there is no prime factor ::; k. At the same time she must also give you a certificate with which you can verify in polynomial time that each of the prime factors really is prime.
There are various certificates that can be given; the oldest and simplest is due to Pratt see, for example, Theorem 8. The Traveling Salesrep decision problem is almost certainly not in P. That is, suppose that an extraterrestrial being finds the most economical tour for the traveling salesrep,. She tells you that the answer is "yes", and then shows you the route, at which point you can rapidly verify that her "yes" answer is in fact correct.
In the same way, one easily sees that the 3-Coloring decision problem is in NP. If a problem is in P, then trivially it is in NP. That is, PcNP. It is almost certain that NP is a much bigger class of problems than P, but this has not been proved. The claim that P NP is the most famous conjecture in computer science. Let P 1 and P2 be two decision problems.
We say that P 1 reduces to P2 more precisely, reduces to P2 in polynomial time if there exists an algorithm. One basic use for this notion of reduction is as follows.
Suppose that we have an efficient algorithm for P2 If P1 reduces to P2 , then we can use the algorithm for P2 to solve P1 as well. Namely, given an instance of P1 , in polynomial time we find a corresponding instance of P2 using the algorithm in Definition 4.
Then if we apply our algorithm for P2 to this instance of P2 , the answer we get is also the answer to our original P1 question. That is, an algorithm for P2 automatically gives an algorithm for P1. If our algorithm for P2 is a polynomial time algorithm, then so is the resulting algorithm for P1. Let P1 be the following problem:. We show that P1 reduces to P2. Set N b2 - 4ac, which can be computed in polynomial time. Suppose that we know or believe the problem P1 to be very difficult.
That is, we are virtually certain that there is no efficient algorithm for it. If P1 reduces to P2, then it follows that there is no efficient algorithm for P2 either.
It is worthwhile to have a broader definition of polynomial time reduction of P 1 to P2 that allows us to use several. Let P2 be a decision or search problem.
In describing an algorithm for some other problem P1 , whenever we say "call to a P2 -oracle" we mean that our algorithm has created an instance of P2 , and we suppose that some other algorithm then gives us the corresponding P2 -output.
The time taken by this algorithm for P2 is not included in the running time for the algorithm for P1. In other words, we pretend that the algorithm for P2 is a "black box" that works instantaneously. To use the language of computer programming, we can think of an oracle as a subroutine that we are free to call upon without including its running time in our estimate for the total running time of our program.
Let P1 and P2 be two problems either decision problems or search problems. We say that P1 reduces to Pz in polynomial time if there is a polynomial time algorithm for P1 that uses at most polynomially many calls to a P2 -oracle. We saw that P1 can be solved with n calls to a P2 -oracle, where n is the input length. Thus, P1 reduces to P2. To put it another way, if one had a polynomial time algorithm for an NP complete problem P, then one would also have polynomial time algorithms for all other NP problems Q.
For this reason, no one is likely to come up with a polynomial time algorithm for any NP-complete problem. In a sense, the NP complete problems are the most difficult problems in the class NP. This statement should be taken cautiously. One might be able to produce an efficient algorithm - even a polynomial time algorithm - that gives an answer to most instances of a certain NP-complete problem. In practice, though, it is usually hard to efficiently solve large instances of an NP-complete problem.
Often the running times of all known algorithms grow exponentially with the length of the input. It can be shown that the Traveling Salesrep problem in Example 4. Suppose that one has a very complicated instance with several hundred cities - say, the business class airfare map for the U. It might take millions of millions of years - longer than the lifetime of the. Universe - for the fastest computers to find an optimal solution to this instance of the Traveling Salesrep problem.
It can also be shown that 3-Coloring is NP-complete. Finally, note that it is possible for a problem P to reduce to an NP-problem even though P itself is not likely to be in NP. The Exact Traveling Salesrep problem is the following decision. To provide a certificate for a "yes" answer it would not be enough simply to show a tour of length k; the extraterrestrial in Definition 4. It is very unlikely that this could be done.
On the other hand, one can use the binary search method to reduce the Exact Traveling Salesrep decision problem to the Traveling Salesrep decision problem. It is also possible but a little harder - see [Papadimitriou 1 ], p. In such a case we say that the two problems are polynomial time equivalent sometimes the term "NP-equivalent" is used.
We conclude this section with a definition that applies to problems that are not necessarily in NP. A decision or search problem is said to be NP-hard if any NP problem reduces to it. Because of the transitivity of reduction, to show that a problem is NP-hard it suffices to find a single NP-complete problem that reduces to it.
Exercises for 4. Arrange these problems from lowest to highest according to input length: a the problem of multiplying together 20 integers, each ;::; 1 0 ; b a Traveling Salesrep problem with 20 cities, where all of the distances are integers between 1 and ; c the problem of finding the roots of a quadratic polynomial whose coefficients are integers of about 50 digits; d the problem of finding all prime factors of an integer of about 40 digits.
For which of the problems a - d in Exercise 1 do you know a polynomial time algorithm? Using the big-0 notation, find an upper bound in terms of B for the input length of the Traveling Salesrep problem if the number of cities is at most B and the distance between any two cities is also at most B. Explain why the 3-Coloring problem for maps may be regarded as a special case of the 3-Coloring problem for graphs.
Explain how to use an algorithm for the Traveling Salesrep decision problem to solve the Traveling Salesrep search problem. Show that P2 reduces to P1 by constructing a reduction of instances of one problem to instances of the other.
Show that P2 reduces to P 1 by constructing a reduction of instances of one problem to instances of the other. Show that P1 reduces to Pz. Show that P1 reduces to P2 in the sense of Definition 4. It is not known w hether P2 reduces to P 1 in which case the two problems would be "polynomial time equivalent". Let p be a fixed prime, and let g be a fixed integer not divisible by p. It is not known whether P2 reduces to P1 , that is, whether the two problems are polynomial time equivalent.
In recent years important partial results have been proved that support the conjecture that P 1 is equivalent to P2. See, for example, [Boneh and Lipton 1 ]. Are the following decision problems likely to be in NP? Recall that 1r N denotes the number of primes less than or equal to N. If a subexponential time algorithm see Definition 3. True or false? Suppose that we are trying to cryptanalyze a public key cryptosystem. That is, we know the public enciphering key E and the one-to-one function fE from the set P of plaintext message units to the set C of ciphertext message units.
This is known as the cracking problem for a public key cryptosystem. Unlike the problems in the last section, the cryptanalyst knows something other than the input. Thus, the cracking problem is of a slightly different sort from our earlier examples, and so one needs a new definition that captures this situation.
Definition 5. A promise problem is a search or decision problem with a condition. When analyzing an algorithm for a promise problem, we disregard what happens when the condition fails - that is, we do not care if the algorithm gives the wrong answer or no answer at all in such a case. Example 5. It is natural to regard the cracking problem for any public key en.
The following is a promise version of the Integer Factorization search. An efficient algorithm for this promise problem would suffice to break RSA. Of course, in the unlikely event that an efficient algorithm was found that could factor a product of two primes but not a product of three primes, it would be easy to modify RSA to use moduli that are products of three primes.
It is important to distinguish between these two types of problems. We shall use the term trapdoor problem for a promise problem that asks us to reverse the basic mathematical construction of the trapdoor in a public key cryptosystem.
If we find an efficient algorithm for the trapdoor problem, then we will also have an efficient algorithm for the cracking problem. The converse is not necessarily true and even if true, it might be very hard to prove.
That is, there might be ways of solving the cracking problem without dealing directly with the underlying trapdoor function. No one has been able to prove, for instance, that the only way to break RSA is to factor the modulus.
Randomized Algorithms and Complexity Classes 6. The randomized algorithm that follows is one of the best ways of. More precisely, the test will determine either that 1 N is probably prime, or else 2 N is definitely composite. Then we raise a to the N - 1 -st power modulo N in two stages: i we find the least nonnegative residue of at modulo N by the "square and multiply" method see Example 3.
When both 1 and 2 hold, we say that N passes the strong Fermat primality test to the base a also called "Miller's test" and "Rabin's probabilistic primality test". If N fails either 1 or 2 , then it is definitely composite.
If, however, N. If the strong Fermat primality test is performed for k different randomly chosen values of a, and if N satisfies 1 and 2 for all of these a, then we can say that there is "at least a 1 - 4- k probability that N is prime". This complexity class captures what is going on in Example 6. Definition 6. We say that a decision problem P is solvable in randomized poly nomial time or "probabilistic polynomial time" and we write P E RP if there. In Example 6. Example 6. Another example of a problem in.
Here each polynomial in the input is listed by giving its terms with nonzero coefficients. If the polynomials are "sparse" - that is, if most of their coefficients are zero - then the input length will be much less than if the polynomials were given by listing all of the terms including the ones with zero coefficient in lexicographical order.
Notice that the running time for the obvious method of answering the question - by simply multiplying out both sets of polynomials - is not generally bounded by a polynomial in the input length. In fact, the number of nonzero terms in each product polynomial might be exponentially large as a function of the input length. Sup pose that the P, and Q1 are polynomials in l variables X 1 , , X1 In some random way choose l rational numbers x1 ,.
Then determine whether or not. If not, then you know that the two products of polynomials are unequal; that is, the answer to Product Polynomial Inequivalence is definitely "yes". If, on the other hand, the above products of rational numbers are equal, then the answer is probably "no". Of course, one cannot be sure that two polynomials are identically equal just because their values at a particular point are equal.
But if their values are equal at a large number of randomly chosen points, then one can say that they are almost certain to be equal - that there is a probability at least 1 E that "no" is the correct answer where E is a constant that does not depend on the input. Using standard techniques of probabilities and statistics, one can show that for any constant o there exists a constant k such that there is a probability greater than 1 E that the "vote" algorithm gives the correct answer.
If we toss the coin a sufficiently large number of times, there is a greater than The definition of the class BPP is fairly broad. Yet Definition 4. See the discussion of P and practicality following Definition 4. Exercises for 6 1. As a function of the input length in the Compositeness problem, what is the order of magnitude of time required for a single strong Fermat primality test?
Here co-RP denotes the set of decision problems that satisfy the definition of RP with "yes" and "no" reversed. The latter class is often denoted ZPP. Some Other Complexity Classes 7.
Definition 7. Define L1 2 to be pNP , which is the class of decision problems that have a polynomial time reduction in the sense of Definition 4. Let L1 1. E2 to be NPNP This is the class of decision problems whose "yes" answers have a certificate that can be verified by a polynomial time algorithm using an oracle for a problem in NP. That is, an extraterrestrial with unlimited computing power could, in the case of a "yes" answer to an instance of the problem, produce a certificate such that the following holds: there is a problem Q ENP and a polynomial time algorithm with at most polynomially many calls on a Q-oracle that you can use to verify the certificate and thereby be certain that the "yes" answer is correct.
Notice the difference between NP and E2 In the former we need certificates that can be checked in absolute polynomial time. In the latter we are allowed to use an oracle for any fixed NP-problem in our algorithm for checking the certificate. The classes L1 2 and E2 make up the "second level of the polynomial hierarchy", along with IJ2 , which is the co-class of E2 , i. In other words, each level is constructed using oracles for problems from the previous level. It is easy to see that each level of PH is contained in the next level.
It has not been proved that any of these containments are proper; it is conjectured that they all are. The study of PH itself is mainly of theoretical interest; from a practical point of view, there are very few interesting problems in PH that lie above the second level of the hierarchy. The class UP "unique P" consists of NP-problems for which there exists a prescription for a uniquely determined polynomial time certificate for any instance having a "yes" answer.
For example, the Traveling Salesrep decision problem is not likely to belong to UP. The obvious certificate for a "yes" answer - a description of a tour of length ::; k - is not, in general, unique. See the remark preceding Example 4. It can be shown that the one-way encryption functions of public key cryptography see Definition 2. It is obvious that PcUPcNP; however, neither of these inclusions has been proven to be a strict inclusion.
The notions of complexity discussed thus far all relate to the worst case of a problem. For example, an NP-problem P is NP-complete if, roughly speaking, an algorithm that efficiently solves all instances of P including the most difficult ones - would lead to an efficient algorithm for any other NP-problem Q. But suppose that we have an algorithm that efficiently solves most instances of an NP-problem P with some reasonable definition of the word "most".
That might be enough for our practical applications. However, this would not necessarily -. It might tum out that our method of reducing Q to P usually leads to instances of P that are not included in the "most" - that is, the instances of Q that are of practical interest might reduce to instances of P that the algorithm cannot solve efficiently. In cryptographic applications it is not really enough to know that the hardest instances of the cracking problem or the trapdoor problem see 5.
What one wants to know is that "most" instances or most instances constructed so that some additional conditions hold are hard. For example, the security of RSA is based on the assumption that most numbers obtained as the product of two randomly chosen large primes are hard to factor. How could one give a precise definition that captures this notion?
The following definition is due to Levin [ 1 ]. Let P be a decision or search problem, and let. Intuitively, if S is a set of instances of P of input length at most n, then. Roughly speaking, Definition 7. See Exercise 2 below. For more discussion of Levin's definition and other aspects of average-case complexity and cryptography, see [Ben-David, Chor, Goldreich, and Luby 1 ] and [Impagliazzo 1 ]. Both cryptographic protocols and games are characterized by interaction between two or more "players".
Various complexity classes have been defined to deal with such situations. One of the most important is the class IP of problems solvable by interactive proof systems. Merlin is like the advanced extraterrestrial being in the definition of NP. He is presumed to have unlimited computing power. He must convince Arthur that a certain instance of a decision problem has answer 'yes. Rather, it will probably take a fairly lengthy interchange of messages before Arthur is convinced beyond a reasonable doubt that the answer is 'yes.
If he is satisfied with Merlin's responses, eventually he will have to admit that there is a probability less than E that Merlin could have given those answers if the correct answer were 'no. The complexity concepts in the earlier sections do not cover all possible features of an algorithm one might construct to break a cryptosystem. For example, some problems can be solved using massively parallel computations.
That is, algorithms are known that can be greatly speeded up if we have a vast number of computers all working at once. In other cases, all of the known algorithms have to be carried out largely in series rather than in parallel, and so it would not help much to have several processors simultaneously working on the problem.
We will not dwell on massively parallel complexity classes, because thus far they have not been of great importance in cryptography. However, we shall give one definition in order to give the flavor of the subject. The class NC consists of decision problems for which there exist. Another concept that has relevance to cryptography is non-uniformity. Notice that Definition 7. For example, the set-up of these algorithms might require a lengthy "pre-computation" whose running time grows exponentially in n.
However, once An is set up, it will be able to quickly solve an arbitrary instance of input length S n. In practice, it often happens that we know in advance that we will want to solve instances of a problem P whose input lengths vary in a small range, for example, 1 00 S n S 1 We might be willing to go to tremendous effort to set up an algorithm that works only for n S 1 The time and money to do this must be spent just once, after which the algorithm handles our needs cheaply and efficiently.
To some extent Definition 7. Exercises for 7. Prove that the trial division algorithm for factorization is not polynomial time on average. In the trial division algorithm one divides all odd numbers 3 , 5 , 7,.
Show that P is not polynomial time on average with respect to this algorithm in the sense of Definition 7. Suppose that Levin's property in Definition 7. Show that a function T i that satisfies this property also satisfies Levin's property, but the converse is false. Show that the following problem is in NC.
The input consists of two polynomials with integer coefficients, where the maximum absolute value of the coefficients is less than the degree. The input is given by listing all of the coefficients not only the nonzero ones. The output is the sum of the two polynomials. We start out by recalling the basic definitions and properties of a field. A field is a set IF' with multiplication and addition operation s that. The following fields are basic in many areas of mathematics: 1 the field Q consisting of all rational numbers; 2 the field lE.
Any vector space has a basis, and the number of elements in a basis is called its dimension. An extension field, by which we mean a bigger field containing IF', is automatically a vector space over IF'. We call it a finite extension if it is a finite dimensional vector space. By the degree of a finite extension we mean its dimension as a vector space.
One adds and multiplies polynomials in IF'[X] in the same way as one does with polynomials over the reals. We say that the polynomial is monic if the coefficient of x d is 1. Polynomial rings in one or more variables have unique factorization, meaning that every polynomial in lF[X] can be written in one and only one way except for constant terms and the order of factors as a product of irreducible elements of lF[X].
In that case there is a unique monic irreducible polynomial in lF[X] of. This monic irreducible polynomial is called the minimal polynomial of ex. If the minimal polynomial of ex has degree d, then any element of lF ex that is, any rational expression involving powers of ex and elements of lF can be expressed as a linear combination of the powers 1 , ex, ex2 ,.
Thus, those powers of ex form a basis of lF ex over lF, and so the degree of the extension obtained by adjoining ex is the same as the degree of the minimal polynomial of ex. Any other root ex' of the minimal polynomial of ex is called a conjugate of ex over lF. The product of all of the conjugates of ex including ex itself is called its norm.
The word "isomorphic" means that we have a 1 -to- 1 correspondence between the two fields that preserves addition and multiplication. If it happens that lF ex and lF ex' are the same field, we say that the map that takes ex to ex' gives an automorphism of the field.
The derivative of a polynomial in one variable and the partial derivatives of a polynomial in several variables are defined using the nx n - 1 rule. If it does, then the degree-! Because of unique factorization, the total number of roots of f in lF counting multiplicity cannot exceed d.
Algebraic extensions of finite fields and extensions of fields of characteristic zero are always separable. C[X] splits into a product of linear factors equivalently, has d roots in llC counting multiplicity, where d is its degree and such that llC is the smallest extension field containing those roots. The splitting field is unique up to isomorphism, meaning that if we have any other field l! C' with the same properties, then there must be a 1 -to- 1 correspondence llC l!
C' that preserves addition and multiplication. If a field IF' has the property that every polynomial with coefficients in IF' factors completely into linear factors, then we say that IF' is algebraically closed.
Equivalently, it suffices to require that every polynomial with coefficients. For instance, the field C of complex numbers is algebraically closed. The smallest algebraically closed extension field of IF' is called the algebraic closure of IF'. It is denoted iF. For example, the algebraic closure of the field of real numbers is the field of complex numbers. If adding the multiplicative identity 1 to itself in IF' never gives 0, then we say that IF' has characteristic zero; in that case IF' contains a copy of.
In that case IF' contains a copy of the field 7Lfp7L, which is called its prime field. Let llC be the splitting field of the polynomial X 3 - 2 over IF'. Explain your answers. Prove that a polynomial in IF'p [X] has derivative identically zero if and only if it is the p-th power of a polynomial in IF'p [X].
Give a criterion for this to happen. Let IF' q denote a field that has a finite number q of elements in it. By choosing a basis, we can set up a l -to- 1 correspondence between the elements of this f -dimensional vector space and the set of all f -tuples of elements in IF'P ' It follows that there must be p f elements in IF'q That is, q is a power of the characteristic p. But first we investigate the multiplicative order of nonzero elements of IF'q.
By the "order" of a nonzero element we mean the least positive power which is l. The group of nonzero elements of IF'q is denoted IF'. It is an easily proved fact about finite groups that the order of any element must divide the number of elements in the group.
Thus, the order of any a E IF' divides q - l. A generator g of a finite field IF' q is an element of order q - 1 ; equivalently, g is a generator if the powers of g run through all nonzero elements of IF'q. The next theorem gives a basic fact about finite fields.
It says that the nonzero elements of any finite field form a cyclic group; in other words, they are all powers of a single element.
Theorem 2. Every finite field has a generator. If g is a generator of IF', then gJ is also a generator if and only if g. Thus, there are a total of r. Suppose that. As mentioned above, d divides q - l.
Since a d is the smallest power that equals l , it follows that the elements a, a2 ,. We claim that the elements of order d are precisely the r.
Any element of order d must therefore be among the powers of a. However, not all powers of a have order d. Namely, if g. Conversely, if g. Thus, aJ has order d if and only if g. The rest of the argument depends on the following lemma. Lemma 2. For any integer N.
That is, we put j in the set Sd if g. We now return to the proof of the theorem. Every element of IF has some order d dividing q 1. This completes the proof. Corollary 2. For every prime p, there exists an integer of g exhaust all nonzero residue classes modulo p.
Namely, the successive powers of 2 reduced mod 19 are: 2, 4, 8, 1 6, 1 3 , 9, 1 8, 17, 15, 1 1 , 3, 6, 12, 5, 10, 1. The following theorem shows that for every prime power q there is one and up to isomorphism only one finite field with q elements. First suppose that IF' q is a finite field. O f course, the element 0 also satisfies the latter equation.
Thus, all q elements of IF'q are roots of the degree-q polynomial X q - X. Since this polynomial cannot have more than q roots, its roots are precisely the elements of IF' q Notice that this means that IF'q is the splitting field of the polynomial X q - X, that is, the smallest field extension of IF'P that contains all of the roots of this polynomial.
Thus, IF' must contain at least the q distinct roots of X q - X. But we claim that the set of q roots is already a field. The key point is that a sum or product of two roots is again a root. The lemma is proved by observing that all of the intermediate terms vanish in the binomial expansion 'Ljo j aP - j OJ , because p! We conclude that the set of q roots is the smallest field containing the roots of X q - X; in other words, the splitting field of this polynomial is a field of q elements.
We derive another important consequence of this in the next theo rem. The elements of IF' q which are kept fixed by IJ are precisely the elements of the prime field IF'p The f -th power and no lower power of the map IJ is the identity map. A map that raises to a power always preserves multiplication. The fact that. IJ preserves addition comes from Lemma 2. Notice that for any j the j-th power of IJ the result of applying IJ repeatedly j times is the map a , The elements.
D Theorem 2. In the notation of Theorem 2. Thus, one obtains d distinct elements by repeatedly applying a- to o:. It now suffices to show that each of these elements satisfies the same monic irreducible polynomial f X that o: does, in which case they must be the d roots.
So far our discussion of finite fields has been rather theoretical. We now discuss how to work with finite extensions of IFp. At this point we should recall how in the case of the rational numbers Q we work with an extension such as Q Vl.
We can take the same general approach with finite fields. We sometimes say that the polynomial X 2 - X - l is primitive, meaning that any. Then the field IF'p a obtained by adjoining this element to the prime field is an extension of degree d that is contained in IF' q. That is, it is a copy of the field IF'P ". Thus, we have proved: Theorem 2. It is now easy to prove a formula that is useful in determining the number of irreducible polynomials of a given degree.
Computability and Complexity of algorithms in group theory used in cryptography as well as generic case complexity. Cryptographic problems : Commutative and non-Commutative public key exchange problems, digital signatures, authentication. Aspects of non-abelian group-based cryptography: a survey and open problems, B. Fine, M. Habeeb, D. Kahrobaei, G.
0コメント