第八章模p平方剩余-智能信息处理研究中心.pdfVIP

第八章 模p平方剩余 0011 0010 1010 1101 0001 0100 1011 张志强 智能信息处理研究中心 模p与原根 0011 0010 1010 1101 0001 0100 1011 p- • 费马小定理告诉我们，如果a 与p互素，则有a 1≡1(mod p) – 事实上不只有a 的p-1幂与1模p 同余，还存在其他的 3 幂次与1模p 同余，例如2 ≡1(mod 7) – 那么对于给定的a ，最小的与1模p 同余的幂次是多少 呢？ • 我们称这种最小的指数为a模p 的次数( 或阶)， e e p(a)=(使得a ≡1(mod p)的最小指数e ≥1) • 例，找出2模7 的次数( 阶) 1 – 计算2 的各次幂对模7 的最小正剩余，2 ≡2(mod 7) 2 3 ， 2 ≡4(mod 7) ， 2 ≡1(mod 7)，则有e (2)=3 7 • 由费马小定理可知e (a) ≤p-1 p 智能信息处理研究中心 2 模p与原根 0011 0010 1010 1101 0001 0100 1011 p=5 p=11 • 两个观察 1 1 ≡1(mod 5) 11≡1(mod 11) 24 ≡1(mod 5) 10 e 2 ≡1(mod 11) – 使得a ≡1(mod 34 ≡1(mod 5) 2 35 ≡1(mod 11) p)的最小指数e 4 ≡1(mod 5) 45 ≡1(mod 11) 整除p-1 p=7 55 ≡1(mod 11) 11≡1(mod 7) 610≡1(mod 11) – 总有一些a 需要 23 ≡1(mod 7) 710≡1(mod 11) 指数p-1 36 ≡1(mod 7) 810≡1(mod 11) 43 ≡1(mod 7) 95 ≡1(mod 11) 56 ≡1(mod 7) 2 2 10 ≡1(mod 1