计算模 m 的 k 次根

2019-04-14 21:30发布

站内文章 / 模拟电子
9399 0 1669
真心说声，不明白古人为什么那么聪明，由一个最简单的带余除法引申出如此之多的智慧... 题目：已知 x^k = b ( mod m )  ， ( b, m ) = 1, ( E(m), k ) = 1;  告诉你 k, b, m 的值， 要你求：x 的值  储备知识：(1) 如果b^k = 1 ( mod m )，则 ( b^k )^t = 1 ( mod m ) , t = 1, 2, 3, ....                     (2) 如果( a, b ) = 1 , 则由整数的整除性质知必定存在整数 s, t 使得 as + bt = 1 一定成立... 求：由( E(m), k ) = 1 知道存在整数 s，t 使得 k * t = E(m) * s + 1; 成立...
        令 x = b^t ; 则(b^t)^k = b^(E(m)*s+1) = b * b^(E(m)*s)  =  b * (b^E(m))^s         由欧拉定理 b^E(m) = 1 ( mod m ) , ( b,m ) = 1;   则 (b^E(m))^s = 1 ( mod m ),         则 b *(b^E(m))^s = b ( mod m ),所以最终需要求的 t 。         根据 k * t = E(m) * s + 1 ， 求 m 的欧拉函数E(m), 再解二元一次不定方程，解的最后的 t 值..         再通过快速幂求得 b^t ，注意一点，一定要解的 t 为最小正数解..    附证明储备知识(1): 57(312868261)  20:56:51
一开始学，多写开来
 a=1 mod m，则a=km+1，那么a^n=(km+1)^n
展开来，全是m的倍数项，就多出一个1      

热门文章