###RSA 学习记录:

###RSA 学习记录:

___________________________________________________________________________________________________________________________________________看[0xDktb]大佬的blog学习路程:

url:https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/

一.2020/12/19

①:绪论:

​ 首先取得值phi(n)=(p-1)*(q-1)中 — p!=q,且若有一个取为 2 则phi(n)必定为偶数,同时若没有一个是取为2时 phi(n)=偶数*偶数 也必然偶数, 而根据(e*d)mod(phi(n))==1可得出,(d*e-1)=k 同时,k mod (phi(n))==0,则k必然为偶数

​ 其次是对 其原理的翻译:
1. 取 一 个 k = d ∗ e − 1 1.取一个k=d*e-1 1.k=de1

2. 选 择 一 个 小 素 数 g = 2 开 始 2.选择一个小素数g=2开始 2.g=2

3. 然 后 判 断 k 是 否 为 偶 数 , 原 因 在 首 先 里 面 , 若 为 偶 数 k = k / / 2 , 然 后 x = g k m o d n 3.然后判断k是否为偶数,原因在首先里面,若为偶数 k=k//2,然后x=g^k\ mod\ n 3.kk=k//2,x=gk mod n

4. p = g c d ( x − 1 , n ) m o d n 如 果 p > 1 则 成 立 算 出 了 p , q = n / / p 4.p=gcd(x-1,n)\ mod\ n 如果p>1则成立算出了p,q=n//p 4.p=gcd(x1,n) mod np>1pq=n//p

否 则 , 若 算 出 的 p < = 1 , 就 要 重 新 循 环 步 骤 3 , 若 k 变 为 奇 数 了 之 后 则 就 会 退 出 这 层 次 的 循 环 重 新 开 始 循 环 否则,若算出的p<=1,就要重新循环步骤3,若k变为奇数了之后则就会退出这层次的循环重新开始循环 p<=1,3k退

并 且 取 得 的 g 为 下 一 个 素 数 的 值 , k 重 新 变 成 了 一 开 始 那 个 k 继 续 进 行 重 复 顺 序 进 行 操 作 直 到 使 得 p > 1 输 出 并且取得的g为下一个素数的值,k重新变成了一开始那个k继续进行重复顺序进行操作直到使得p>1输出 gkk使p>1

​ 然后就是对于他的python脚本的函数的复现了:

from gmpy2 import next_prime, gcddef Factorize(n, e, d):g = 2while True:k = e * d - 1.//k=Z*phi(n) Z为一个整数while not k & 1:k //= 2p = int(gcd(pow(g, k, n) - 1, n)) % n // p=int(gcd(pow(g,t*(p-1)*(q-1))-1,n))%nif p > 1:return (p, n // p)g = int(next_prime(g))

接下来重点来了!!! shallow 的讲解:他是用最小公倍数 用2 用g^(p-1)-1 但找不到 去找他的倍数 就是phi(n) 但是有问题, %q后变成0
找值 x=g^k x%p==1但是x%q!=1 k用ed-1去找 再去百度:“数论阶” “二次剩余”

***②:二次剩余:

二次剩余是数论基本概念之一。它是初等数论中非常重要的结果,不仅可用来判断二次同余式是否有解,还有很多用途。C.F.高斯称它为算术中的宝石,他一人先后给出多个证明。 [1]

研究二次剩余的理论称为二次剩余理论。二次剩余理论在实际上有广泛的应用,包括从噪音工程学到密码学以及大数分解。 [2]

