网站首页 密码学

Paillier同态加密算法总结

发布时间:2021-4-7 9:10 Wednesday编辑:admin阅读(703)

    一、密码学知识总结

    1.卡迈克尔数

    对于所有与n互质的正整数b,都有同余式b^(n-1)≡ 1 (mod n)成立,则称合数n为Carmichael数。

    卡迈克尔数有至少3个正素因数

    2.费马小定理

    设p为一素数,对于任意整数a,有a(p-1)≡ 1 (mod p)。

    费马小定理可得,若n为素数,则对任意整数b,且b和n互素,都有bn-1(mod n) ≡1。因此,若存在整数b,使得bn-1(mod n)≡1不成立,则n是一个合数。


    3.欧拉函数

    正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)


    4.剩余类(同余类)

    设模为n,则根据余数可将所有的整数分为n类,把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类,记作[a]。并把a叫作剩余类[a]的一个代表元。

    5、既约剩余系


    6.Carmichael’s function


    7、二项式定理


    二、paillier同态加密算法

    1.密钥产生

    2、加密过程

    3、解密过程


    4、正确性证明


    其中