一种基于 Complicated Concept of Feast 的加密方式

作者 Constantine 博士 Sun Ping 博士 Justin-Saber 博士。

2023 年 9 月 16 日。

摘要

#略

关键词

#略

研究背景及目的

在 2022 年进行的星战中，因为我军通讯系统遭敌人窃听并破译，导致敌人在决定是否反击时，在 45% 的情况中完美发现了我军的伏兵，从而简单做出不反击的命令。从而减小了敌方舰队的伤亡。

事后我们发现，敌人在监听我们的通讯时，使用了宇宙射线使我军密码直接被转化为明码，导致我军信息泄露。经查，是因为我们先前使用的 Method of Four Russians 算法执行被敌军破译。为了使军事通讯更有保障，我们发明了 Complicated Concept of Feast 这一加密模式。

研究内容

#略

研究结论

在对于一条通讯信息进行加密前，我们先建出它的哈夫曼树，其次我们对它进行染色，由于没有要求染色时保证相邻两个节点颜色不同，我们一定能用两个以内的颜色染色。

随后我们对所有内容的哈夫曼编码进行分组，求出他们的因数和——显然注意到小于 $n$ 的质数的幂的倒数和量级为 $O(\ln \ln n)$，所以我们可以设计两种算法，用时间复杂度的高的算法进行计算，用时间复杂度低的算法进行验证。

随后我们利用海伦公式求出它们所有可以构成的三角形的面积，但是我们不要求它们能构成三角形，于是可能结果是 nan。

随后我们对每一个数使用 unsigned short 进行左移、右移、疑惑，利用自然溢出进行加密，虽然这一步很多余。

随后我们通过二分（注意到这一步的变量必须要写 h,g,m）求出它们所构成的序列使序列中数两两之间的差大于 $m$ 的数的对数大于等于 $k$ 的最小的 $m$。注意到我们有 $\log n+\log A=\log nA$，所以时间复杂度是 $O(n\log nA)$

实现过程要用上 union 和 mkdir。并要使用链表维护。

随后我们只要向信息传递目标发送 $m$ 和 $k$ 就行了。

收信人收到 $m$ 和 $k$ 时，先建图，利用拓扑排序和 $\sum\limits_{i=0}^n 16^i\times x_i$ 这一公式求出我们要发送的信息就即可。注意到在计算 $16^i$ 的时候，为了不被对方探查出我们使用了快速幂，我们要使用时间复杂度为 $O(n)$ 的快速幂，达到加密的作用。

研究展望

#略

致谢

#略

参考文献

CSP-J 2023 初赛、CSP-S 2021、2022、2023 初赛，CSP-S 2022 复赛 T3。