怎么求本原元

求本原元的方法有以下几种：

暴力搜索法

从2开始逐个判断数字是否为本原根。

对于给定的模数n，本原根g满足g的取值范围是[2, n-1]，且g的所有幂次mod n都不等于1，直到找到第一个满足条件的g为止。

费马定理

对于给定的模数n，如果n是一个素数，那么任意一个与n互质的数a，a的φ（n）次方mod n等于1，其中φ（n）表示小于n且与n互质的正整数的个数。

可以选择一个与n互质的数a，不断计算a的幂次mod n，直到得到1为止，这个幂次即为本原根。

欧拉定理

对于给定的模数n，如果n是一个素数，那么任意一个与n互质的数a，a的φ（n）/k次方mod n不等于1，其中k是n的所有素因子。

可以选择一个与n互质的数a，计算a的幂次mod n的结果，并判断是否等于1，如果不等于1，则继续计算a的幂次mod n的结果，直到得到1为止，这个幂次即为本原根。

高斯算法

在比较大的域中，需要一个系统的方法来寻找本原元。

高斯算法的基本步骤如下：

设i=1，取域F中的任意一个非零元，且记为a。

若a的阶等于q-1，则a即为所寻找的本原元，算法停止。

否则，在域F中选一个不是a的幂次的非零元b，若b的阶等于q-1，则令a=b，算法停止。

否则，寻找a的一个因子d和b的一个因子e，使得de ≡ 1 （mod n），然后令a = a^e，返回第二步。

这些方法中，暴力搜索法适用于小规模模数，费马定理和欧拉定理适用于素数模数，而高斯算法适用于较大规模的有限域。根据具体问题的需求选择合适的方法可以更高效地求出本原元。