数论（求逆元） 在密码学中我们经常需要用到逆元，尤其在RSA公钥密码体制中。下面简介一下求逆元的通用方法，广义欧几里得除法的逆运算。如果a,m互素的话，那么根据欧几里得除法，最终会得到余数为1，此时我们可以消去中间变量，最终得到sa+tm=(a,m)=1，两边同时除以m可以得到sa=1(mod m)，显而易见可以得到s是a模m的逆元。求逆元步骤就分为两部：1.判断a，m是否互素；2.根据广义欧几里得除法计算逆... 随笔 2024-08-11 26 点赞 0 评论 39 浏览