——————————定义:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pkCItZYP-1608436422073)(https://bkimg.cdn.bcebos.com/formula/e8568e6b789887b42fe84e15e6e3f1ff.svg)] 在数论中,特别在同余理论里,一个整数X对另一个整数p的

二次剩余(英语:Quadratic residue)指X的平方除以p得到的余数。

当存在某个X,式子[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q5goaSH5-1608436422074)(https://bkimg.cdn.bcebos.com/formula/d17269045494b7b0b40db02c214055a2.svg)]成立时,称**“d是模p的二次剩余”**

当对任意不成立时,称**“ d是模 p的二次非剩余”**

——————————基本结论:
1.质数二次剩余

对于质数2,每个整数都是它的二次剩余。 以下讨论p是奇质数的情况:

对于X,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5PHOxHqu-1608436422076)(https://bkimg.cdn.bcebos.com/formula/d17269045494b7b0b40db02c214055a2.svg)]而言,能满足“d是模 p的二次剩余”的 d共有

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZOr1FLkM-1608436422077)(https://bkimg.cdn.bcebos.com/formula/725225ce2c117d88b0685518f36dc79c.svg)]个(剩余类),分别为:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FaRB7tQy-1608436422078)(https://bkimg.cdn.bcebos.com/formula/967b90967043ee461c1a345ae8d2c6e7.svg)](0计算在内)此外是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I7INt2q2-1608436422079)(https://bkimg.cdn.bcebos.com/formula/4d5d2cd8c4d3e67be5f30a7c1445457d.svg)]个二次非剩余。但在很多情况下,我们只考虑乘法群Z/*p*Z,因此不将0包括在内。这样,每个二次剩余的乘法逆元仍然是二次剩余;二次非剩余的乘法逆元仍然是二次非剩余。二次剩余的个数与二次非剩余的个数相等,都是。此外,两个二次非剩余的乘积是二次剩余,二次剩余和二次非剩余的乘积是二次非剩余。

应用二次互反律可以知道,当p模4余1时,-1是p的二次剩余;如果p模4余3,那么,-1是p的二次非剩余。要知道d是否为模p的二次剩余,可以运用欧拉判别法(或叫欧拉准则)。

—————>>>欧拉准则<<<:

叙述::

​ 若p是奇质数且p不能整除d,则:

​ d是模p的二次剩馀当且仅当:

​ d是模p的非二次剩馀当且仅当:

​ 以勒让德符号表示,即为: (d/p)=1

例子一:对于给定数,寻找其为二次剩余的模数

​ 令a = 17。对于怎样的质数p,17是模p的二次剩余呢?

​ 根据判别法里给出的准则,我们可以从小的质数开始检验。

​ 首先测试p = 3。我们有:17^((3 − 1)/2) = 17^1 ≡ 2 (mod 3) ≡ -1 (mod 3),因此17不是模3的二次剩余。

​ 再来测试p = 13。我们有:17^((13 − 1)/2) = 17^6 ≡ 1 (mod 13),因此17是模13的二次剩余。实际上我们有:17 ≡ 4 (mod 13),而2^2 = 4.

​ 运用同余性质和勒让德符号可以加快检验速度。继续算下去,可以得到:

​ 对于质数p =,(17/p) = +1(也就是说17是模这些质数的二次剩余)。

​ 对于质数p =,(17/p) = -1(也就是说17是模这些质数的二次非剩余)。

例子二:对指定的质数p,寻找其二次剩余

​ 哪些数是模17的二次剩余?

​ 我们可以手工计算:

​ 1^2 = 1 2^2 = 4 3^2 = 9 4^2 = 16 5^2 = 25 ≡ 8 (mod 17) 6^2 = 36 ≡ 2 (mod 17)

​ 7^2 = 49 ≡ 15(mod 17) 8^2 = 6^4 ≡ 13 (mod 17)

​ 于是得到:所有模17的二次剩余的集合是1,2,4,8,9,13,15,16。要注意的是我们只需要算到8,因为9=17-8,9的平方与8的平方模17是同余的:9^2 = (−8)^2 = 8^2 ≡ 13 (mod 17).(同理不需计算比9大的数)。

​ 但是对于验证一个数是不是模17的二次剩余,就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余,只需要计算3^((17 − 1)/2) = 3^8 ≡ 81^2 ≡ − 4^2 ≡ − 1 (mod 17),然后由欧拉准则判定3不是模17的二次剩余。

​ 欧拉准则与高斯引理以及二次互反律有关,并且在定义欧拉-雅可比伪素数(见伪素数)时会用到。

2.质数乘方

每个奇数的平方都模8余1,因此模4也余1。设a是一个奇数。m为8,16或2的更高次方,那么a是关于m的二次剩余当且仅当a≡ 1(mod 8)。

比如说,在模32时,所有的奇数的平方分别是:

  • 1≡ 15 ≡ 1
  • 3≡ 13 ≡ 9
  • 5≡ 11 ≡ 25
  • 7≡ 9 ≡ 17

模8都余1。而偶数的二次剩余是:

  • 0≡ 8≡ 16 ≡ 0
  • 2≡ 6≡ 10≡ 14 ≡ 4
  • 4≡ 12≡ 16 ≡ 16

可以看出,关于8,16或2的更高次方的二次剩余是具有4(8n+ 1)形式的所有数,其中k、n为整数。

对于奇质数p以及与p互质的整数A,A是关于p的若干次乘方的剩余当且仅当它是关于p的剩余。

设模的是p(n次乘方),

  • 那么p**A

    • kn时是模p的剩余;
    • k<n并为奇数时是模p的非剩余。

k<n并为偶数时,

  • 如果A是关于p的剩余,那么p**A就是模p的剩余;
  • 如果A是关于p的非剩余,那么p**A就是模p的非剩余。
3.合数二次剩余

首先可以看出, [3]

  • 如果a是模n的剩余,并且p整除n,那么a是模p的剩余。
  • 如果a是模n的非剩余,那么存在p整除n,使得a是模p的非剩余。

对于模合数的情况,两个剩余的乘积仍然是剩余,剩余和非剩余的乘积必为非剩余,但是两个非剩余的乘积则可能是剩余、非剩余或0。

比如,对于模15的情况
  1, 2, 3,4, 5,6, 7, 8,9,10, 11, 12, 13, 14(粗斜体为二次剩余)。
 两个二次非剩余2和8的乘积是二次剩余1,但另外两个二次非剩余2和7的乘积是二次非剩余14。

③:数论阶:

对于(a,n)=1的整数,满足a^r≡1 (mod n ) 的最小整数r,称为a模n的阶。

——————————定义:

设n>1,a是满足(a,n)=1的整数,则必有一个r(1≤r≤n-1)使得a^r≡1 (mod n )

满足a^r≡1 (mod n ) 的最小整数r,称为a模n的阶。

——————————性质:

(1)设gcd(a,n)=1 ,a模n的阶为r. 若正整数N使得a^N≡1(mod n ), 则 r∣N

(2)设gcd(a,n)=1, 则a模n的阶r整除ψ(n).特别的,若n是素数p, 则a模p的阶整除p-1.(费马定理)

存在性

设m≥2(可推广至m≥1),gcd(a,m)=1,则存在正整数d≤m-1(m=1例外),使得ad≡1(mod m)

:∵m≥2,gcd(m,a)=1, ∴m不整除a。

又∵gcd(m,a)=1∴m不整除aj,j≥1∴存在唯一一对整数qj与 rj,满足:aj=qj*m+rj,r^j∈(0,m)

∴m个余数r0,r1,……,rm-1仅可能取m-1个值,∴其中必有两个相等,设为ri=rk,0≤i

∴m(qk -qi)= ak–ai= ai(ak-i-1)又∵(m,a)=1,∴m∣ak-i-1∴取d=k-i,有ad≡1(mod m)

定义:设m≥1,gcd(a,m)=1(或存在x0和y0,使得ax0+my0=1),d0是满足a^d≡1(mod m)的最小正整数d,记d0为δ+m(a)(简记为δm(a)),称为a对模m的指数(阶)。对给定的模m,d0=δ+m(a)是由a唯一确定的,是a的函数,用于刻画与m既约的a关于模m的性质。

性质1.:a^d≡1(mod m),d≥1,充要条件是d0=δ+m(a)∣d ,即d≡0(modδ+m(a))。

充分性显然

证必要性:∵d0与d是整数,∴存在唯一一对整数q与 r,满足:d=qd0+r, 0≤r

∴a^d -1=a^(qd0+r)- a^r +a^r-1= ar(a^qd0 - 1)+(a^r-1)。

又∵m∣ad-1,m∣aqd0-1,∴m∣a^r-1。又∵d0的最小性,0≤r

证完。

性质3.:

设gcd(a,m)=1,那么d0=δ+m(a),充要条件是a^d0≡1(mod m),a0(=1),a1(=a),……,a^(d0-1)这δ+m(a)个数对模m两两不同余。

证必要性:∵d0=δ+m(a),∴a^d0≡1(mod m)。设存在i,j,0≤ij≡ai(mod m)。

∵(ai,m)=1,∴a(j-i)≡1(mod m)。但1≤j-i

∴a0,a1,……,a^(d0-1)这d0个数对模m两两不同余。

证充分性:∵a0,a1,……,a(d0-1)对模m两两不同余,∴aj与a^0(=1)关于模m不同余,1≤j< d0

又∵a^d0≡1(mod m),∴d0=δ+m(a)。

证完。

定义

当δ+m(a)=φ(m)时,称a是模m的原根,简称m的原根。

性质4.:

设(a,m)=1,a是模m的原根,即d0=φ(m),充要条件是a0(=1),a1(=a),……, a^φ(m)-1(证= a^(d0-1))这φ(m)个数为模m的一组既约剩余系。

证必要性:

∵(a,m)=1,∴a0,a1,……, a^(φ(m)-1)(= a^(d0-1))均和m既约。

又∵a0,a1,……, a^(φ(m)-1)(= a^(d0-1))对模m两两不同余,共φ(m)个数,

∴a0,a1,……, a^(φ(m)-1)(= ad^(0-1))为模m的一组既约剩余系。

证充分性:

欧拉定理a^φ(m)≡1(mod m)推出。证完。

补充

性质1.:若b≡a(mod m),(a,m)=1,则δ+m(a)=δ+m(b)。

性质2.:δ+2l(a)∣2l-2,l≥3。

性质3.:若(a,m)=1,ak≡ah(mod m),则k≡h(modδ+m(a))。

性质4.:设a-1是a对模m的逆,即(a-1)*a≡1(mod m),有δ+m(a-1)=δ+m(a)。

定义:设(a,m)=1(或存在x0和y0,使得a*x0+m*y0=1),m≥2。若有正整数d,使得m∣ad+1(即ad≡-1(mod m)),记δ-m(a)是满足以上性质的最小正整数d,称为a对模m的半阶。

性质1.:当m=2时,δ+2(a)=δ-2(a)=1 。

性质2.:当m>2时,δ+m(a)=2δ-m(a)。

若δ+m(a)≤δ-m(a),∵aδ-m(a)+1=aδ+m(a)(a^δ-m(a)-δ+m(a)+1),

∴m∣(aδ-m(a)-δ+m(a)+1),即aδ-m(a)-δ+m(a)≡-1(mod m)。

由δ-m(a)的最小性,知:δ-m(a)-δ+m(a)=0。但m>2,不可能∴δ+m(a)>δ-m(a)∵a^2δ-m(a)≡1(mod m)∴δ+m(a)∣2δ-m(a)又∵δ+m(a)>δ-m(a)∴δ+m(a)=2δ-m(a)。

性质3.:

当m>2时,m∣ah+1(即ah≡-1(mod m)),充要条件是δ-m(a)∣h,h/δ-m(a)是奇数。

:设h=qδ-m(a)+r,0≤r<δ-m(a),∴ah+1=ar(a ^(qδ-m(a)) - (-1) q*a^r+(-1)q* a^r+1。

∴m∣ar+(-1)q,即ar≡-(-1)q(mod m)。∵m>2,δ-m(a)的最小性,∴q不可能为偶数。

∴q= h/δ-m(a)是奇数。∵δ+m(a)>δ-m(a)>r,δ-m(a)的最小性,∴r=0∴δ-m(a)∣h。

性质4.:

当m∣ah+1(即ah≡-1(mod m)),或m∣a^h-1(即ah≡1(mod m))时,均有δ-m(a)∣h。

④:原根:

——————————定义:

原根是一种数学符号,设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)

假设一个数g是P的原根,那么g^i mod P的结果两两不同,且有 1

简单来说,g^i mod p ≠ g^j mod p (p为素数),其中i≠j且i, j介于1至(p-1)之间,则g为p的原根。

——————————性质:

原根具有以下性质:

(1)对于任意正整数a,m,如果(a,m) = 1,存在最小的正整数 d 满足a^d≡1(mod m),则有 d 整除 φ(m),因此Ordm(a)整除φ(m)。这里的d被称为a模m的阶,记为Ordm(a)。——>>> ## Ordm(a) 使得a^Ordm(a)≡1(mod m)
  例如:求3模7的阶时,我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。

(2)记δ = O r d m ( a ),则a1,……a(δ-1)模 m 两两不同余。因此当a是模m的原根时,a0,a1,……a^(δ-1)构成模 m 的简化剩余系。

(3)模m有原根的充要条件是m= 1,2,4,p,2p,p^n,其中p是奇质数,n是任意正整数。

(4)对正整数(a,m) = 1,如果 a 是模 m 的原根,那么 a 是**整数模n乘法群(即加法群 Z/mZ的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn的一个生成元。由于Z**n有 φ(m)个元素,而它的生成元的个数就是它的可逆元个数,即 φ(φ(m))个,因此当模m有原根时,它有φ(φ(m))个原根。

—————>>>欧拉函数<<<:

​ 在数论,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)。此函数以其首名研究者欧拉命名(Euler’s totient function),它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

通式:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1Fahs77X-1608436422080)(https://bkimg.cdn.bcebos.com/formula/ba40ed514646510df8a1033ff30701aa.svg)](其中p1, p2……pn为x的所有质因数,x是不为0的整数)

定义 φ(1)=1(和1互质的数(小于等于1)就是1本身)。注意:每种质因数只有一个。

若n是质数p的k次幂,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ao1LhdAy-1608436422080)(https://bkimg.cdn.bcebos.com/formula/b843a8b241f76d7068e96630fc384bb9.svg)],因为除了p的倍数外,其他数都跟n互质。

比如12=2*2*3那么φ(12)=φ(4*3)=φ(22*31)=(22-21)*(31-30)=4

设n为正整数,以 φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值

φ:N→N,n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R9zdwomp-1608436422081)(https://bkimg.cdn.bcebos.com/formula/312031d1a76fa578eb4ef166530937fa.svg)]

特殊性质:当n为奇质数时,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mjKxHMGH-1608436422081)(https://bkimg.cdn.bcebos.com/formula/5047f2bc6e623027b7707e6c51adc92f.svg)], 证明与上述类似。

若n为质数则[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Isum06q8-1608436422082)(https://bkimg.cdn.bcebos.com/formula/25e9558d577009b1b8b56f9a103b2321.svg)]

证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知,若[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2lIHRpfc-1608436422082)(https://bkimg.cdn.bcebos.com/formula/b689c5f3bc3bd614b600806584a0cdb4.svg)]则[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UIs1CWOg-1608436422083)(https://bkimg.cdn.bcebos.com/formula/da073c0163a4267db82b77da9e970e41.svg)]

例如[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k5JO1qXW-1608436422083)(https://bkimg.cdn.bcebos.com/formula/b9da8fe1c5634394163b2d5d28fe1207.svg)]与欧拉定理、费马小定理的关系

对任何两个互质的正整数a, m(m>=2)有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f204CMFJ-1608436422083)(https://bkimg.cdn.bcebos.com/formula/3299b84e0579640e7850b0557cdfcad1.svg)]即欧拉定理

当m是质数p时,此式则为:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DkPQUqAY-1608436422084)(https://bkimg.cdn.bcebos.com/formula/1afec892eb28397532afc4a1e0033468.svg)]即费马小定理。

——————————原根存在条件:

原根存在的条件有以下几个:

定理一:设p是奇素数,则模p的原根存在;

定理二:设g是模p的原根,则g或者g+p是模[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cY0uCXF2-1608436422084)(https://bkimg.cdn.bcebos.com/formula/c0dee93635088cdcefe83be0398d1229.svg)]的原根;

定理三:设p是奇素数,则对任意[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AZkqcQCZ-1608436422085)(https://bkimg.cdn.bcebos.com/formula/219e07cd6117a5150dd0d7aee4592aaa.svg)],模[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hWzLC1mk-1608436422085)(https://bkimg.cdn.bcebos.com/formula/08d31591f8b4d54eadb878d104580944.svg)]的原根存在;

定理四:设[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TAu8WyQE-1608436422085)(https://bkimg.cdn.bcebos.com/formula/219e07cd6117a5150dd0d7aee4592aaa.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QdKbFciD-1608436422086)(https://bkimg.cdn.bcebos.com/formula/b33249e39ddc764f15916bf5f5a87a5b.svg)]1,若g是模[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OeoWK9ke-1608436422087)(https://bkimg.cdn.bcebos.com/formula/08d31591f8b4d54eadb878d104580944.svg)]的一个原根,则g与g+[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UKyg3NNh-1608436422087)(https://bkimg.cdn.bcebos.com/formula/08d31591f8b4d54eadb878d104580944.svg)]中的奇数是模2[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F28Ba6uC-1608436422087)(https://bkimg.cdn.bcebos.com/formula/08d31591f8b4d54eadb878d104580944.svg)]的一个原根。

——————————例子:

m= 7,则φ(7)等于6。

a= 2,由于2^3=8≡1(mod 7),26=64≡1(mod7),23≡2^6(mod7),所以 2 不是模 7 的一个原根。设a= 3,由于3^1≡3(mod 7),3^2≡2(mod 7),3^3≡6(mod 7),3^4≡4(mod 7),3^5≡5(mod 7),3^6≡1(mod 7),所以 3 是模 7 的一个原根。

[外链图片转存中…(img-OeoWK9ke-1608436422087)]的一个原根,则g与g+[外链图片转存中…(img-UKyg3NNh-1608436422087)]中的奇数是模2[外链图片转存中…(img-F28Ba6uC-1608436422087)]的一个原根。

——————————例子:

m= 7,则φ(7)等于6。

a= 2,由于2^3=8≡1(mod 7),26=64≡1(mod7),23≡2^6(mod7),所以 2 不是模 7 的一个原根。设a= 3,由于3^1≡3(mod 7),3^2≡2(mod 7),3^3≡6(mod 7),3^4≡4(mod 7),3^5≡5(mod 7),3^6≡1(mod 7),所以 3 是模 7 的一个原根。

补充一点,根据原根的性质1,只需要验证31,32,33,36即可,这样可以简化运算。


本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!

相关文章

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部