Properties of Primes and Multiplicative Group of a Field

Kenichi Arai; Hiroyuki Okazaki

Formalized Mathematics (2009)

  • Volume: 17, Issue: 2, page 151-155
  • ISSN: 1426-2630

Abstract

top
In the [16] has been proven that the multiplicative group Z/pZ* is a cyclic group. Likewise, finite subgroup of the multiplicative group of a field is a cyclic group. However, finite subgroup of the multiplicative group of a field being a cyclic group has not yet been proven. Therefore, it is of importance to prove that finite subgroup of the multiplicative group of a field is a cyclic group.Meanwhile, in cryptographic system like RSA, in which security basis depends upon the difficulty of factorization of given numbers into prime factors, it is important to employ integers that are difficult to be factorized into prime factors. If both p and 2p + 1 are prime numbers, we call p as Sophie Germain prime, and 2p + 1 as safe prime. It is known that the product of two safe primes is a composite number that is difficult for some factoring algorithms to factorize into prime factors. In addition, safe primes are also important in cryptography system because of their use in discrete logarithm based techniques like Diffie-Hellman key exchange. If p is a safe prime, the multiplicative group of numbers modulo p has a subgroup of large prime order. However, no definitions have not been established yet with the safe prime and Sophie Germain prime. So it is important to give definitions of the Sophie Germain prime and safe prime.In this article, we prove finite subgroup of the multiplicative group of a field is a cyclic group, and, further, define the safe prime and Sophie Germain prime, and prove several facts about them. In addition, we define Mersenne number (Mn), and some facts about Mersenne numbers and prime numbers are proven.

How to cite

top

Kenichi Arai, and Hiroyuki Okazaki. "Properties of Primes and Multiplicative Group of a Field." Formalized Mathematics 17.2 (2009): 151-155. <http://eudml.org/doc/267044>.

@article{KenichiArai2009,
abstract = {In the [16] has been proven that the multiplicative group Z/pZ* is a cyclic group. Likewise, finite subgroup of the multiplicative group of a field is a cyclic group. However, finite subgroup of the multiplicative group of a field being a cyclic group has not yet been proven. Therefore, it is of importance to prove that finite subgroup of the multiplicative group of a field is a cyclic group.Meanwhile, in cryptographic system like RSA, in which security basis depends upon the difficulty of factorization of given numbers into prime factors, it is important to employ integers that are difficult to be factorized into prime factors. If both p and 2p + 1 are prime numbers, we call p as Sophie Germain prime, and 2p + 1 as safe prime. It is known that the product of two safe primes is a composite number that is difficult for some factoring algorithms to factorize into prime factors. In addition, safe primes are also important in cryptography system because of their use in discrete logarithm based techniques like Diffie-Hellman key exchange. If p is a safe prime, the multiplicative group of numbers modulo p has a subgroup of large prime order. However, no definitions have not been established yet with the safe prime and Sophie Germain prime. So it is important to give definitions of the Sophie Germain prime and safe prime.In this article, we prove finite subgroup of the multiplicative group of a field is a cyclic group, and, further, define the safe prime and Sophie Germain prime, and prove several facts about them. In addition, we define Mersenne number (Mn), and some facts about Mersenne numbers and prime numbers are proven.},
author = {Kenichi Arai, Hiroyuki Okazaki},
journal = {Formalized Mathematics},
language = {eng},
number = {2},
pages = {151-155},
title = {Properties of Primes and Multiplicative Group of a Field},
url = {http://eudml.org/doc/267044},
volume = {17},
year = {2009},
}

TY - JOUR
AU - Kenichi Arai
AU - Hiroyuki Okazaki
TI - Properties of Primes and Multiplicative Group of a Field
JO - Formalized Mathematics
PY - 2009
VL - 17
IS - 2
SP - 151
EP - 155
AB - In the [16] has been proven that the multiplicative group Z/pZ* is a cyclic group. Likewise, finite subgroup of the multiplicative group of a field is a cyclic group. However, finite subgroup of the multiplicative group of a field being a cyclic group has not yet been proven. Therefore, it is of importance to prove that finite subgroup of the multiplicative group of a field is a cyclic group.Meanwhile, in cryptographic system like RSA, in which security basis depends upon the difficulty of factorization of given numbers into prime factors, it is important to employ integers that are difficult to be factorized into prime factors. If both p and 2p + 1 are prime numbers, we call p as Sophie Germain prime, and 2p + 1 as safe prime. It is known that the product of two safe primes is a composite number that is difficult for some factoring algorithms to factorize into prime factors. In addition, safe primes are also important in cryptography system because of their use in discrete logarithm based techniques like Diffie-Hellman key exchange. If p is a safe prime, the multiplicative group of numbers modulo p has a subgroup of large prime order. However, no definitions have not been established yet with the safe prime and Sophie Germain prime. So it is important to give definitions of the Sophie Germain prime and safe prime.In this article, we prove finite subgroup of the multiplicative group of a field is a cyclic group, and, further, define the safe prime and Sophie Germain prime, and prove several facts about them. In addition, we define Mersenne number (Mn), and some facts about Mersenne numbers and prime numbers are proven.
LA - eng
UR - http://eudml.org/doc/267044
ER -

References

top
  1. [1] Broderick Arneson and Piotr Rudnicki. Primitive roots of unity and cyclotomic polynomials. Formalized Mathematics, 12(1):59-67, 2004. 
  2. [2] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990. 
  3. [3] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990. Zbl06213858
  4. [4] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  5. [5] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. Formalized Mathematics, 5(4):485-492, 1996. 
  6. [6] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  7. [7] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  8. [8] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990. 
  9. [9] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  10. [10] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990. 
  11. [11] Yoshinori Fujisawa and Yasushi Fuwa. The Euler's function. Formalized Mathematics, 6(4):549-551, 1997. 
  12. [12] Eugeniusz Kusak, Wojciech Leończuk, and Michał Muzalewski. Abelian groups, fields and vector spaces. Formalized Mathematics, 1(2):335-342, 1990. 
  13. [13] Rafał Kwiatek. Factorial and Newton coefficients. Formalized Mathematics, 1(5):887-890, 1990. 
  14. [14] Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relative primes. Formalized Mathematics, 1(5):829-832, 1990. 
  15. [15] Michał Muzalewski and Lesław W. Szczerba. Construction of finite sequences over ring and left-, right-, and bi-modules over a ring. Formalized Mathematics, 2(1):97-104, 1991. 
  16. [16] Hiroyuki Okazaki and Yasunari Shidama. Uniqueness of factoring an integer and multiplicative group R/pZ*. Formalized Mathematics, 16(2):103-107, 2008, doi:10.2478/v10037-008-0015-1.[Crossref] 
  17. [17] Christoph Schwarzweller. The ring of integers, euclidean rings and modulo integers. Formalized Mathematics, 8(1):29-34, 1999. 
  18. [18] Dariusz Surowik. Cyclic groups and some of their properties - part I. Formalized Mathematics, 2(5):623-627, 1991. 
  19. [19] Andrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1):115-122, 1990. 
  20. [20] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990. 
  21. [21] Wojciech A. Trybulec. Groups. Formalized Mathematics, 1(5):821-827, 1990. 
  22. [22] Wojciech A. Trybulec. Subgroup and cosets of subgroups. Formalized Mathematics, 1(5):855-864, 1990. 
  23. [23] Wojciech A. Trybulec. Lattice of subgroups of a group. Frattini subgroup. Formalized Mathematics, 2(1):41-47, 1991. 
  24. [24] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  25. [25] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.