基于背包问题的MC矩阵覆盖密码体制

设A是整数环上的n阶非负方阵,s是一非负整数,求解xi∈{0,1},1≤i≤n,使得XAXT=s,其中X=(x1,x2,…,xn),XT是向量X的转置,是一个公认的NP完全问题[1]。论文就这此问题,利用整数位数及其整数位数上的数字是否为零这一特征建立了一个公钥密码算法。