精华内容
下载资源
问答
  • 数论——高次同余式

    2021-11-03 01:02:31
    (1) (2)

    (1)

     (2)

     

     

    展开全文
  • 8.素数模高次同余方程 1. 素数模的高次同余方程 问题的引出 一般素数p模同余方程 f(x)=a0xn+...+an≡0(mod p),p不整除a0 f(x)=a_0x^n+...+a_n≡0(mod\ p),p不整除a_0 f(x)=a0​xn+...+an​≡0(mod p),p不...

    8.素数模高次同余方程

    1. 素数模的高次同余方程

    问题的引出

    一般素数p模同余方程
    f ( x ) = a 0 x n + . . . + a n ≡ 0 ( m o d   p ) , p 不 整 除 a 0 f(x)=a_0x^n+...+a_n≡0(mod\ p),p不整除a_0 f(x)=a0xn+...+an0(mod p),pa0
    的求解问题

    基本方法

    把模p的完全剩余系中数一一代入即可求解。但当p,n过大时,代入验算不是易事。因此需要简化处理。

    简化处理方式

    • f ( x ) f(x) f(x)的系数有大于p的都把它们化为小于p

    • f ( x ) f(x) f(x)的次数n不小于p,利用 x p ≡ x ( m o d   p ) x^p≡x(mod\ p) xpx(mod p)(费马小定理),可以用 x p − x x^p-x xpx(因为 x p − x ≡ 0 ( m p d   p ) x^p-x≡0(mpd\ p) xpx0(mpd p))除 f ( x ) f(x) f(x)得到次数小于p的 r ( x ) r(x) r(x),即把 f ( x ) f(x) f(x)化为次数小于p的 r ( x ) r(x) r(x)。即
      f ( x ) ≡ r ( x ) ( m o d   p ) f(x)≡r(x)(mod\ p) f(x)r(x)(mod p)

    • f ( x ) = g 1 ( x ) g 2 ( x ) ( m o d   p ) f(x)=g_1(x)g_2(x)(mod\ p) f(x)=g1(x)g2(x)(mod p),则原方程的求解问题变成求解 g 1 ( x ) ≡ 0 ( m o d   p ) g_1(x)≡0(mod\ p) g1(x)0(mod p) g 2 ( x ) ≡ 0 ( m o d   p ) g_2(x)≡0(mod\ p) g2(x)0(mod p)

      由于 d e g g 1 ( x ) < d e g f ( x ) , d e g g 2 ( x ) < d e g f ( x ) degg_1(x)<degf(x),degg_2(x)<degf(x) degg1(x)<degf(x),degg2(x)<degf(x),计算的困难性可以大大减少。

    • 若已经知道了同余方程的一个解 x ≡ a ( m o d   p ) x≡a(mod\ p) xa(mod p),则由于 f ( x ) = ( x − a ) g ( x ) + r f(x)=(x-a)g(x)+r f(x)=(xa)g(x)+r,有 r ≡ 0 ( m o d   p ) r≡0(mod\ p) r0(mod p),因此 f ( x ) ≡ ( x − a ) g ( x ) ( m o d   p ) f(x)≡(x-a)g(x)(mod\ p) f(x)(xa)g(x)(mod p),求解问题变为 g ( x ) ≡ 0 ( m o d   p ) g(x)≡0(mod\ p) g(x)0(mod p)

    例子

    x 2 ≡ 1 ( m o d   p ) x^2≡1(mod\ p) x21(mod p)

    只有1和 p − 1 p-1 p1两个解。其中p为素数

    答:
    显 然 , x ≡ 1 是 原 方 程 f ( x ) = x 2 − 1 ≡ 0 ( m o d   p ) 的 一 个 解 。 由 于 f ( x ) = ( x − 1 ) ( x + 1 ) 因 此 f ( x ) ≡ ( x − 1 ) ( x + 1 ) ≡ 0 ( m o d   p ) , 求 解 问 题 变 为 ( x + 1 ) ≡ 0 ( m o d   p ) 显 然 此 时 x ≡ p − 1 ( m o d   p ) 显然,x≡1是原方程f(x)=x^2-1≡0(mod\ p)的一个解。 \\由于f(x) = (x-1)(x+1) \\因此f(x) ≡ (x-1)(x+1)≡0(mod\ p),求解问题变为(x+1)≡0(mod\ p) \\显然此时x ≡ p-1(mod\ p) x1f(x)=x210(mod p)f(x)=(x1)(x+1)f(x)(x1)(x+1)0(mod p)(x+1)0(mod p)xp1(mod p)

    例子

    求与同余式 3 x 14 + 4 x 13 + 2 x 11 + x 9 + x 6 + x 3 + 12 x 2 ≡ 0 ( m o d   5 ) 3x^{14}+4x^{13}+2x^{11}+x^9+x^6+x^3+12x^2≡0(mod\ 5) 3x14+4x13+2x11+x9+x6+x3+12x20(mod 5)等价的次数小于5的同余式

    解:

    3 x 14 + 4 x 13 + 2 x 11 + x 9 + x 6 + x 3 + 12 x 2 3x^{14}+4x^{13}+2x^{11}+x^9+x^6+x^3+12x^2 3x14+4x13+2x11+x9+x6+x3+12x2 = ( x 5 − x ) ( 3 x 9 + 4 x 8 + 2 x 6 + 3 x 5 + 5 x 4 + 2 x 2 + 4 x + 5 ) + 3 x 3 + 16 x 2 + 6 x =(x^5-x)(3x^9+4x^8+2x^6+3x^5+5x^4+2x^2+4x+5)+3x^3+16x^2+6x =(x5x)(3x9+4x8+2x6+3x5+5x4+2x2+4x+5)+3x3+16x2+6x

    所以原同余式等价于 3 x 3 + 16 x 2 + 6 x ≡ 0 ( m o d   5 ) 3x^3+16x^2+6x≡0(mod\ 5) 3x3+16x2+6x0(mod 5)

    例子

    x p − 1 ≡ 1 ( m o d   p ) x^{p-1}≡1(mod\ p) xp11(mod p)

    p − 1 p-1 p1个(不相同的)解。其中p为素数

    解1:

    由 于 p 是 素 数 , 所 以 φ ( p ) = p − 1 由 欧 拉 定 理 , 当 ( k , p ) = 1 时 , k φ ( p ) ≡ 1 ( m o d   p ) 即 k p − 1 ≡ 1 ( m o d   p ) 由 于 p 是 素 数 , 因 此 p 的 p 个 剩 余 类 里 只 有 [ 0 ] 与 p 不 互 素 因 此 x p − 1 ≡ 1 ( m o d   p ) 有 p − 1 个 ( 不 相 同 的 ) 解 , 其 中 p 为 素 数 。 由于p是素数,所以\varphi(p) = p-1 \\由欧拉定理,当(k,p)=1时,k^{\varphi(p)}≡1(mod\ p) \\即k^{p-1}≡1(mod\ p) \\由于p是素数,因此p的p个剩余类里只有[0]与p不互素 \\因此x^{p-1}≡1(mod\ p)有p-1个(不相同的)解,其中p为素数。 pφ(p)=p1(k,p)=1kφ(p)1(mod p)kp11(mod p)ppp[0]pxp11(mod p)p1p

    解2:

    这 个 方 程 有 p − 1 个 不 同 的 解 : x ≡ 1 , . . . , p − 1 ( m o d   p ) 在 模 p 的 意 义 下 有 如 下 分 解 : x p − 1 − 1 ≡ ( x − 1 ) ( x − 2 ) . . . ( x − ( p − 1 ) )   ( m o d   p ) 令 x = 0 , 有 : − 1 ≡ ( − 1 ) p − 1 ( p − 1 ) !   ( m o d   p ) 这个方程有p-1个不同的解: \\x≡1,...,p-1(mod\ p) \\在模p的意义下有如下分解: \\x^{p-1}-1≡(x-1)(x-2)...(x-(p-1))\ (mod\ p) \\令x=0,有:-1≡(-1)^{p-1}(p-1)!\ (mod\ p) p1x1,...,p1(mod p)pxp11(x1)(x2)...(x(p1)) (mod p)x=01(1)p1(p1)! (mod p)

    Wilson定理

    若 p 为 素 数 , 则 ( p − 1 ) ! ≡ − 1 ( m o d   p ) 若p为素数,则(p-1)!≡-1(mod\ p) p(p1)!1(mod p)

    • 当p是奇素数时,上面的例子显然满足Wilson定理
    • 当p是偶素数时,显然p只能是2,而 − 1 ≡ ( − 1 ) 2 − 1 ( 2 − 1 ) ! ( m o d   2 ) -1≡(-1)^{2-1}(2-1)!(mod\ 2) 1(1)21(21)!(mod 2),上面的例子也满足Wilson定理
    例子

    若p>2,则
    x p − 2 + x p − 3 + . . . + x + 1 ≡ 0   ( m o d   p ) x^{p-2}+x^{p-3}+...+x+1≡0\ (mod\ p) xp2+xp3+...+x+10 (mod p)
    p − 2 p-2 p2个不相同的解:
    x ≡ 2 , 3 , . . . , p − 1   ( m o d   p ) x≡2,3,...,p-1\ (mod\ p) x2,3,...,p1 (mod p)

    解:

    由 于 x p − 1 − 1 ≡ ( x − 1 ) ( x − 2 ) . . . ( x − ( p − 1 ) )   ( m o d   p ) ( 上 面 的 结 论 ) 且 x p − 1 − 1 ≡ ( x − 1 ) ( x p − 2 + x p − 3 + . . . + x + 1 )   ( m o d   p ) 因 此 ( x − 1 ) ( x − 2 ) . . . ( x − ( p − 1 ) ) ≡ ( x − 1 ) ( x p − 2 + x p − 3 + . . . + x + 1 )   ( m o d   p ) 而 上 式 左 边 有 p − 1 个 不 同 的 解 : 1 , 2 , . . . , p − 1    ( m o d   p ) 因 此 上 式 右 边 也 有 p − 1 个 不 同 的 解 : 1 , 2 , . . . , p − 1    ( m o d   p ) 其 中 ( x − 1 ) 贡 献 解 1   ( m o d   p ) 从 而 x p − 2 + x p − 3 + . . . + x + 1 ≡ 0   ( m o d   p ) 有 p − 2 个 不 相 同 的 解 : 2 , 3 , . . . , p − 1   ( m o d   p ) 由于x^{p-1}-1≡(x-1)(x-2)...(x-(p-1))\ (mod\ p)(上面的结论) \\且x^{p-1}-1≡(x-1)(x^{p-2}+x^{p-3}+...+x+1)\ (mod\ p) \\因此(x-1)(x-2)...(x-(p-1))≡(x-1)(x^{p-2}+x^{p-3}+...+x+1)\ (mod\ p) \\而上式左边有p-1个不同的解:1,2,...,p-1\ \ (mod\ p) \\因此上式右边也有p-1个不同的解:1,2,...,p-1\ \ (mod\ p) \\其中(x-1)贡献解1\ (mod\ p) \\从而x^{p-2}+x^{p-3}+...+x+1≡0\ (mod\ p)有p-2个不相同的解: \\2,3,...,p-1\ (mod\ p) xp11(x1)(x2)...(x(p1)) (mod p)xp11(x1)(xp2+xp3+...+x+1) (mod p)(x1)(x2)...(x(p1))(x1)(xp2+xp3+...+x+1) (mod p)p11,2,...,p1  (mod p)p11,2,...,p1  (mod p)(x1)1 (mod p)xp2+xp3+...+x+10 (mod p)p22,3,...,p1 (mod p)

    重解

    定义

    假如关于模 m m m ( x − a ) k {(x-a)}^k (xa)k f ( x ) f(x) f(x)的因式,但 ( x − a ) k + 1 {(x-a)}^{k+1} (xa)k+1不是 f ( x ) f(x) f(x)的因式,则 x ≡ a ( m o d   m ) x≡a(mod\ m) xa(mod m)叫做同余方程 f ( x ) ≡ 0 ( m o d   m ) f(x)≡0(mod\ m) f(x)0(mod m)的k重解。当k=1时又称为单解,当k>1时叫做重解。

    例子

    f ( x ) = x 7 − 2 x 6 − 7 x 5 + x + 2 ≡ 0 ( m o d   5 ) f(x)=x^7-2x^6-7x^5+x+2≡0(mod\ 5) f(x)=x72x67x5+x+20(mod 5)可分解为
    f ( x ) = ( x − 1 ) ( x + 1 ) 2 ( x − 2 ) 2 ( x 2 + x + 2 ) ( m o d   5 ) f(x)=(x-1){(x+1)}^2{(x-2)}^2(x^2+x+2)(mod\ 5) f(x)=(x1)(x+1)2(x2)2(x2+x+2)(mod 5)
    因此 x ≡ 1 x≡1 x1 f ( x ) ≡ 0 ( m o d   5 ) f(x)≡0(mod\ 5) f(x)0(mod 5)的单解, x ≡ 2 , 4 x≡2,4 x2,4是重解。注意到当 f ( x ) ≡ 0 ( m o d   p ) f(x)≡0(mod\ p) f(x)0(mod p)降次后得到的 r ( x ) ≡ 0 ( m o d   p ) r(x)≡0(mod\ p) r(x)0(mod p)中不相同的解是一致的,但它们在各方程中的重数不一定一致

    拉格朗日定理

    f ( x ) ≡ 0 ( m o d   p ) 的 不 相 同 的 解 的 个 数 不 大 于 f ( x ) 的 次 数 f(x)≡0(mod\ p)的不相同的解的个数不大于f(x)的次数 f(x)0(mod p)f(x)

    证明:

    用 数 学 归 纳 法 : 当 n = 1 时 , 定 理 显 然 成 立 假 定 n − 1 时 定 理 成 立 , 假 如 x = a 是 f ( x ) ≡ 0 ( m o d   p ) 的 解 , 即 有 f ( a ) ≡ 0 ( m o d   p ) . 令 f ( x ) ≡ ( x − a ) g ( x ) ( m o d   p ) . 若 x ≡ b ( m o d   p ) 是 任 意 一 解 , 则 有 : f ( b ) ≡ ( b − a ) g ( b ) ≡ 0 ( m o d   p ) 故 有 b ≡ a ( m o d   p ) 或 g ( b ) ≡ 0 ( m o d   p ) 前 者 说 明 b 与 a 在 模 p 之 下 同 余 , 后 者 说 明 x ≡ b ( m o d   p ) 是 g ( x ) ≡ 0 ( m o d   p ) 的 解 。 也 就 是 说 f ( x ) ≡ 0 ( m o d   p ) 的 解 或 者 是 x ≡ a ? ( m o d   p ) , 或 者 是 g ( x ) ≡ 0 ( m o d   p ) 由 于 d e g g ( x ) = n − 1 , 由 归 纳 假 设 , 它 的 不 相 同 的 解 的 个 数 不 多 于 n − 1 个 。 因 此 无 论 哪 种 情 况 , f ( x ) ≡ 0 ( m o d   p ) 的 解 数 都 不 超 过 n 个 用数学归纳法:当n=1时,定理显然成立 \\假定n-1时定理成立,假如x=a是f(x)≡0(mod\ p)的解,即 \\有f(a)≡0(mod\ p). \\令f(x)≡(x-a)g(x)(mod\ p).若x≡b(mod\ p )是任意一解,则有: \\f(b) ≡(b-a)g(b)≡0(mod\ p) \\故有b≡a(mod\ p)或g(b)≡0(mod\ p) \\前者说明b与a在模p之下同余, \\后者说明x≡b(mod\ p)是g(x)≡0(mod\ p)的解。 \\也就是说f(x)≡0(mod\ p)的解或者是x≡a?(mod\ p),或者是g(x)≡0(mod\ p) \\由于degg(x)=n-1,由归纳假设,它的不相同的解的个数不多于n-1个。 \\因此无论哪种情况,f(x)≡0(mod\ p)的解数都不超过n个 n=1n1x=af(x)0(mod p)f(a)0(mod p).f(x)(xa)g(x)(mod p).xb(mod p)f(b)(ba)g(b)0(mod p)ba(mod p)g(b)0(mod p)bapxb(mod p)g(x)0(mod p)f(x)0(mod p)xa(mod p)g(x)0(mod p)degg(x)=n1n1f(x)0(mod p)n

    拉格朗日定理的注记
    1. 由拉格朗日定理可知,假如
      a 0 x n + a 1 x n − 1 + . . . + a n ≡ 0 ( m o d   p ) a_0x^n+a_1x^{n-1}+...+a_n≡0(mod\ p) a0xn+a1xn1+...+an0(mod p)
      有多于n个不相同的解,则它的所有系数都能用p整数,即
      a i ≡ 0 ( m o d   p ) , i = 0 , 1 , . . . , m a_i≡0(mod\ p),i = 0,1,...,m ai0(mod p),i=0,1,...,m

    2. f ( x ) = a 0 x n + . . . + a n ≡ 0 ( m o d   p ) , p 不 整 除 a 0 f(x)=a_0x^n+...+a_n≡0(mod\ p),p不整除a_0 f(x)=a0xn+...+an0(mod p)pa0

      不一定有解。即使有解,解的个数也不一致。上定理只是解个数的最好上限而已

      例如:

      x 3 + 4 x 2 + x + 1 ≡ 0 ( m o d   5 ) x^3+4x^2+x+1≡0(mod\ 5) x3+4x2+x+10(mod 5)无解

      x 3 + 2 x 2 − 2 x + 1 ≡ 0 ( m o d   5 ) x^3+2x^2-2x+1≡0(mod\ 5) x3+2x22x+10(mod 5)有一个解: x ≡ − 2 ( m o d   5 ) x≡-2(mod\ 5) x2(mod 5)

      x 3 − 2 x 2 − x + 2 ≡ 0 ( m o d   5 ) x^3-2x^2-x+2≡0(mod\ 5) x32x2x+20(mod 5)有三个解: x ≡ 1 , − 1 , − 2 ( m o d   5 ) x≡1,-1,-2(mod\ 5) x1,1,2(mod 5)

    3. 拉格朗日定理之所以能成立,是因为模数是素数。假如模数是合数,定理不一定成立。

      例如:
      x 3 − x = x ( x − 1 ) ( x + 1 ) ≡ 0   ( m o d   6 ) x^3-x=x(x-1)(x+1)≡0\ (mod\ 6) x3xx(x1)(x+1)0 (mod 6)
      有6个解: x ≡ 0 , 1 , 2 , 3 , 4 , 5   ( m o d   6 ) x≡0,1,2,3,4,5\ (mod\ 6) x0,1,2,3,4,5 (mod 6)

      原因:

      若p是合数,那么在拉格朗日定理的证明过程中:
      f ( b ) ≡ ( b − a ) g ( b ) ≡ 0 ( m o d   p ) 故 有 b ≡ a ( m o d   p ) 或 g ( b ) ≡ 0 ( m o d   p ) f(b) ≡(b-a)g(b)≡0(mod\ p) \\故有b≡a(mod\ p)或g(b)≡0(mod\ p) f(b)(ba)g(b)0(mod p)ba(mod p)g(b)0(mod p)
      不再成立。因为:
      若 p 是 素 数 , c ∗ d ≡ 0 ( m o d   p )    ⟺    c ∗ d = n ∗ p    ⟺    p ∣ c ∗ d    ⟺    p ∣ c 或 p ∣ d 若 p 是 合 数 , 上 述 性 质 “ p ∣ c ∗ d    ⟺    p ∣ c 或 p ∣ d ” 不 再 成 立 若p是素数,c*d≡0(mod\ p)\iff c*d=n*p \\ \iff p|c*d\iff p|c或p|d \\若p是合数,上述性质“p|c*d\iff p|c或p|d”不再成立 pcd0(mod p)cd=nppcdpcpdppcdpcpd

    n次同余方程有n个不同解的判定

    定理

    n ( < p ) 次 同 余 方 程 f ( x ) ≡ 0 ( m o d   p ) 有 n 个 不 相 同 解 的 必 要 充 分 条 件 是 : f ( x ) 在 模 p 之 下 是 x p − x 的 因 式 。 n(<p)次同余方程f(x)≡0(mod\ p)有n个不相同解的必要充分条件是: \\f(x)在模p之下是x^p-x的因式。 n(<p)f(x)0(mod p)nf(x)pxpx

    充分性证明:

    假 如 x p − x ≡ q ( x ) f ( x ) ( m o d   p ) . ( 即 : f ( x ) 在 模 p 之 下 是 x p − x 的 因 式 ) 若 f ( x ) ≡ 0 ( m o d   p ) 解 的 个 数 小 于 n , 由 于 q ( x ) ≡ 0 ( m o d   p ) 的 解 不 能 多 于 p − n 个 , 故 q ( x ) f ( x ) ≡ 0 ( m o d   p ) 的 解 少 于 p 个 , 这 与 前 面 的 例 子 矛 盾 故 f ( x ) ≡ 0 ( m o d   p ) 的 解 有 n 个 。 假如x^p-x≡q(x)f(x)(mod\ p).(即:f(x)在模p之下是x^p-x的因式) \\若f(x)≡0(mod\ p)解的个数小于n,由于q(x)≡0(mod\ p)的解不能多于p-n个, \\故q(x)f(x)≡0(mod\ p)的解少于p个,这与前面的例子矛盾 \\故f(x)≡0(mod\ p)的解有n个。 xpxq(x)f(x)(mod p).f(x)pxpxf(x)0(mod p)nq(x)0(mod p)pnq(x)f(x)0(mod p)pf(x)0(mod p)n

    前面的例子指:
    x p − 1 ≡ 1 ( m o d   p ) 有 p − 1 个 ( 不 相 同 的 ) 解 , 其 中 p 为 素 数 。 从 而 x p − x ≡ 0 有 p 个 ( 不 相 同 的 ) 解 x^{p-1}≡1(mod\ p)有p-1个(不相同的)解,其中p为素数。 \\从而x^p-x≡0有p个(不相同的)解 xp11(mod p)p1pxpx0p

    必要性证明:

    若 n ( < p ) 次 同 余 方 程 f ( x ) ≡ 0 ( m o d   p ) 有 n 个 不 相 同 解 , 设 为 x 1 , . . . , x n , 则 f ( x ) 可 以 写 为 : f ( x ) = c ( x − x 1 ) ( x − x 2 ) . . . ( x − x n ) ( m o d   p ) 由 于 前 面 的 例 子 : x p − 1 − 1 ≡ ( x − 1 ) ( x − 2 ) . . . ( x − ( p − 1 ) )   ( m o d   p ) 得 到 x p − x ≡ ( x − 0 ) ( x − 1 ) ( x − 2 ) . . . ( x − ( p − 1 ) )   ( m o d   p ) 显 然 , f ( x ) 在 模 p 之 下 是 x p − x 的 因 式 。 若n(<p)次同余方程f(x)≡0(mod\ p)有n个不相同解,设为x_1,...,x_n, \\ 则f(x)可以写为: \\f(x)=c(x-x_1)(x-x_2)...(x-x_n)(mod\ p) \\由于前面的例子:x^{p-1}-1≡(x-1)(x-2)...(x-(p-1))\ (mod\ p) \\得到x^{p}-x≡(x-0)(x-1)(x-2)...(x-(p-1))\ (mod\ p) \\显然,f(x)在模p之下是x^{p}-x的因式。 n(<p)f(x)0(mod p)nx1,...,xn,f(x)f(x)=c(xx1)(xx2)...(xxn)(mod p)xp11(x1)(x2)...(x(p1)) (mod p)xpx(x0)(x1)(x2)...(x(p1)) (mod p)f(x)pxpx

    2. 模pq的e次剩余

    m = p q m=pq m=pq是两个不同素数的乘积时,是否仍满足 a m − 1 ≡ 1 ( m o d   m ) a^{m-1}≡1(mod\ m ) am11(mod m)呢?

    示例

    一个数的幂次模15的结果会是什么样的?如果我们做一个平方以及立方模15的表,结果看起来并不十分有趣,但是对于四次方模15,有许多结果为1的情况:
    a 4 ≡ 1 ( m o d   15 )   a = 1 , 2 , 4 , 7 , 8 , 11 , 13 , 14 ; a 4 ≠ 1 ( m o d   15 )   a = 3 , 5 , 6 , 9 , 10 , 12. a^4≡1(mod\ 15)\ a=1,2,4,7,8,11,13,14; \\a^4≠1(mod\ 15)\ a=3,5,6,9,10,12. a41(mod 15) a=1,2,4,7,8,11,13,14;a4=1(mod 15) a=3,5,6,9,10,12.
    这表明,当a与模数m互素时可以找到一些类似于费马小定理的结果,但是这些结果对应的指数却不一定是m-1.

    对于m = 15,我们发现结果为1,对应指数是4。为什么是4?

    为了说明 a 4 ≡ 1 ( m o d   15 ) a^4≡1(mod\ 15) a41(mod 15),只需检验以下两个同余式的正确性:
    a 4 ≡ 1 ( m o d   3 )       a 4 ≡ 1 ( m o d   5 ) a^4≡1(mod\ 3)\ \ \ \ \ a^4≡1(mod\ 5) a41(mod 3)     a41(mod 5)
    两个同余式的模数都是素数,可通过费马小定理检验其正确性,因此有:
    a 4 ≡ ( a 2 ) 2 ≡ ( a 3 − 1 ) 2 ≡ 1 2 ≡ 1 ( m o d   3 ) a 4 ≡ a 5 − 1 ≡ 1 ( m o d   5 ) a^4≡{(a^2)}^2≡{(a^{3-1})}^2≡1^2≡1(mod\ 3) \\a^4≡a^{5-1}≡1(mod\ 5) a4(a2)2(a31)2121(mod 3)a4a511(mod 5)
    若考虑这两个同余式,可以看出指数4的关键性质是它是p=3和p=5对应的p-1的公倍数。注意到14就不满足这一性质,也就不是有效的指数。

    基于这一观察,我们准备介绍RSA公钥密码的基本公式。

    模pq的欧拉公式

    定理

    设 p 和 q 是 不 同 的 素 数 , 设 g = g c d ( p − 1 , q − 1 ) . 对 于 所 有 满 足 g c d ( a , p q ) = 1 的 a , 有 a ( p − 1 ) ( q − 1 ) g ≡ 1 ( m o d   p q ) 特 别 地 , 若 p 和 q 都 是 奇 素 数 , g c d ( p − 1 , q − 1 ) = 1 , 则 a ( p − 1 ) ( q − 1 ) 2 ≡ 1 ( m o d   p q ) 设p和q是不同的素数,设g=gcd(p-1,q-1). \\对于所有满足gcd(a,pq)=1的a,有a^{\frac{(p-1)(q-1)}{g}}≡1(mod\ pq) \\特别地,若p和q都是奇素数,gcd(p-1 , q-1)=1,则a^{\frac{(p-1)(q-1)}{2}}≡1(mod\ pq) pqg=gcd(p1,q1).gcd(a,pq)=1aag(p1)(q1)1(mod pq)pqgcd(p1,q1)=1,a2(p1)(q1)1(mod pq)

    • ( p − 1 ) ( q − 1 ) g \frac{(p-1)(q-1)}{g} g(p1)(q1):就是 ( p − 1 ) ( q − 1 ) (p-1)(q-1) (p1)(q1)的最小公倍数
    证明

    由 假 设 可 知 p 不 整 除 a 且 g 整 除 q − 1 , 因 此 我 们 可 以 计 算 : a ( p − 1 ) ( q − 1 ) g = ( a p − 1 ) ( q − 1 ) / g ( 因 为 q − 1 g 是 整 数 ) ≡ 1 ( q − 1 ) / g ( m o d   p ) ( 因 为 a p − 1 ≡ 1 ( m o d   p ) ≡ 1 ( m o d   p ) ( 因 为 1 的 任 意 幂 次 都 是 1 ) 这 证 明 了 a ( p − 1 ) ( q − 1 ) g − 1 可 以 被 p 和 q 整 除 , 因 此 它 可 以 被 p q 整 除 , 从 而 完 成 了 定 理 的 证 明 由假设可知p不整除a且g整除q-1,因此我们可以计算: \\a^{\frac{(p-1)(q-1)}{g}}={(a^{p-1})}^{(q-1)/g}(因为\frac{q-1}{g}是整数) \\≡1^{(q-1)/g}(mod\ p) (因为a^{p-1}≡1(mod\ p) \\≡1(mod\ p)(因为1的任意幂次都是1) \\这证明了a^{\frac{(p-1)(q-1)}{g}}-1可以被p和q整除,因此它可以被pq整除,从而完成了定理的证明 pagq1ag(p1)(q1)=(ap1)(q1)/ggq11(q1)/g(mod p)ap11(mod p1(mod p)11ag(p1)(q1)1pqpq

    高次同余方程的求解困难性

    RSA公钥密码体系:依赖于求解以下形式同余方程的困难性:
    x e ≡ c ( m o d   N ) x^e≡c(mod\ N) xec(mod N)
    其中e,c,N已知,x未知。换言之,RSA的安全性依赖于求解模N的e次剩余的困难性假设。

    这是合理的假设吗?如下一个命题所述,如果模数N是素数,那么就可相对容易地计算出模N的e次剩余。

    素数模高次同余方程的求解

    命题

    设 p 是 素 数 , e ≥ 1 是 整 数 , 满 足 g c d ( e , p − 1 ) = 1. 则 e 模 p − 1 一 定 有 唯 一 逆 元 , 也 就 是 : d e ≡ 1 ( m o d   p − 1 ) 那 么 同 余 方 程 x e ≡ c ( m o d   p ) , 就 有 唯 一 解 : x ≡ c d ( m o d   p ) 设p是素数,e\ge 1是整数,满足gcd(e,p-1)=1.则e模p-1一定有唯一逆元, \\也就是:de≡1(mod\ p-1) \\那么同余方程x^e≡c(mod\ p),就有唯一解:x≡c^d(mod\ p) pe1gcd(e,p1)=1.ep1de1(mod p1)xec(mod p)xcd(mod p)

    证明:

    如果 c ≡ 0 ( m o d   p ) c≡0(mod\ p) c0(mod p),则 x ≡ 0 ( m o d   p ) x≡0(mod\ p) x0(mod p)是其唯一解,该情况证毕。

    所以我们下面假定 c ≠ 0 ( m o d   p ) c≠0(mod\ p) c=0(mod p)。该情况的证明需要用到费马小定理。首先同余方程 d e ≡ 1 ( m o d   p − 1 ) de≡1(mod\ p-1) de1(mod p1) ,意味着存在一个整数k,使得
    d e = 1 + k ( p − 1 ) de=1+k(p-1) de=1+k(p1)
    现在我们检验 c d c^d cd x e ≡ c ( m o d   p ) x^e≡c(mod\ p) xec(mod p)的解:
    ( c d ) e ≡ c d e ( m o d   p ) ≡ c 1 + k ( p − 1 ) ( m o d   p ) ≡ c ⋅ ( c p − 1 ) k ( m o d   p ) ≡ c ⋅ 1 k ( m o d   p ) ≡ c ( m o d   p ) {(c^d)}^e≡c^{de}(mod\ p) \\≡c^{1+k(p-1)}(mod\ p) \\≡c·{(c^{p-1})}^k(mod\ p) \\≡c·1^k(mod\ p) \\≡c(mod\ p) (cd)ecde(mod p)c1+k(p1)(mod p)c(cp1)k(mod p)c1k(mod p)c(mod p)
    这就证明了 x = c d x=c^d x=cd x e ≡ c ( m o d   p ) x^e≡c(mod\ p) xec(mod p)的解。

    为了证明解的唯一性,假设有 x 1 x_1 x1 x 2 x_2 x2都是同余方程 x e ≡ c ( m o d   p ) x^e≡c(mod \ p) xec(mod p)的解。我们刚刚证明了 z d e ≡ z ( m o d   p ) z^{de}≡z(mod\ p) zdez(mod p)对于任何非零值z都成立,由此可发现
    x 1 ≡ x 1 d e ≡ ( x 1 e ) d ≡ c d ≡ ( x 2 e ) d ≡ x 2 d e ≡ x 2 ( m o d   p ) x_1≡x_1^{de}≡{(x_1^e)}^d≡c^d≡{(x_2^e)}^d≡x_2^{de}≡x_2(mod\ p) x1x1de(x1e)dcd(x2e)dx2dex2(mod p)
    因此 x 1 x_1 x1 x 2 x_2 x2模p同余,所以 x e ≡ c ( m o d   p ) x^e≡c(mod\ p) xec(mod p)至多有一个解。

    尝试求解同余方程:
    x 1583 ≡ 4714 ( m o d   7919 ) x^{1583}≡4714(mod\ 7919) x15834714(mod 7919)
    其中模数p = 7919是素数。

    首 先 解 同 余 方 程 1583 d ≡ 1 ( m o d   7918 ) 由 扩 展 欧 几 里 得 算 法 求 得 d ≡ 5277 ( m o d   7918 ) . 由 命 题 可 知 : x ≡ 471 4 5277 ≡ 6059 ( m o d   7919 ) 是 同 余 方 程 x 1583 ≡ 4714 ( m o d   7919 ) 的 解 。 首先解同余方程1583d≡1(mod\ 7918) \\由扩展欧几里得算法求得d≡5277(mod\ 7918). \\由命题可知: \\x≡4714^{5277}≡6059(mod\ 7919) \\是同余方程x^{1583}≡4714(mod\ 7919)的解。 1583d1(mod 7918)d5277(mod 7918).:x471452776059(mod 7919)x15834714(mod 7919)

    素数模高次同余方程的注记

    • 命题包括 g c d ( e , p − 1 ) gcd(e,p-1) gcd(e,p1)这一假设。如果去掉这一假设,那么同余方程 x e ≡ c ( m o d   p ) x^e≡c(mod\ p) xec(mod p)对于c的某些值(并非所有值)将有解。此外如果它确实有解,那么解将不止一个。

    命题说明如果模数p是一个素数,那么求解e次方根是很容易的。模数N是合数的情况看起来与之相似,但其实差别很大。如果我们知道如何分解N,那么计算e次方根也是容易的。

    模pq时高次同余方程的求解

    命题

    假 设 p 和 q 是 不 同 的 素 数 , 并 假 设 e ≥ 1 , 满 足 : g c d ( e , ( p − 1 ) ( q − 1 ) ) = 1. 则 e 模 ( p − 1 ) ( q − 1 ) 存 在 逆 元 , 也 就 是 d e ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) ) . 则 同 余 方 程 x e ≡ c ( m o d   p q ) 有 唯 一 解 x ≡ c d ( m o d   p q ) 假设p和q是不同的素数,并假设e\ge 1,满足: \\gcd(e,(p-1)(q-1))=1. \\则e模(p-1)(q-1)存在逆元,也就是 \\de ≡1(mod(p-1)(q-1)). \\则同余方程 \\x^e≡c(mod\ pq) \\有唯一解x≡c^d(mod\ pq) pqe1,gcd(e,(p1)(q1))=1.e(p1)(q1)de1(mod(p1)(q1)).xec(mod pq)xcd(mod pq)

    证明

    首 先 我 们 假 设 g c d ( c , p q ) = 1 同 余 方 程 d e ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) ) 说 明 存 在 一 整 数 k , 使 得 d e = 1 + k ( p − 1 ) ( q − 1 ) 下 面 我 们 验 证 c d 是 x e ≡ c ( m o d   p q ) 的 一 个 解 : ( c d ) e ≡ c d e ( m o d   p q ) ≡ c 1 + k ( p − 1 ) ( q − 1 ) ( m o d   p q ) ≡ c ⋅ ( c ( p − 1 ) ( q − 1 ) ) k ( m o d   p q ) ≡ c ⋅ 1 k ( m o d   p q ) ≡ c ( m o d   p q ) 首先我们假设gcd(c,pq )=1 \\同余方程de≡1(mod(p-1)(q-1))说明存在一整数k,使得 \\de=1+k(p-1)(q-1) \\下面我们验证c^d是x^e≡c(mod\ pq)的一个解: \\{(c^d)}^e≡c^{de}(mod\ pq) \\≡c^{1+k(p-1)(q-1)}(mod\ pq) \\≡c·{(c^{(p-1)(q-1)})}^k(mod\ pq) \\≡c·1^k(mod\ pq) \\≡c(mod\ pq) gcd(c,pq)=1de1(mod(p1)(q1))k使de=1+k(p1)(q1)cdxec(mod pq)(cd)ecde(mod pq)c1+k(p1)(q1)(mod pq)c(c(p1)(q1))k(mod pq)c1k(mod pq)c(mod pq)

    若 g c d ( c , p q ) ≠ 1 , 则 g c d ( c , p q ) = p 或 g c d ( c , p q ) = q 不 妨 设 g c d ( c , p q ) = p , 则 c = x p , 1 ≤ x ≤ q . 由 欧 拉 定 理 知 : c φ ( q ) ≡ 1 ( m o d   q ) 即 有 : c q − 1 ≡ 1 ( m o d   q ) 进 而 : ( c q − 1 ) k ( p − 1 ) ≡ 1 ( m o d   q ) 即 : c k ( p − 1 ) ( q − 1 ) ≡ 1 ( m o d   q ) 存 在 整 数 b 使 得 c k ( p − 1 ) ( q − 1 ) = 1 + b q 两 边 同 时 乘 以 c 得 c 1 + k ( p − 1 ) ( q − 1 ) = c + b c q = c + b x p q ≡ c ( m o d   p q ) 即 ( c d ) e = c 1 + k ( p − 1 ) ( q − 1 ) ≡ c ( m o d   p q ) 从 而 x ≡ c d ( m o d   p q ) 是 同 余 方 程 x e ≡ c ( m o d   p q ) 的 解 若gcd(c , pq)≠1,则gcd(c, pq)=p或gcd(c,pq)=q \\不妨设gcd(c,pq)=p,则c = xp,1\le x \le q. \\由欧拉定理知:c^{\varphi(q)}≡1(mod\ q) \\即有:c^{q-1}≡1(mod\ q) \\进而:{(c^{q-1})}^{k(p-1)}≡1(mod\ q) \\即:c^{k(p-1)(q-1)}≡1(mod\ q) \\存在整数b使得c^{k(p-1)(q-1)}=1+bq \\两边同时乘以c得c^{1+k(p-1)(q-1)}=c+bcq=c+bxpq≡c(mod \ pq) \\即{(c^d)}^e=c^{1+k(p-1)(q-1)}≡c(mod \ pq) \\从而x≡c^d(mod\ pq)是同余方程x^e≡c(mod\ pq)的解 gcd(c,pq)=1gcd(c,pq)=pgcd(c,pq)=qgcd(c,pq)=p,c=xp,1xq.cφ(q)1(mod q)cq11(mod q)(cq1)k(p1)1(mod q)ck(p1)(q1)1(mod q)b使ck(p1)(q1)=1+bqcc1+k(p1)(q1)=c+bcq=c+bxpqc(mod pq)(cd)e=c1+k(p1)(q1)c(mod pq)xcd(mod pq)xec(mod pq)

    还要证明解的唯一性:
    假 设 x = u 是 x e ≡ c ( m o d   p q ) 的 一 个 解 若 g c d ( c , p q ) = 1 , 则 ( u , p q ) = 1 ( ? 为 什 么 呢 ) 有 u ≡ u d e − k ( p − 1 ) ( q − 1 ) ( m o d   p q ) ≡ ( u e ) d ⋅ ( u ( p − 1 ) ( q − 1 ) ) − k ( m o d   p q ) ≡ ( u e ) d ⋅ 1 − k ( m o d   p q ) ≡ c d ( m o d   p q ) 因 此 x e ≡ c ( m o d   p q ) 的 每 个 解 都 等 于 c d ( m o d   p q ) 假设x=u是x^e≡c(mod\ pq)的一个解 \\若gcd(c,pq)=1,则(u,pq)=1(?为什么呢)有 \\u≡u^{de-k(p-1)(q-1)}(mod\ pq) \\≡{(u^e)}^d·{(u^{(p-1)(q-1)})}^{-k}(mod\ pq) \\≡{(u^e)}^d·1^{-k}(mod\ pq) \\≡{c}^d(mod\ pq) \\因此x^e≡c(mod\ pq)的每个解都等于c^d(mod\ pq) x=uxec(mod pq)gcd(c,pq)=1,(u,pq)=1uudek(p1)(q1)(mod pq)(ue)d(u(p1)(q1))k(mod pq)(ue)d1k(mod pq)cd(mod pq)xec(mod pq)cd(mod pq)

    若 g c d ( c , p q ) ≠ 1 , 则 g c d ( c , p q ) = p 或 g c d ( c , p q ) = q 不 妨 设 g c d ( c , p q ) = p , 则 c = x p , 1 ≤ x ≤ q 由 u e ≡ c ( m o d   p q ) 得 u e ≡ c ( m o d   p ) , 有 p ∣ u , 从 而 有 u ≡ c d ( m o d   p ) 又 因 为 u ≡ u d e − k ( p − 1 ) ( q − 1 ) ( m o d   q ) ≡ ( u e ) d ⋅ ( u ( p − 1 ) ( q − 1 ) ) − k ( m o d   q ) ≡ ( u e ) d ⋅ 1 − k ( m o d   q ) ≡ c d ( m o d   q ) 即 有 u ≡ c d ( m o d   q ) , 而 ( p , q ) = 1 故 有 u ≡ c d ( m o d   p q ) , 解 的 唯 一 性 得 证 。 若gcd(c,pq)≠1,则gcd(c,pq)=p或gcd(c,pq)=q \\不妨设gcd(c,pq)=p,则c = xp,1\le x\le q \\由u^e≡c(mod\ pq)得u^e≡c(mod\ p),有p|u,从而有u≡c^d(mod\ p) \\又因为 \\u≡u^{de-k(p-1)(q-1)}(mod\ q) \\≡{(u^e)}^d·{(u^{(p-1)(q-1)})}^{-k}(mod\ q) \\≡{(u^e)}^d·1^{-k}(mod\ q) \\≡{c}^d(mod\ q) \\即有u≡c^d(mod\ q),而(p,q)=1 \\故有u≡c^d(mod\ pq),解的唯一性得证。 gcd(c,pq)=1gcd(c,pq)=pgcd(c,pq)=qgcd(c,pq)=pc=xp,1xquec(mod pq)uec(mod p),pu,ucd(mod p)uudek(p1)(q1)(mod q)(ue)d(u(p1)(q1))k(mod q)(ue)d1k(mod q)cd(mod q)ucd(mod q),(p,q)=1ucd(mod pq)

    模pq时高次同余方程的求解的备注

    • 命题给出了求解 x e ≡ c ( m o d   p q ) x^e≡c(mod\ pq) xec(mod pq)的算法,首先解 d e ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) ) de≡1(mod(p-1)(q-1)) de1(mod(p1)(q1)),然后计算 c d ( m o d   p q ) c^d(mod\ pq) cd(mod pq)。我们通常可通过使用较小的d值来加快计算速度。设 g = ( g c d ( p − 1 ) ( q − 1 ) ) g=(gcd(p-1)(q-1)) g=(gcd(p1)(q1)),并假设我们解出了以下同余方程中的 d d d
      d e ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) g ) de≡1(mod\frac{(p-1)(q-1)}{g}) de1(modg(p1)(q1))

    由欧拉公式可知 a ( p − 1 ) ( q − 1 ) g ≡ 1 ( m o d   p q ) ( 这 又 是 为 什 么 呢 ? ? ? ) a^{\frac{(p-1)(q-1)}{g}}≡1(mod\ pq)(这又是为什么呢???) ag(p1)(q1)1(mod pq)。因此,我们写出 d e = 1 + k ( p − 1 ) ( q − 1 ) g de=1+k\frac{(p-1)(q-1)}{g} de=1+kg(p1)(q1),则
    ( c d ) e ≡ c d e ≡ c 1 + k ( p − 1 ) ( q − 1 ) / g ≡ c ⋅ ( c ( p − 1 ) ( q − 1 ) / g ) k ≡ c ( m o d   p q ) {(c^d)}^e≡c^{de}≡c^{1+k(p-1)(q-1)/g}≡c·{(c^{(p-1)(q-1)/g})}^k≡c(mod\ pq) (cd)ecdec1+k(p1)(q1)/gc(c(p1)(q1)/g)kc(mod pq)
    因此使用这个较小的d值,仍能得到 c d ( m o d   p q ) c^d(mod\ pq) cd(mod pq) x e ≡ c ( m o d   p q ) x^e≡c(mod\ pq) xec(mod pq)的解。

    模pq时高次同余方程的举例

    求解同余方程:
    x 17839 ≡ 43927 ( m o d   64349 ) x^{17839}≡43927(mod\ 64349) x1783943927(mod 64349)
    其中模数N=64349=229.281是两素数p = 229和q = 281的乘积。

    解:

    第一步解同余方程
    17389 d ≡ 1 ( m o d   63840 ) 17389d≡1(mod\ 63840) 17389d1(mod 63840)
    其中63840=(p-1)(q-1)=228·280.

    解为 d ≡ 53509 ( m o d   63840 ) d≡53509(mod\ 63840) d53509(mod 63840),然后由命题3.5得
    x ≡ 4392 7 53509 ≡ 14458 ( m o d   64349 ) x≡43927^{53509}≡14458(mod\ 64349) x439275350914458(mod 64349)
    为方程 x 17389 ≡ 43927 ( m o d   64349 ) x^{17389}≡43927(mod\ 64349) x1738943927(mod 64349)的解

    • 使用备注中描述的技巧,可以节省一点工作量。于是有:
      g = g c d ( p − 1 , q − 1 ) = g c d ( 228 , 280 ) = 4 g = gcd(p-1,q-1)=gcd(228,280)=4 g=gcd(p1,q1)=gcd(228,280)=4
      所以 ( p − 1 ) ( q − 1 ) g = ( 228 ∗ 280 ) 4 = 15960 \frac{(p-1)(q-1)}{g}=\frac{(228*280)}{4}=15960 g(p1)(q1)=4(228280)=15960,然后解下面的同余方程得到相应的d:
      17389 d ≡ 1 ( m o d   15960 ) 17389d≡1(mod\ 15960) 17389d1(mod 15960)
      解得 d ≡ 5629 ( m o d   15960 ) d≡5629(mod\ 15960) d5629(mod 15960),则
      x ≡ 4392 7 5629 ≡ 14458 ( m o d   64349 ) x≡43927^{5629}≡14458(mod\ 64349) x43927562914458(mod 64349)
      对比之前的方法: x ≡ 4392 7 53509 ≡ 14458 ( m o d   64349 ) x≡43927^{53509}≡14458(mod\ 64349) x439275350914458(mod 64349)

    国庆后的第一节信安数基,听的云里雾里,看的一知半解……复健路漫漫啊!

    展开全文
  • 原根与指标 ...作用:原根的求解只是求解高次同余方程时计算指标,判断是否有解。 定理5.2.1 设p是奇素数,则模p的原根存在,且有φ(p−1)φ(p-1)φ(p−1)个原根。 定理5.2.2 设p为奇素数,p-1的所有

    原根与指标

    指数与原根

    a e ≡ 1 ( m o d   m ) a^e≡1(mod\ m) ae1(mod m)

    对于上面这个式子

    成立的最小整数e对模m的指数,记做 o r d m ( a ) ord_{m}(a) ordm(a)

    如果a对模m的指数是 φ ( m ) φ(m) φm,则a叫做模m的原根(原根不唯一)。

    作用:原根的求解只是求解高次同余方程时计算指标,判断是否有解。

    定理5.2.1

    设p是奇素数,则模p的原根存在,且有 φ ( p − 1 ) φ(p-1) φp1个原根。

    定理5.2.2

    设p为奇素数,p-1的所有不同素因子为 q 1 , … … , q s q_1,……,q_s q1,,qs则g是模p的原根的充要条件是:
    g p − 1 q i ! ≡ 1 ( m o d   p ) ,    i = 1 , … … , s g^{\frac{p-1}{q_i}}!≡1(mod\ p),\ \ i=1,……,s gqip1!1(mod p),  i=1,s

    例题求模p=43的原根 P 180 P_{180} P180

    1. 得到p-1
    2. 计算 q i q_i qi(为p-1的素因子)
    3. 将g=2,3,5,6,7等带入计算,逐个验证,根据定理5.2.2进行判断。

    PS

    在进行第三部的时候可以通过求其平方的方法进行迭代,或者其他一些小trick

    指标

    g r ≡ a ( m o d   m ) g^r≡a(mod\ m) gra(mod m)

    对于上式来说:

    • g是模m的一个原根
    • a是一个与m互素的整数
    • 存在唯一一个整数r使上式成立

    这个整数r叫做以g为底的a对模m的一个指标,记作 r = i n d g a ( 或 r = i n d a ) r=ind_ga(或r=inda) r=indga(r=inda)

    当我们了解了原根与指标的计算之后就可以进行高次同余方程的学习了

    高次同余方程判断是否有解

    参考 P 196 P_{196} P196
    x n ≡ a ( m o d   m ) x^n≡a(mod\ m) xna(mod m)
    对于这个高次同余式,有解的条件是满足 ( n , φ ( m ) ) ∣   i n d a (n,φ(m))|\ inda n,φm inda,且解数为 ( n , φ ( m ) ) (n,φ(m)) n,φm

    原根的求解只是求解高次同余方程时计算指标,判断是否有解

    所以我们可以记住常见的模p对应的原根:

    23374143
    5263

    在考试的时候直接写出,然后验证其是原根既可。

    得到了原根,我们就可以根据公式三进行计算,得到对应的指标。

    要求学会画对应的指标表,听说模数小的会让我们求,模数大的会提供一个对应的指标表。

    根据 ( n , φ ( m ) ) ∣   i n d a (n,φ(m))|\ inda n,φm inda进行判断,且解数为 ( n , φ ( m ) ) (n,φ(m)) n,φm
    x 12 ≡ 37 ( m o d   41 ) x^{12}≡37(mod\ 41) x1237(mod 41)
    判断出有解之后进行化简:

    mod φ ( 41 ) φ(41) φ41
    12 i n d x ≡ i n d 37 ( m o d   φ ( 41 ) ) = > 12 i n d x ≡ 32 ( m o d   40 ) = > 3 i n d x ≡ 8 ( m o d   10 ) 12indx≡ind37(mod\ φ(41))\\ =>12indx≡32(mod\ 40)\\ =>3indx≡8(mod\ 10) 12indxind37(mod φ(41))=>12indx32(mod 40)=>3indx8(mod 10)
    自己计算得到一个特殊解: i n d x = 6 indx=6 indx=6

    然后计算特解:
    i n d x = 6 + k × 10 ( m o d   40 )     k ∈ Z indx=6+k×10(mod\ 40)\ \ \ k∈Z indx=6+k×10(mod 40)   kZ
    既可得出 i n d x ≡ 6 , 16 , 26 , 36 ( m o d 40 ) indx≡6,16,26,36(mod 40) indx6,16,26,36(mod40)

    通过查表求出对应的 x ≡ 39 , 18 , 2 , 23 ( m o d   41 ) x≡39,18,2,23(mod\ 41) x39,18,2,23(mod 41)

    求解的过程类似于一次同余式:

    image-20211118221820937

    通过查表求出对应的 x ≡ 39 , 18 , 2 , 23 ( m o d   41 ) x≡39,18,2,23(mod\ 41) x39,18,2,23(mod 41)

    求解的过程类似于一次同余式:
    在这里插入图片描述

    展开全文
  • 同余式x2≡a (mod m ) 且(a, m)=1有解,则 a 叫做模 m 的平方剩余(或二剩余); 否则,a 叫做模 m 的平方非剩余(或二非剩余)。 是否有解,就看b2-4ac+m*k是否为平方和,但是通常很难用这种方法判断,尤其数很...

    这一章内容比较简单(因为只学了一小部分),估计也就考一道关于欧拉判别条件的应用(与快速平方法一起)
    设 m 是正整数。若同余式x2≡a (mod m ) 且(a, m)=1有解,则 a 叫做模 m 的平方剩余(或二次剩余);
    否则,a 叫做模 m 的平方非剩余(或二次非剩余)。
    是否有解,就看b2-4ac+m*k是否为平方和,但是通常很难用这种方法判断,尤其数很大的时候,所以就有了欧拉判别条件:
    设p是奇素数,(a,p)=1,则
    a是模p的平方剩余的充分必要条件是
    a(p-1)/2=1(mod p)
    a是模p的平方非剩余的充分必要条件是
    a(p-1)/2=-1(mod p)
    并且当a是奇素数p的平方剩余时,同余式恰有两解

    在这里插入图片描述
    最后两页感觉不会考,跳了

    展开全文
  • 同余式ax ≡ c(mod m)

    2021-04-22 18:22:57
    子变形为ax-c=my可以看出原有解当且仅当线性方程ax-my=c有解设g = gcd(a, m)则所有形如ax-my的数都是g的倍数因此如果g不整除c则原方程无解。下面假设g整除c:利用扩展欧几里得算法解出 au + mv =g 一个特解(u0...
  • 次同余方程的解

    2021-05-25 03:09:31
    今天要讨论的问题是解方程,其中是奇质数。 引理: 证明:由费马小定理, 引理:方程有解当且仅当 定理:设满足不是模的二剩余,即无解,那么是二 剩余方程... 题意:求二次同余方程的解。代码:#include #incl...
  • =0(mod m),则n叫做f(x)的次数,记为degf,此时上述同余式又称作模m的n次同余式。 在模m的完全剩余系中,使得同余式成立的剩余个数叫做同余式的解数 同余式求解的基本思路 (1) 求解归约( f(x) (mod m)<= f(x) ...
  • 可以将集合 { 1 , 2 , … , p − 1 } \{1,2,…,p-1\} {1,2,…,p−1}内的 p − 1 p-1 p−1个数分为 p − 1 2 \frac{p-1}{2} 2p−1​组,每组里面的两个数的积与 a a a同余,所以 ( p − 1 ) ! (p-1)! (p−1)!即 a p ...
  • This way 题意: 让你求多项式f(x)=anxn+an...高次同余方程的两个性质 性质一:求解数可将p分成多个互质的数的乘积,对每个数求解数再将解数相乘得到p的解数 性质二:对于%(pr)=0\%(p^r)=0%(pr)=0的方程的解,可以
  • 孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物...
  • The Uniform Recursive Algorithm for Seeking the GCD, Multiplicative Inverse or General Solutions to a Simple Congruence (Outline)Shenghui Su11、School of Information Engineering, University of Science...
  • 剩余详解 以下内容摘自 我的博客:算法竞赛中的数论问题 - 数论全家桶(信奥 / 数竞 / ACM)作者孟繁宇,四万字,十三万字符的竞赛数论完全总结,将会择机发布,敬请期待 ~
  • 这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何... 这是你第一使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Mar
  • 数论 —— 逆元与同余式定理
  • 同余方程详解

    2021-07-27 16:04:39
    同余方程是一个数学方程。 该方程的内容为:对于一组整数Z,Z里的每一个数都除以同一个数m,得到的余数可以为0,1,2,...m-1,共m种。我们就以余数的大小作为标准将Z分为m类。每一类都有相同的余数。 基本...
  • 余数和同余

    2020-12-19 05:01:12
    小升初奥数综合训练(十八+十九)余数和同余【知识要点】1、例如:37÷5=7……2,四者之间的数量关系:被除数=除数×商+余数2、同余的概念:两个整数,...3、同余最基本的性质是:几个同余式(模相同)相加、减、乘、乘...
  • 第二章 同余式同余的定义和基本性质剩余类与完全剩余系三级目录 同余的定义和基本性质 同余 给定一个正整数m,如果用m去除整数a和b所得的余数相同,称a,b对模(数)m同余,记作:a≡b(mod m) 性质 自反性:a≡a...
  • [转]同余即相关性质

    2021-03-17 11:13:30
    一、同余我们来了解一下什么是“同余”。简单来说就是,如果两个数都除以某个数能够有相同的余数,那么我们就说这两个数“同余”。不过这次我们用严谨的数学概念来表述:两个整数 a,b,若它们除以整数 m所得的余数...
  • 纯线性同余随机数生成器1. 线性同余随机数生成器介绍:古老的LCG(linear congruential generator)代表了最好最朴素的伪随机数产生器算法。主要原因是容易理解,容易实现,而且速度快。 LCG 算法数学上基于公式: X(n...
  • 【知识要点】1、例如:37÷5=7……2,四者之间的数量关系:被除数=除数×商+余数2、同余的概念:两个整数...3、同余最基本的性质是:几个同余式(模相同)相加、减、乘、乘方仍然同余。【典型例题】例1、两个整数相除...
  • 模和同余定理

    千次阅读 2021-01-11 23:37:12
    比如: 23÷5=4.....3 16÷5=3.....1 (23X16)÷5=73.....(3=3X1) 同余定理 若两个整数a、b被自然数m除有相同的余数,那么称a、b对应模m同余,记为同余式a≡b (mod m)。由同余的性质,我们可以得到一个推论:若a、b...
  • 同余

    2021-04-13 16:17:07
    本博客主要介绍同余这一内容。当然,本博客仅代表作者自身观点如有错误,请您指出。   同余,是数论中一个特别重要的一部分,而且编程中需要用到数论的大部分都是同余相关的问题。所以本篇博客就来介绍一下关于...
  • 肖丽【摘要】本研究基于观点视角,例析同余定理在小学数学竞赛中的应用,探讨运用其解决小学奥数问题的优越性。【关键词】小学数学竞赛 同余定理 应用【中图分类号】G623.5【文献标识码】A 【文章编号】2095-3089...
  • 4.4 求解同余方程

    2021-01-02 11:47:46
    4.4 求解同余方程 线性同余方程 ax≡b (mod m),其中,m∈N+,a,b∈N,x为变量,这样的方程称为线性同余方程 ax \equiv b\ (mod\ m),其中,m \in {N}^{+},a,b \in N,x为变量,这样的方程称为线性同余...
  • 浅谈质数与同余

    2021-05-22 14:59:53
    浅谈质数与同余 一、质数 定义:除了1和本身两个数都不能被整除的自然数叫做质数,否则为合数。 0和1既不是质数也不是合数,最小的合数是4, 最小的质数是2,是唯一的偶质数,质数有无穷多个 质数分布定理: 对正...
  • 同余概述(同余定理)

    2021-01-26 22:36:31
    如果a=b(mod m),那么我们称a,b关于模m同余,这个式子叫做同余式。 定理1.若a=b(mod m),且c=d(mod m),那么ax+cy=bx+dy(mod m),同余式满足加法 定理2.若a=b(mod m),且 c=d(mod m),那么,ac=bd(mod m),同余式满足...
  • 国考行测数量关系之余数同余问题解题诀窍在公务员考试的数量关系模块中,余数相关问题是考查的传统重点,也是令很多考生犯难的一种题型。硕文公务员考试研究中心针对常见的几类题目给予分析,帮助考生轻松解决余数...
  • Python求解二方程

    2020-12-30 09:52:14
    讲解对象:Python求解二方程作者:融水公子 rsgz源代码:#!/usr/bin/env python3import matha = int(input("Enter value of a: "))b = int(input("Enter value of b: "))c = int(input("Enter value of c: "))d ...
  • 同余理论在软件编程中的应用.pdf设计通讯 2oo7 No.2同余理论在软件编程中的应用石军摘 要 简要介绍同余理论的概念、性质、四则运算等基本知识,通过几个...关键词 同余 算法 校验码 计算机应用1.3 同余式的性质0...
  • 解同余方程组:x≡6(mod11) x≡3(mod 8 ) x≡11(mod20)等效于同余式组(x==6 mod 11 (#1#)x==3 mod 8 (#2#)x==11 mod 4 (#3#)x==11 mod 5 (#4#)其中,用==表示同余号.)即求他们的解集的交集.其中 (#2#)的解集是(#3#)的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 156,270
精华内容 62,508
关键字:

高次同余式