I. INTRODUCTION
Let , . By a ring we mean a commutative ring with unity. Let R be a ring. Denote by the group of all invertible elements of R. The set of all irreducible elements in R will be denoted by Irr R. By a domain we mean a commutative ring with unity without zero divisors. An element is called nilpotent if there is such that .
The most important motivation for writing this paper is to quote the most important results related to polynomial composites, their algebraic place in mathematics and their application in cryptology.
D.D. Anderson, D.F. Anderson, M. Zafrullah in [2] called object as a composite, where A be a subdomain of the field B. If B be a domain and M be an additive cancellative monoid (a semigroup with neutral element and cancellative property) we can define a monoid domain . If , then . Monoid domains appear in many works, for example [8], [16].
There are a lot of works where composites are used as examples to show some properties. But the most important works are presented below.
In 1976 [4] authors considered the structures in the form D + M, where D is a domain and M is a maximal ideal of ring R, where D \subset R. Later In the second section we can find many results about polynomial composites and monoid domains. Basic algebraic properties such as irreducible elements, nilpotents and ideals have been examined. Theorem 2.6 is especially worth noting. In this theorem, for be fields, we can note that every nonzero prime ideal polynomial composites is maximal, every prime ideal different from some maximal ideal of polynomial composite is principal and every polynomial composites are atomic (every element of polynomial composites be a product of finite irreducibles (atoms)). In Theorem 2.9 we have an information about irreducibles of monoid domain. In the second part of the second section we have results about ACCP and atomic properties. Recall, a property: for any ascending chain of principal ideals of ring , there is such that . A domain with ACCP property is called ACCP-domain. Every ACCP-domain be atomic. In Theorem 2.23 it turns out that the polynomial composite of the form (where be fields) is a Dedekind ring. This is a very important class of rings in algebra.
In the third section we can find relationships between a theory of polynomial composites and Galois theory. Galois theory contributed greatly to the development of many fields, not only in mathematics. Particularly noteworthy is the solution of three ancient problems of construction with a compass and a straightedge in the 19th century. The results in this section, under different assumptions, boil down to the relationship between field extensions and Noetherian rings. Recall a Noetherian ring is called a ring with ACCP-property. Equivalence, a ring such that every ideal be a finite generated. In Theorems 3.13 and 3.14 we combine the Magid's results with the current results to create a complete characterization of field extensions using polynomial composites and idempotents. Recall, an element is called idempotent if holds. For example, in we have two trivial idempotents 0 and 1.
Sections four and five are reminder from a generalized RSA cipher and a Diffie-Hellman protocol key exchange. Such a reminder is purposeful because we want to draw attention to the replacement of the finite alphabet with the infinite one and the replacement of classical prime numbers with prime ideals. Such a swap will be extremely difficult for third person to break.
In sections six and seven we have cryptosystems which use the structure Dedekind. The former uses this structure in the key, and the latter uses it in two different alphabets. Of course, these ciphers can be generalized to infinite alphabets and ideals.
Section eight shows a cryptosystem based on polynomial composites. Section nine shows a cryptosystem based on monoid domains. Note that in the last cryptosystem, in order to break it, the discrete logarithm calculation should be used. At the moment, there is no mathematical way to facilitate the computation of discrete logarithms. We can count using computers, but here the algorithm would consist in checking each successive number, not on a specific indication of the number. And this is a great difficulty in breaking the last cryptosystem.
II. POLYNOMIAL COMPOSITES AND MONOID DOMAINS
In this section we introduce the most important facts about polynomial composites and monoid domains in math.
Let , where be domains such that , .
Let's start from the following Lemma which is very easy to proof.
Lemma 2.1. , be rings, .
Now let's look at invertible and nilpotent elements.
Proposition 2.2. Let for any . Then if and only if and are nilpotents.
Proof. We know that if R is a ring then if and only if and are nilpotents. In our Proposition we have are nilpotents. Of course we get .
Proposition 2.3. Let , where and for and for .
(i) if and only if and are nilpotents.
(ii) be a nilpotent if and only if are nilpotents.
Proof. Analogous proof like in Proposition 2.2.
Proposition 2.4. Let B be a domain and , where and .
(i) if and only if there exist such that and and for every we have be nilpotents.
(ii) be a nilpotent if and only if are nilpotents.
Proof. (i) Assume . Then there exists , where and such that fg = 1. Hence there exist such that . We have and . The rest of coefficients are nilpotents. On the other side of the proof it is easy.
Ref (ii) Obvious.
Let's recall Theorem from [2](Theorem 2.9) in a different form.
Theorem 2.5. Let be a subfield of . Consider . Then .
Theorem 2.6. Consider , where be a subfield of ; , where be fields. Then (i) every nonzero prime ideal of ( , respectively) is maximal;
(ii) every prime ideal P different from (in ) is principal;
(iii) every prime ideal different from (in ) is principal;
(iv) is atomic, i.e., every nonzero nonunit of is a finite product of irreducible elements (atoms);
(v) is atomic.
Proof. (i). We proof for . The proof for will be a corollary.
First note that is maximal since . Let P be a nonzero prime ideal of . Now implies and hence so . So suppose that . Then for , is a prime ideal in the PID . (In fact, and is a DVR (discrete valuation ring)). So P is minimal and is also maximal unless . But let with , where for any n, s. Then , so implies that , a contradiction. So every nonzero prime ideal is maximal.
(ii), (similarly (iii)). If P is different from , then it contains an element of the form , where for and . Now if can be factored in it can be written as , where for and . Hence is irreducible in if and only if it is irreducible in .
Now let be irreducible in and suppose that in . Then in , and so in we have, say . Then, in , . Now can be written as . If r > 0, , while if r = 0, and because . In either case, and so in . Consequently, in every irreducible element of the type is prime.
Now since every element of the form is a product of irreducible elements of the same form and hence is a product of prime elements, it follows that every prime ideal of P different from contains a principal prime and hence is actually principal.
(iv) (similarly v). From (ii) a general element of can be written as , where (with if r=0) and is a product of primes.
Now, We give some basic information related to ideals.
Corollary 2.7. (i) If be a field, then be an maximal ideal in .
(ii) If be an integral domain, then be an prime ideal in .
(iii)
(iv)
(v) Let be fields in . be a field for any .
(vi) Let be fields in . be a field for any such that .
Proof. (i) Let be a field. The proof follows from . We have is a maximal ideal in .
(ii) - (iv) Obvious.
(v), (vi) From Theorem 2.9 in [2] aX for any is an irreducible element. We get be a field. We also have for any such that is a irreducible element. We have be a field.
Corollary 2.8. (i) If be a field (where ), then be an maximal ideal in .
Ref (ii) If be a domain, then be an prime ideal in .
(iii)
(iv) .
(v) Let be fields in . be a field for any .
(vi) Let be fields in . be a field for any , such that .
Proof. The proof is similarly to proof of Corollary 2.7.
Theorem 2.9. Consider , where be a subfield of ; , where be fields. Then (i) if and only if , .
(ii) if and only if , , where with for and .
Proof. (i). Suppose that or . If , then , so . Now, assume that . Then f = gh, where . Let . We have . Then , where . Now, suppose that . If , then . Now, assume that . Then we have f = gh, where . This implies .
(ii) Occur in the same way as in (i).
In [8], Lemma 6.4 we have informations about irreducible element in monoid domain , where be a domain, and be a submonoid of . I present a generalized Proposition.
Proposition 2.10. Let B be an integral domain with quotient field K and M a monoid with quotient group . Assume that B contains prime elements . Assume that M is integrally closed and each nonzero element of G is type (G satisfies the ascending chain condition on cyclic subgroups). Consider such that and . Then .
Proof. Let be a total order on G. We may assume that . Suppose that with . Write and in canonical form, where and . First assume that either f or g is a monomial, say . Then . Since , either t or is invertible in M. If is invertible, then , a contradiction. Thus t is invertible in M, and hence f is a unit in B[M]. Thus we may assume that f and g are not monomials. Now consider the reduction of modulo the ideal . Then . This means that . In this case , a contradiction. Thus .
Proposition 2.11. be a field, where be a domain, with , .
Proof. It follows from Proposition 2.10.
Recall that Noetherian rings satisfy the ACCP condition. Almost every mathematician has encountered such rings. For example, Z is a Noetherian ring. Below are the results of ACCP properties in polynomial composites and monoid domains.
Proposition 2.12. Let A be an integral domain, B be a field such that . Let R be a ring with . Then R has ACCP if and only if has ACCP and for each ascending chain of polynomials where all have the same degree, then there is such that .
Proof. [11], Proposition 2.1.
Proposition 2.13 shows that between and we can find a structure which satisfying ACCP condition.
Proposition 2.13. Let be an integral domain, be a field such that . Let be a domain such that . Suppose that for each , there exists for all with . Then has ACCP if and only if has ACCP.
Proof. [11], Proposition 2.2.
The above Proposition is not obvious for arbitrary composition. This would be a valuable remark, as it would allow we to choose the smallest possible composite.
Question: For subdomains of a field B, is the Proposition 2.13 valid for such domain C satisfying , where the condition holds or not?
Kim in [8] proved very serious fact about ACCP monoid domain.
Lemma 2.14. Let A be a domain. Then A has ACCP if and only if has ACCP.
Proof. [8], Corollary 2.2. Can be easily proved by comparing degrees.
It also turn out that ACCP property moves between A and . This is important because we do not have to choose a general polynomial, and we can limit the inclusion to the smallest composite needed. Such a significant limitation of a polynomial to a composite is important, e.g. in Galois theory in commutative rings.
Theorem 2.15. Let be an integral domain, be a field such that . An has ACCP if and only if has ACCP.
Proof. From Proposition 2.13 we have , where be a quotient field of . We can to prove that for each , there exists for all with . Because has ACCP then from Proposition 2.13 we get has ACCP. Conversely, because has ACCP then has ACCP.
The next facts are the conclusions of Theorem 2.15.
Corollary 2.16. Let be subdomains of a field such that . Let be a domain with . Suppose that for each , there exists for all with . Then has ACCP if and only if has ACCP.
Corollary 2.17. Let be subdomains of a field B such that . An has ACCP if and only if has ACCP.
Next Lemmas coming from Kim [8] are results about ACCP properties in monoid domains.
Lemma 2.18. Let be an extension of torsion-free cancellative monoids. If satisfies ACCP and , then satisfies the ACCP.
Proof. [8] Proposition 1.2. (1).
Lemma 2.19. Let D be an integral domain, S a torsion-free cancellative additive monoid, and the monoid domain. If satisfies ACCP, then D and S satisfy ACCP.
Proof. [8], Proposition 1.5.
Next Theorem is the answer about question from Kim [8] Question 1.6. In [8] Proposition 1.5 (1) we have an implication. Kim asked that are the sufficient conditions in [8] Proposition 1.5 (1) for the monoid domain to satisfy ACCP, necessary.
Theorem 2.20. Let A be an integral domain and B be a field such that and . Let S be a torsion-free cancellative monoid. Both A and satisfy ACCP if and only if satisfies ACCP.
Proof. ( ) The proof is similar to [8], Proposition 1.5.
From Lemma 2.19, since has ACCP, then has ACCP. Now, consider such that . Without loss of generality, we can assume that because every ACCP-domain is atomic. Since , so . By assumption has ACCP, so there exists such that . We get in which is stationary.
Recall that each ACCP-domain is atomic. Hence, all previous results about the ACCP-domains hold for the atomic domains. We complete the knowledge about the atomicity condition in monoid domains.
Lemma 2.21. Let D be an integral domain, S a torsion-free cancellative monoid, and the monoid domain. If be atomic, then D and S be atomic.
Proof. [8], Proposition 1.4.
Next Theorem is similarly to 2.20.
Theorem 2.22. Let A be an integral domain and B be a field such that with . Let S be a torsion-free cancellative monoid. Both A and be atomic if and only if be atomic.
Proof. ( ) Since B[S] be atomic, then consider , where . Hence from assumption we have . Then A[S] is atomic.
From Lemma 2.21 since be atomic, then and be atomic. Now consider , where , because be atomic. Then , hence be atomic.
Anderson, Anderson and Zafrullah asked in [1](Question 1) is atomic when is atomic. I say no. I have no example but we can deduce from well known facts:
Suppose that is not atomic. We want to get R is not atomic. Since is not atomic then has no ACCP. Hence R has no ACCP which it does not imply R is not atomic because there exists an example atomic domain which is not ACCP.
Converse, if R is not atomic, then R has no ACCP. Hence has no ACCP which it does not imply is atomic.
In [13] we have another results about polynomial composites. Various properties have been investigated: BFD (bounded factorization domain), HFD (half factorial domain), idf (each nonzero element of domain has at most a finite number of nonassociate irreducible divisors), FFD (finite factorization domain), S-domain (for each height-one prime ideal P of domain, height of is equal to 1 in polynomial ring over domain), Hilbert ring (every prime ideal of domain is an intersection of maximal ideals of that domain).
Theorem 2.23 says that, under some assumption, a polynomial composite has the structure of Dedekind rings. Dedekind rings are a very important class of rings in algebra. There are a lot of work, the results associated with it. On the basis of the Dedekind structure, I developed cryptosystems with the Dedekind structure in Sections 6 and 7.
Theorem 2.23. Let be a finite fields extension. Then be a Dedekind domain.
Proof. By [2], Theorem 2.7 every nonzero prime ideal is a maximal. By [13] Proposition 3.1 we have is integrally closed. By Theorem 3.2 [14] is noetherian domain. Hence be a Dedekind domain.
In the following Proposition, we provide the most important and fundamental facts about the structure of Dedekind.
Proposition 2.24. Let be an extension fields and let .
(a) If be a nonzero prime ideal of and , then .
(b) Every nonzero ideal of has an unambiguous representation in the form product of prime ideals.
(c) Every nonzero ideal of is invertible.
(d) If is an ideal of , then is a principal ideal domain.
(e) (a group of class of invertible ideals) be isomorphic to (a group of class of invertible modules).
(f) If M be a finite generated torsion-free T-module, then , where are nonzero ideals of T and k is a range of M. Moreover
Ref (g) If be a finite generated -module, then
where , , I is unambiguously, with the accuracy to isomorphism, a designated ideal, are nonzero prime ideals of T, , and a finite set of pair is designated unambiguously.
III. RELATIONSHIPS BETWEEN POLYNOMIAL COMPOSITES AND CERTAIN TYPES OF FIELDS EXTENSIONS
Let be a fields extension. Let's build a polynomial composites . In this section, we will answer the question of whether there are relationships between field extensions and polynomial composites.
All my considerations began with the Theorem 3.1 below. This Proposition motivated me to further consider polynomial composites in a situation where the extension of fields is algebraic, separable, normal and Galois, respectively.
Theorem 3.1. Let be a field extension. Put . Then is Noetherian if and only if .
Proof. ( ) Since XL[X] is a finitely generated ideal of , it follows from [14] Lemma 3.1 that . Thus, L[X] is module-finite over the Noetherian ring .
is Noetherian ring and module-finite over the subring . This is the situation covered by P.M. Eakin's Theorem [6].
Every Propositions and Theorems of this section we can find in [14].
Proposition 3.2. Let be a fields extension such that . Put . is Noetherian if and only if be an algebraic extension.
Proposition 3.3. Let be fields extension such that be a perfect field and assume that any -isomorphism , where holds for every field such that . Put . be a Noetherian if and only if be a separable extension.
Proposition 3.4. Let be fields extension. Assume that if a map is -embedding, then . Put . be a Noetherian if and only if be a normal extension.
Proposition 3.5. Let be fields extension such that . Put . be a Noetherian if and only if be a normal extension.
Proposition 3.6. Let be Noetherian, where be fields. Assume and any -isomorphism , where holds for every field such that . be a Noetherian if and only if be a Galois extension.
Proposition 3.7. Let , where be fields such that . be a Noetherian if and only if be a Galois extension.
Proposition 3.8. Let be fields such that be a perfect field. If and be Noetherian then be separable fields extension.
Moreover, if we assume that any -isomorphism , where holds for every field such that , then be a Noetherian.
Proposition 3.9. Let be fields such that . If be Noetherian then be a normal fields extension. Moreover, be Noetherian.
Proposition 3.10. Let be extension fields such that . Then be Noetherian. Moreover, if , then be a normal.
Theorem 3.11 ([9], Theorem 1.2.). Let be an algebraically closed field algebraic over , and let such that be an intermediate field. Then the following are equivalent:
(a) is separable over .
(b) has no nonzero nilpotent elements.
(c) Every element of is a unit times an idempotent.
(d) As an -algebra is generated by idempotents.
Theorem 3.12 ([9], Theorem 1.3.). Let M be an algebraically closed field containing K, and let L be a field algebraic over K. Then the following are equivalent:
(a) is separable over .
(b) has no nonzero nilpotent elements.
(c) Every element of is a unit times an idempotent.
(d) As an -algebra is generated by idempotents.
Below we have conclusions from the above results.
Theorem 3.13. In Theorems 3.11 and 3.12, if we assume, then conditions (a) - (d) are equivalent.
(e) be a Noetherian.
(f)
(g) be an algebraic extension.
(h) be a Galois extension.
Proof. (h) (a) - Obvious.
(a) (g) (e) (h) If be a separable extension, then be an algebraic extension. By Proposition 3.2 be a Noetherian. By Proposition 3.7 be a Galois extension.
(e)⇒(f) - Theorem 3.1.
Theorem 3.14. In Theorem 3.13 if assume be a perfect field and , then conditions (a) - (h) are equivalent to (g) be a normal extension.
Proof. (g)⇒(a) If be a normal extension, then be an algebraic extension. By definition perfect field be a separable extension.
(h)⇒(g) Obvious.
Proposition 3.7, Theorems 3.13 and 3.14 can be used to solve the inverse Galois problem. The inverse Galois problem concerns whether or not every finite group appears as the Galois group of some Galois extension of the rational numbers Q. This problem, first posed in the early 19th century, is unsolved.
There is a lot of work. And it is enough to solve the problem for non-abelian groups. Thus, the following question arises:
Question:
Can all the statements of this sections operate in noncommutative structures?
And another question also arises regarding polynomial composites:
Question:
Under certain assumptions for any type of , we get that be a Noetherian ring. When can be isomorphic to any Noetherian ring?
IV. GENERALIZED RSA CIPHER
In [12] we have an information about how can we make a finite alphabet to an infinite alphabet?
We can assign an appropriate number to each letter of the alphabet: A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7, I = 8, J = 9, K = 10, L = 11, M = 12, N = 13, O = 14, P = 15, Q = 16, R = 17, S = 18, T = 19, U = 20, V = 21, W = 22, X = 23, Y = 24, Z = 25. So the alphabet is a finite set. The opposite side can easily decipher using the length of the alphabet. What if we extend this alphabet to an infinite set? In this situation, we can stay with the alphabet, but extend the length to infinity. So we have , , , , , , where . So, for example, the text ABACAB can be converted to 0 1 0 2 0 1, but also to 0 1 26 54 26 53. And we can give this number sequence to encrypt.
a) Generating keys
Let's choose distinct prime ideals and ( are distinct primes) such that such that , where is the length of the alphabet.
Ref
Let's choose the ideal such that and are relatively primes and .
We find the ideal such that .
The public key is defined as the pair of ideals , while the private key is the pair .
b) Encryption and decryption
We encrypt the message by calculation
The encrypted message is decrypted by formula
From [12] recall a generalized Diffie-Hellman key exchange.
First person F and second person S agree on the prime ideals and in such that .
Person F chooses any secret in and sends to person S
Person S chooses any secret (b) in and sends to person F
Person F compute .
Person S compute .
Person F and person S share a secret ideal (s). This is because
Ref
VI. A Key that is a Fractional Ideal
In section 6 and 7 we have cryptosystems that use the Dedekind structure ([15] in cooperation with M. Jankowska). My goal was not to create an entire cryptosystem based on the Dedekind structure. The first cryptosystem has a Dedekind structure in the key. The second cryptosystem has a Dedekind structure in two different alphabets. It is essential. This increases the security of our data. First of all, we use the fractional ideal structure. The definition itself is very interesting and motivated to apply.
Let A = {a_0, a_1, \ldots, a_n} be an alphabet such that |A| be a prime number. Let x \in {2, 3, \ldots, |A|} be the value of one of the letters of the alphabet, k \geqslant 2 be an key. Then
where y be the value of one of the letters of the alphabet be an encrypted letter.
Now, assume we have encrypted letter y. Then we get a decrypted letter x by a formula
where d be the remainder of dividing y by k.
Proof.
As proposed in [12](Introduction of section 3), this cipher can be generalized to a complete algebraic structure. It is enough to adopt the infinite alphabet as in [12], be transformed into the principal ideal , be transformed into the principal ideal , into the principal ideal . This way we get algebraic encryption where the key be the fractional ideal in the Dedekind's ring, in this case .
VII. THE ALPHABET AS A FRACTIONAL IDEAL
Let be a set of characters. Assume is equal to any prime number. Secretly establish a second alphabet such that with a prime length.
Let be a message, we want to encrypt.
A secret short alphabet divides a large public alphabet into zones. We skip the extra characters such that 0, 1. So we have a clean alphabet from 2. Let's move one over, so we have 1. Suppose , . We have zones. Zero zone, includes the alphabet from 1 to . The first zone, i.e. the alphabet from to and so on. The last zone includes the alphabet from to .
Let's extend the message values with random numbers informing us about a given zone of a given letter (this information denote by ):
Notes
Denote by k the key. Multiply each value of the message (not the information about the zone) by k and use the modulo q.
Hence ciphertext is:
where be a encrypted message.
Now let's decode the message.
by dividing it into blocks (each block contains a zone and a message).
Let's apply the formula:
where is the decoded letter, encrypted letter, is a number satisfies a congruence , be the key, be a zone.
Of course, this cryptosystem can also be easily generalized by turning individual elements into ideals.
VIII. APPLICATIONS OF POLYNOMIAL COMPOSITES IN CRYPTOLOGY
Finally, we will show cryptosystems based on polynomial composites and monoid domains.
Lemma 8.1. Let , , where for and for . Then
Put ( ) be different encryption systems. Then we have and are composition of encryption systems. No consider .
To improve security, let's fix that , , where . And such , Alice and Bob agree before the message is sent.
Alice and Bob multiply these composites to form one. We have .
Note that the sum and product of the encryption systems must be defined in the formula above. Definitions we leave Alice and Bob. But in this section we can put and . We can define the product and the sum of cryptosystems completely differently.
So in the product we encrypt the letter as two letters, the first in the first system and the second in the second system. And in the sum we encrypt the letter using the first system and then the second system. Of course, we can define completely different, at our discretion.
Assume that degree of fg is m and text to encrypt consists of more letters then . Then we divide the text into blocks of length . We can assume that encrypts the first letter of each block. Expression at X of fg encrypts the second letter of each block, and expression at of fg encrypts the third letter and so on.
Now, let's see how to decrypt in this idea.
Assume that we have an encrypted message . If our key is degree m, then we divide message on partition. And every partion divide to two. Every two letters are one letter of message.
Earlier we define and . Then decryption of two letters ( ) are (one letter) and (one letter).
The use of many cryptosystems in various configurations in a polynomial composite increases our security. The security here lies in the fact that the encrypted message is resistant to breaking under many cryptanalyst criteria.
It is very easy to decrypt the message when you know the key.
IX. APPLICATIONS OF MONOID DOMAINS IN CRYPTOLOGY
Any alphabet of characters creates a finite set. Most ciphers are based on finite sets. But we can have the idea of using the infinite alphabet A, although in reality they can be cyclical sets with an index that would mean a given cycle. For example, , , , , , , , where , , for . We see that this is isomorphic to a monoid non-negative integers by a formula
Then we can use a monoid domain by a map
We want to encrypt the message (the letters transform to numbers by a function ). We establish the secret key X. Let F be a field. We determine any coefficients from this field: . Then the message be transformed into a polynomial of the form:
We compute for : ( must be prime) and then we have a decrypt message .
Notes To decrypt it we need to use a formula (for ):
Proof.