基于有限域可逆仿射的数字ID生成方案
把一个递增序列映射为一个相同空间的乱序序列,用于乱序ID生成
基于RSA算法的性质:
- RSA算法涉及三个参数,n、e1、e2,其中,n是两个大质数p、q的积。
- 根据欧拉函数,求得 rn=(p-1)(q-1)。
- e1和e2是一对相关的值,e1可以任意取,但要求e1与rn互质,再选择e2,要求e1e2 ≡1(mod rn)。(模反元素e2存在,当且仅当e1与rn互质)
A=B^e1 mod n
B=A^e2 mod n
B即为加密前的数据,A为加密后的数据,A和B是双射的,也即B通过RSA的加密算法得到唯一的A,A通过RSA解密算法获得唯一的B
例:
要求生成一个6位数字的乱序ID,则n为小于等于999999的数,这个数要求尽量接近999999,且可以分解成两个质数之积。查质数表可以找到两个质数分别为p=757, q=1321,可以使 n=999997,为保证e1与(p-1)*(q-1)
(rn=997920)互质,可以取 e1=13, 11, 7 等,不要取太大的值,否则计算pow(a,e1)数值较大,CPU性能和精度不好控制,同时 pow(a,e1)% n
与循环 e1-1
次 a=(a*a0)%n
的结果是一样的,后者的实现不会产生大数。
可以得到公式:A = pow(B,13) % 999997
此外,可以根据扩展欧几里得算法可以计算模反元素e2
如果不要求逆运算,可以进行简单的ID散列处理:
f(x) = (ax + b) % R, 其中a可以取一个比较大的素数,b随便找个,R是输出的id范围。
sentry = pow(10, 7)
if uid < sentry:
uid = (uid * 2654435769) % sentry
数学原理:
欧拉函数:
任意给定一个正整数,在小于等于n的正整数中有多少个数与n构成互质关系,这个数即为欧拉函数r。当n是质数时,r= n-1,因为质数与小于它的每一个数都构成互质关系。当n可以分解为两个互质整数p,q之积时,r=(p-1)(q-1)。
欧拉定理:
如果两个正整数a,b互质,则b的欧拉函数r保证下面等式成立:
a^r≡1(mod b) (1)
当b是质数时,r= b-1,所以欧拉定理可以改写成
a^(b-1)≡1(mod b) (2)
这个公式就是欧拉定理的特例,也就是费马小定理。
模反元素:
如果两个正整数a和n互质,那么一定可以找到一个整数b,使得 a * b≡1 (mod n),此时我们称整数b为a的模反元素。通过欧拉定理得到 a^r=aa^(r-1) ≡1 (mod n),显然a^(r-1)即为模范元素b。
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com
文章标题: 基于有限域可逆仿射的数字ID生成方案
文章字数: 693
本文作者: Jun
发布时间: 2021-04-14, 21:13:51
最后更新: 2021-04-14, 22:32:30
原始链接: http://yoursite.com/2021/04/14/基于有限域可逆仿射的数字ID生成方案/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。