关于扩展欧几里德算法我要用扩展欧几里德算法计算-n*n' % r=1等式中的n',其中n为已知非负奇数,r=2^k,想问下 -n*n'%r=n*n'%r=1 是否成立,在运算过程中,是不是会有负号产生,计算出来的n'会不会是负数,如果是,忽略了它的负号会不会有影响?以上式子可否化成,n'=-n^(-1)%r=(r-n)^(-1)%r 其中n^(-1)是不是n的导数,还是什么?如果有详解,小弟感激不尽|!
问题描述：
关于扩展欧几里德算法
我要用扩展欧几里德算法计算-n*n' % r=1等式中的n',其中n为已知非负奇数,r=2^k,想问下 -n*n'%r=n*n'%r=1 是否成立,在运算过程中,是不是会有负号产生,计算出来的n'会不会是负数,如果是,忽略了它的负号会不会有影响?
以上式子可否化成,n'=-n^(-1)%r=(r-n)^(-1)%r 其中n^(-1)是不是n的导数,还是什么?如果有详解,小弟感激不尽|!
答
负号当然不能丢掉。
1 % 4 = 1
3 % 4 = -1
这俩不相等。
答
-n*n'%r=n*n'%r=1不成立
n'如果算出是负数不能忽略符号
n'=-n^(-1)%r=(r-n)^(-1)%r可以化
其中n^(-1)是不是n的倒数?是数论倒数
n^(-1)*n被模r除余1