「密码学」-Merkle-Hellman

背包密码体制

• 加密：
  选择任何一个超递增集。陷门有任意大于的素数和任意小于的整数组成，这两个数和集合都是保密的。公开的整数集是,其中。二进制明文的加密操作为。整数是密文。
• 解密：
  找到。因为是质数，一定存在。计算。得到这使得
  
  因为集合是超递增集，所以很容易定位明文位

超递增集：每一个整数都大于它前面整数之和
陷门：超递增集必须被隐藏在陷门后
：是a在模的情况下的逆元

习题

• 给定一个超递增集和素数以及一个整数，构造一个加密集。对二进制消息进行加密；并对密文进行解密。

依题意可知:

加密过程：
根据，可以得到
密文。可以得到

解密过程：
通过扩展欧几里得可以得到在模的情况下的逆元
所以

扩展欧几里得：

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
   if(b==0)
   {
       gcd=a;
       x=1;
       y=0;
   }
   else
   {
       exgcd(b,a%b,gcd,y,x);
       y-=x*(a/b);
   }
}
ll inv(ll a,ll b)
{
   ll gcd,x,y;
   exgcd(a,b,gcd,x,y);
   return gcd==1?(x%b+b)%b:-1;
}
int main( )
{
   ll a,b;
   while(~scanf("%lld%lld",&a,&b))//a是被模数,b是模数,-->a%b
   {
       printf("%lld\n",inv(a,b));
   }
   return 0;
}