# On the Reduced Testing of a Primitive Element in ${\\mathbb Z}_n^\\times$On the Reduced Testing of a Primitive Element in ${\\mathbb Z}_n^\\times$On the Reduced Testing of a Primitive Element in ${\mathbb Z}_n^\times$

19 ( 1 )  , pp.41 - 47 , 2015-09-30
NII書誌ID(NCID):AA11155514

The primitive roots in ${\mathbb Z}_n^\times$ are defined and exist iff $n = 2, 4, p^{\alpha}, 2p^{\alpha}$. Knuth gave the definition of the primitive roots in ${\mathbb Z}_{p^\alpha}^\times$, and showed the necessary and sufficient condition for testing a primitive root in ${\mathbb Z}_{p^\alpha}^\times$. In this paper we define the primitive elements in ${\mathbb Z}_n^\times$, which is a generalization of primitive roots, as elements that take the maximum multiplicative order.And we give two theorems for the reduced testing of a primitive element in ${\mathbb Z}_n^\times$ for any composite $n$. It is shown that the two theorems, using a technique of a lemma, for testing a primitive element allow us an effective reduction in testing processes and in computing time cost as a consequence.
The primitive roots in ${\mathbb Z}_n^\times$ are defined and exist iff $n = 2, 4, p^{\alpha}, 2p^{\alpha}$. Knuth gave the definition of the primitive roots in ${\mathbb Z}_{p^\alpha}^\times$, and showed the necessary and sufficient condition for testing a primitive root in ${\mathbb Z}_{p^\alpha}^\times$. In this paper we define the primitive elements in ${\mathbb Z}_n^\times$, which is a generalization of primitive roots, as elements that take the maximum multiplicative order.And we give two theorems for the reduced testing of a primitive element in ${\mathbb Z}_n^\times$ for any composite $n$. It is shown that the two theorems, using a technique of a lemma, for testing a primitive element allow us an effective reduction in testing processes and in computing time cost as a consequence.

このアイテムのアクセス数：  回

 その他の情報