[密码学入门]仿射密码(Affine) - 码农知识堂

[密码学入门]仿射密码(Affine)
加密算法y=(ax+b)mod N

解密算法x= $a^{-1}$ *(y-b)mod N(此处的 $a^{-1}$ 为a关于N的乘法逆元，不是幂的概念）

同余的几个性质：

1，若 $a\equiv b modN$ ，对于任意整数，

$(a+c)\equiv (b+c)modN$

$\left ( a-c \right )\equiv \left ( b-c \right )modN$

$\left ( a*c \right )\equiv (b*c)m odN$

在模运算下，除法有些特殊：

若 $\left ( c,N \right )=1$ , $\left ( a*c \right )\equiv (b*c)m odN$ ，则 $a\equiv b modN$ 。

若 $\left ( a*c \right )\equiv (b*c)m od\left ( N*c\right )$ ，则 $a\equiv b modN$ 。

逆元的定义：

$a*a^{-1}\equiv 1modN$ ,则称 $a^{-1}$ 是关于N的逆元。

注意这里 $a^{-1}$ 是正整数。

逆元是一组解，不光是一个数。例如3*3%8=1，3*11%8=1,3*19%8=1，任何3+8*k的整数都是3模8的乘法逆元。

如何求 $a^{-1}$ ，涉及的知识挺多，还没想好怎么写，丢番图方程，贝祖定理（又译裴蜀定理），扩展欧几里得算法。 $a^{-1}$ 存在需要满足（a,n）=1。

python中可以这么求逆元
```
pow(a,-1,n)
```
相关阅读:
leetcode-每日一题-二进制表示中质数个计算置位(简单,popcount算法)
在 IDEA 中用 Nacos2.1.0 源码启动集群模式并调试
 vue实现简单的购物车案例
 geohash学习
 不指定时区会踩坑：MySQL Java 驱动升级遇到的 Bug 分析
 这两个工具能批量PDF转图片，建议收藏使用
 外包干了3天，技术退步明显.......
【POJ No. 2352】数星星 Stars
还在直接用localStorage么？全网最细：本地存储二次封装（含加密、解密、过期处理）
Effective Modern C++[实践]-＞优先选用别名声明，而非typedef
原文地址：https://blog.csdn.net/amber_o0k/article/details/133090969