原根(扩展欧几里得的应用)

在一个模的既约剩余系中，如果一个元素的指数恰好等于m)(mφ，则这个元素即为模 的一个原根．在存在原根的既约剩余系中，每个元素均可以表示成原根的幂，反过来原根的幂 所表示的所有不同的元素恰好构成既约剩余系，这就给出了一种构造模m的既约剩余系的很自 然的一种方法．但只有时才有原根，对于不存在原根的模，它的既约 剩余系是怎样构造的呢？以上所描述的结论与问题正是本章所要研究的主要内容．另外，本章 还介绍指数、指标两个主要概念及性质，其中指标为密码学中的离散对数问题．离散对数问题 是设计许多公钥密码算法的重要理论根据．