Departmental Bulletin Paper 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$

Suzuki, Hideo  ,  スズキ, ヒデオ  ,  Hideo, Suzuki

19 ( 1 )  , pp.41 - 47 , 2015-09-30
NCID:AA11155514
Description
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.
Full-Text

https://tuis.repo.nii.ac.jp/?action=repository_action_common_download&item_id=543&item_no=1&attribute_id=18&file_no=1

Number of accesses :  

Other information