(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211115726.0 (22)申请日 2022.09.14 (71)申请人 上海交通大 学 地址 200240 上海市闵行区东川路80 0号 (72)发明人 张文甲　何祖源　王绍萌　 (74)专利代理 机构 上海汉声知识产权代理有限 公司 3123 6 专利代理师 胡晶 (51)Int.Cl. H04L 9/30(2006.01) H04L 9/32(2006.01) (54)发明名称 基于伊辛模型的大整数分解问题映射方法 及系统 (57)摘要 本发明提供了一种基于伊辛模型的大整数 分解问题映射方法及系统， 包括： 对二进制乘法 竖式构建辅助块， 对每块所得到的损失函数进行 形式上的等价替换， 满足伊辛模型的形式要求， 将得到伊辛模 型的哈密顿量表达式； 根据不同自 旋状态下哈密顿量的取值及其范围的分布特征， 使其能够跳出局部最优解， 直至伊辛模型到达自 旋基态； 获取两个素因子信息， 实现大整数分解， 进一步由欧拉公式和密码系统中开放的公钥得 到RSA加密算法中的私钥， 使用私钥将密文信息 转换为原始明文信息， 实现对RSA密码系统的破 解。 本发明完整地表现了一种将大整数分解问题 映射为伊辛模型求 解问题的一般流 程。 权利要求书3页 说明书9页 附图5页 CN 115514488 A 2022.12.23 CN 115514488 A 1.一种基于伊 辛模型的大整数分解问题映射方法， 其特 征在于， 包括： 步骤S1： 对二进制乘法竖式中的每个 中间项引入辅助变量， 构建辅助块， 对每块所得到 的损失函数进行形式上 的等价替换， 使其满足伊辛模型 的形式要求， 将各块的损失函数相 加并作变量代换， 化简得到伊 辛模型的哈密顿量表达式； 步骤S2： 根据不同自旋状态下哈密顿量的取值及其范围的分布特征， 采取由少到多地 更新自旋状态的技术方案， 并在特定情况下改变判别条件， 使其能够跳出局部最优解， 直至 伊辛模型到 达自旋基态； 步骤S3： 获取两个素因子信息， 实现大整数分解， 进一步由欧拉公式和密码系统中开放 的公钥得到RSA加密算法中的私钥， 使用私钥将密文信息转换为原始明文信息， 实现对RSA 密码系统的破解。 2.根据权利要求1所述的基于伊辛模型的大整数分解问题映射方法， 其特征在于， 在所 述步骤S1中： 针对每个辅助块产生特定形式的损 失函数， 代入边界条件， 并对每个损 失函数进行形 式上的等价替换， 使其不包含二次项以上的高次项， 满足伊辛模型的形式要求， 进而将全部 的损失函数相加、 变量代换、 化简， 得到伊辛模 型的哈密顿量表达式， 提取出相互作用矩阵J 和外部磁场向量h， 将大整数分解问题转 化为寻找该伊 辛模型自旋基态的求 解问题； 所述的转化过程是通过固定流程实现的， 适用于任意大整数， 在计算机内程序化完成， 针对特定的大整数， 不需要单独分析或推导中间过程， 能够直接得到对应的伊 辛模型； 所述的辅助变量是依据两个因数的二进制乘法竖式中的每个中间项aibj逐个引入的， 即yi,j和zi,j， 其中yi,j为上方辅助块中的二进制变量相加所得的最低位结果， zi,j为右方辅 助块中的二进制变量相加所 得的进位， aibj、 yi,j、 zi,j三项构成一个辅助块， 产生损失函数； 所述的损失函数的形式为Fi,j＝(aibj+yi,j+zi,j‑yi+1,j‑1‑2zi‑1,j)2， 等价替换后的形式为 所述的等价替换后的损 失函数不含有二次以上的项， 无需降次操作， 并且将其全部相 加、 化简、 变量代换后所得哈密顿量表达式中， 变量的系数大小被限制在预设范围， 所得伊 辛模型的相互作用矩阵J和外 部磁场向量h的元 素大小也是有限范围的。 3.根据权利要求2所述的基于伊 辛模型的大整数分解问题映射方法， 其特 征在于： 步骤S1.1： 将所要分解的目标 大整数表示 为二进制形式， 记录位数为 w； 步骤S1.2： 假设目标大整数的两个因数的二进制位数分别是k和h， 二进制形式从高位 到低位分别为a1,a2,…,ak和b1,b2,…,bh； 步骤S1.3： 对于两个因数的二进制乘法竖式中的每个中间项aibj， 逐个引入辅助变量 yi,j和zi,j， 并将aibj、 yi,j、 zi,j三项作为 一个辅助块； 步骤S1.4： 每个辅助块产生一个损失函数， 对于边界上的辅助块， 根据损失函数的形式 引入额外的辅助变量， 并代入边界条件； 步骤S1.5： 对每块得到的损失函数进行 形式上的等 价替换， 使其只包 含二次项； 步骤S1.6： 将各个替换后的损失函数相加并进行变量代换， 然后化简得到伊辛模型的 哈密顿量表达式； 步骤S1.7： 表达式中的各个变量作为自旋节点， 分别提取二元二次项系数和一次项系权　利　要　求　书 1/3 页 2 CN 115514488 A 2数组成伊 辛模型的相互作用矩阵J和外 部磁场向量h， 并将其 余的不变量部分的和记为C 。 4.根据权利要求1所述的基于伊辛模型的大整数分解问题映射方法， 其特征在于， 在所 述步骤S2中： 步骤S2.1： 随机产生初始自旋状态， 根据得到的伊 辛模型计算出哈密顿量； 步骤S2.2： 每次改变x个自旋， x的初始值为1， 随着同一个自旋状态的改变次数增多， 使 x逐渐增大； 步骤S2.3： 若改变后的哈密顿量减小， 则接受这次对自旋状态的改变， 并将x重置为1， 否则继续保持改变前的自旋状态； 步骤S2.4： 若x到达一定值仍未被重置， 则降低接受自旋状态改变的判别标准， 直到x被 重置； 步骤S2.5： 重复流程步骤S2.2 ‑步骤S2.4， 直到自旋状态对应 的哈密顿量为 ‑C， 说明此 时伊辛模型已到 达自旋基态， 包 含目标大整数的两个素因子信息， 则实现大整数分解。 5.根据权利要求 4所述的基于伊 辛模型的大整数分解问题映射方法， 其特 征在于： 所述的降低接受自旋状态改变的判别标准， 通过设置一个跳出局部最优解所需的判别 能量E_jump， 使当前自旋状态所对应的哈密顿量不再是计算得到的， 而是将其直接设为E_ jump， 然后重复迭代过程， 直至再次更新哈密顿量得以实现。 6.一种基于伊 辛模型的大整数分解问题映射系统， 其特 征在于， 包括： 模块M1： 对二进制乘法竖式中的每个 中间项引入辅助变量， 构建辅助块， 对每块所得到 的损失函数进行形式上 的等价替换， 使其满足伊辛模型 的形式要求， 将各块的损失函数相 加并作变量代换， 化简得到伊 辛模型的哈密顿量表达式； 模块M2： 根据不同自旋状态下哈密顿量的取值及其范围的分布特征， 采取由少到多地 更新自旋状态的技术方案， 并在特定情况下改变判别条件， 使其能够跳出局部最优解， 直至 伊辛模型到 达自旋基态； 模块M3： 获取两个素因子信息， 实现大整数分解， 进一步由欧拉公式和密码系统中开放 的公钥得到RSA加密算法中的私钥， 使用私钥将密文信息转换为原始明文信息， 实现对RSA 密码系统的破解。 7.根据权利要求6所述的基于伊辛模型的大整数分解问题映射系统， 其特征在于， 在所 述模块M1中： 针对每个辅助块产生特定形式的损 失函数， 代入边界条件， 并对每个损 失函数进行形 式上的等价替换， 使其不包含二次项以上的高次项， 满足伊辛模型的形式要求， 进而将全部 的损失函数相加、 变量代换、 化简， 得到伊辛模 型的哈密顿量表达式， 提取出相互作用矩阵J 和外部磁场向量h， 将大整数分解问题转 化为寻找该伊 辛模型自旋基态的求 解问题； 所述的转化过程是通过固定流程实现的， 适用于任意大整数， 在计算机内程序化完成， 针对特定的大整数， 不需要单独分析或推导中间过程， 能够直接得到对应的伊 辛模型； 所述的辅助变量是依据两个因数的二进制乘法竖式中的每个中间项aibj逐个引入的， 即yi,j和zi,j， 其中yi,j为上方辅助块中的二进制变量相加所得的最低位结果， zi,j为右方辅 助块中的二进制变量相加所 得的进位， aibj、 yi,j、 zi,j三项构成一个辅助块， 产生损失函数； 所述的损失函数的形式为Fi,j＝(aibj+yi,j+zi,j‑yi+1,j‑1‑2zi‑1,j)2， 等价替换后的形式为权　利　要　求　书 2/3 页 3 CN 115514488 A 3