整数分解

摘要： 借助加窗技术和模整数的陪集表示技术,在加法的近似编码表示基础上给出Shor算法量子线路的整体优化和资源估计,并对设计的量子线路进行了仿真实验。借助加窗技术和模整数的陪集表示技术可以有效减少Toffoli门的数目以及降低整个量子线路的深度,其中Toffoli门数目为0.18n^(3)+0.000465n^(3)log n,线路深度为0.3n^(3)+0.000465n^(3)log n。由于采用加窗的半经典傅里叶变换,使得空间资源代价为3n+O(log n)个量子比特。在增加少量近似误差(误差可以随着填充数目的增加呈指数减小)的前提下,实现了时间空间资源代价的折衷。

摘要： 非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的.Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统.文中提出基于Grover搜索算法并结合经典预处理实现整数分解.首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率.仿真结果验证了使用Grover算法求解素因子P和Q的可行性.文中实现了在搜索空间为16且一次G迭代条件下以近78％的成功概率搜索到目标项.文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异.通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显.

摘要： 设D是大于2且不含6k+1型素因数的无平方因子正整数.用初等数论方法证明了不定方程x3±33m=Dy2有正整数解(m,x,y)的充要条件是方程Da2=3(3m±1/2)2-1有正整数解(m,a),且D的奇素因子p都满足p≡11(mod 12).

摘要： 通过对文献资料的归类分析,结合大整数分解理论和实践的具体发展,从宏观层面将大整数分解的历程划分为四个阶段并归纳出了每个阶段的基本特征,同时结合国内研究情况总结出了国内研究的特点,指出了国内外研究的差别以及国内研究的某些局限性.文章最后还介绍了最近几年新发现的基于二叉树研究方法的特色及其取得的成果,展示了一些算例并揭示了未来的相关研究方向和内容.文章可作为研究大整数分解算法的参考.

摘要： 通过对文献资料的归类分析,结合大整数分解理论和实践的具体发展,从宏观层面将大整数分解的历程划分为四个阶段并归纳出了每个阶段的基本特征,同时结合国内研究情况总结出了国内研究的特点,指出了国内外研究的差别以及国内研究的某些局限性。文章最后还介绍了最近几年新发现的基于二叉树研究方法的特色及其取得的成果,展示了一些算例并揭示了未来的相关研究方向和内容。文章可作为研究大整数分解算法的参考。

摘要： 分析一个费马数分解算法中的冗余步骤,给出相应的优化结果.针对相关文献述及大费马数表示困难的问题,给出利用GMP大数运算库表示大费马数的一种方法.基于数学软件Maple,进行解析费马数小因数的试验.试验表明,优化后的算法可提高计算效率.

摘要： 讨论了一个非线性欧拉方程Φ(mn)=5Φ(m)+8Φ(n)+16的解.利用整数的分解以及Euler函数Φ(n)的相关性质,给出了其全部的49组解.

摘要： 讨论了一个包含完全数的非线性Euler函数Φ(n)的方程Φ(mn)=Φ(m)+28Φ(n)+28的解.利用完全数的性质、整数的分解以及Euler函数Φ(n)的性质给出方程的全部34组解.

摘要： 讨论了一个有关Euler函数Φ(n)的非线性方程Φ(mn)=7Φ(m)+8Φ(n)+16的解,利用整数的分解以及Euler函数Φ(n)的性质给出了其全部的52组解.%The positive integer solutions of a nonlinear equation Φ(mn) =7Φ(m) + 8Φ(n) + 16 on Euler function was discussed.And all the 52 positive integer solutions of that equation were given by integer factorization and the properties of Euler function Φ(n).

摘要： 在数论中,整数分解是一个古老的难解性问题,至今没有一个好的解决方法,而当今世界上,应用最为广泛的RSA密码体制,其安全性就建立在大整数分解的难解性之上,本文用自然数中两个最小的邻接素数2*3组成(mod6)等差数列建立的数学模型"薛氏筛法",是把自然数进行分类研究,从而发现两种属性的大整数M与相同属性关系的素数因子p与q,以及这种因子与序数N的同步互数关系形成的筛法,再根据因子P表现出显规律、潜规律则的性质,且判定与分解时并非直接对整数M进行实质计算,而是利用序数N因子p与整数M之间所存在的同步关系,通过对序数位置的计算,获得"序数位置同步判定素数与分解整数"的新方法.

摘要： 本文扼要介绍了整数分解的困难性及其在公钥密码体制上的应用.

摘要： 整数分解是数论中的一个非常古老的难解性问题,而当今世界上最有名且广泛使用的RSA公钥密码体制,其安全性是基于整数分解的难解性.迄今为止,最有希望破解RSA的方法就是Shor的量子算法.本文利用RSA不动点性质,基于量子Fourier变换和变量代换,提出一个新的攻击RSA的量子算法,该算法不需要分解jn而从RSA密文C直接恢复其明文M.该算法与Shor算法相比,需要更少的量子位,且成功概率大于1/2.文章最后还将新算法的资源消耗情况与Shor算法的进行了对比.

摘要： 考虑定义在模数N的剩余类环上的矩阵所构成的矩阵环上的求根问题的困难性,本文设计了一个数字签名算法,证明了攻击者能够成功伪造一个签名当且仅当攻击者能够求解矩阵环上的求根问题.对矩阵环上的求根问题的困难性进行了分析,在一种特殊情况下,证明了矩阵环上的求根问题与整数分解问题是等价的.分析表明,该数字签名算法是一个高效安全的签名算法.

摘要： 本发明属于集成电路的分频器技术领域，具体为一种基于特征状态反馈的整数和半整数分频器。本发明的分频器包括时钟相位反转器、N位二进制计数器、输出时钟选择器和反馈控制器；反馈控制器包括电平型特征状态译码器、触发型特征状态译码器、电平型反转器和触发型反转器。本发明通过由分频系数确定的特征状态进行反馈，对输入时钟进行相位处理，使二进制计数器在待分频时钟指定的边沿触发，并选择与分频系数对应的计数位输出作为分频时钟。本发明仅需对二进制计数器的接口信号进行处理而无需改变其内部结构，具有设计简单和通用性强的优点，它不仅能够实现完备的整数和半整数分频，而且还能够以0.5个输入时钟周期为精度调节分频时钟的占空比。

摘要： 使用QR因数分解及修改的K-best算法来检测从多个发射天线(1、2、3、4)向多个接收天线发射的符号，所述K-best算法涉及实值分解及排序。首先，对于第一天线(4)，计算所接收的信号与第一天线符号的多个候选(212、214、...、242)之间的部分距离。然后，对于所述算法的每一步骤，在相应第一选择器中选择具有较小部分距离的候选(220、222、224、226)，在相应第一块中确定接收的信号与具有不同的正交相位值的新的多个候选(244、246、248、...)之间的距离，在相应第二选择器中选择具有较小距离的候选(244、254、260、262)，且在相应第二块中确定接收的信号与具有不同的同相值的新的多个候选之间的距离。最后，识别器对由所述算法的最后步骤输出的候选(272、274、...、291)中具有最小距离的符号(274)进行检测。

摘要： 本发明属于集成电路的分频器技术领域，具体为一种基于特征状态反馈的整数和半整数分频器。本发明的分频器包括时钟相位反转器、N位二进制计数器、输出时钟选择器和反馈控制器；反馈控制器包括电平型特征状态译码器、触发型特征状态译码器、电平型反转器和触发型反转器。本发明通过由分频系数确定的特征状态进行反馈，对输入时钟进行相位处理，使二进制计数器在待分频时钟指定的边沿触发，并选择与分频系数对应的计数位输出作为分频时钟。本发明仅需对二进制计数器的接口信号进行处理而无需改变其内部结构，具有设计简单和通用性强的优点，它不仅能够实现完备的整数和半整数分频，而且还能够以0.5个输入时钟周期为精度调节分频时钟的占空比。

摘要： 一种可配置任意整数半整数分频器装置及方法，属数字分频技术领域，装置包括模式选择及输出部分、配置数据锁存部分和分频计数部分，其特征在于模式选择及输出部分分别与配置数据锁存部分和分频计数部分相连接；其方法步骤为：1、开始；2、输入分频系数及模式选择信号；3、施加有效复位信号，锁存分频系数及模式选择信号；4、输入待分频信号，分频器工作，输出分频信号；5、判断是否要改变分频系数或者分频模式。本发明可实现任意整数或半整数的分频功能，在整数分频时可根据需求输出等占空比和不等占空比两种分频信号，分频器的分频系数和输出信号的占空比可以根据情况进行调节，从而提高分频器的灵活性，扩大其使用范围。

摘要： 使用QR因数分解及修改的K-best算法来检测从多个发射天线(1、2、3、4)向多个接收天线发射的符号，所述K-best算法涉及实值分解及排序。首先，对于第一天线(4)，计算所接收的信号与第一天线符号的多个候选(212、214、...、242)之间的部分距离。然后，对于所述算法的每一步骤，在相应第一选择器中选择具有较小部分距离的候选(220、222、224、226)，在相应第一块中确定接收的信号与具有不同的正交相位值的新的多个候选(244、246、248、...)之间的距离，在相应第二选择器中选择具有较小距离的候选(244、254、260、262)，且在相应第二块中确定接收的信号与具有不同的同相值的新的多个候选之间的距离。最后，识别器对由所述算法的最后步骤输出的候选(272、274、...、291)中具有最小距离的符号(274)进行检测。

摘要： 本发明公开了一种新的基于整数分解问题的代理签名及验证方法，其步骤是：在网络运行之前，原始签名人和代理签名人首先生成自身的公钥和私钥，并发布公钥；当具有签名请求时，原始签名人生成委托书，并基于变色龙哈希函数和普通数字签名算法计算签名授权发送给代理签名人；代理签名人对收到的签名授权进行有效性验证，若有效，则基于变色龙哈希函数碰撞性生成代理签名，而无需对消息再进行数字签名；当验证者收到委托书和代理签名后，首先验证委托书是否有效，确认有效后，再验证代理签名的有效性。本发明的应用，代理签名处理效率高、代理签名长度短，适用于计算能力和网络带宽比较受限的移动网络、无线网络等环境中。

摘要： 本发明提供了一种基于伊辛模型的大整数分解问题映射方法及系统，包括：对二进制乘法竖式构建辅助块，对每块所得到的损失函数进行形式上的等价替换，满足伊辛模型的形式要求，将得到伊辛模型的哈密顿量表达式；根据不同自旋状态下哈密顿量的取值及其范围的分布特征，使其能够跳出局部最优解，直至伊辛模型到达自旋基态；获取两个素因子信息，实现大整数分解，进一步由欧拉公式和密码系统中开放的公钥得到RSA加密算法中的私钥，使用私钥将密文信息转换为原始明文信息，实现对RSA密码系统的破解。本发明完整地表现了一种将大整数分解问题映射为伊辛模型求解问题的一般流程。

摘要： 本发明属于量子计算技术领域，特别涉及一种基于Grover量子计算搜索算法的整数分解优化方法及系统，包含：对量子比特线路进行仿真，将输入基态通过哈达玛变换至叠加态；将整数分解问题转化为优化问题，将需分解整数及其素因子用二进制表示，并构建二进制乘法表；依据二进制乘法表获取二进制相乘方程组，并通过引入约束条件对方程组进行简化；设置迭代条件，将简化后的方程转化为布尔逻辑关系，构造量子黑盒；利用幺正矩阵将目标状态振幅相对于平均振幅做反转，增加搜索到目标项的概率；通过重复迭代来改变搜索到目标项的概率，直至搜索到目标项的概率达到最优。本发明能够达到较好的计算效果，加速效果在大型搜索问题中尤为明显，具有较好的应用价值。

摘要： 本发明公开了一种基于量子退火算法的百万位整数分解的通用方法，包括，基于整数二进制乘法表的信息限制，不断更新所述整数二进制乘法表并对其进行分栏；对分栏后的所述整数二进制乘法表进行目标函数构造，通过平方项属性对每栏的目标函数进行化简；根据降维公式引入辅助变量对所述目标函数中大于2次项的多项式进行降维操作；对每栏的所述目标函数分别进行变量替换，使值域从{0,1}变换到{‑1,1}；将所述目标函数最终的局部场系数矩阵h和耦合项系数矩阵J输入量子计算qbsolv软件环境执行量子退火过程；最终输出能量最小值，对应整数分解成功的解。本发明减少分解整数所需的量子比特数，进而降低量子硬件要求，旨在分解更大规模整数。

摘要： 本发明公开了一种新的基于整数分解问题的代理签名及验证方法，其步骤是：在网络运行之前，原始签名人和代理签名人首先生成自身的公钥和私钥，并发布公钥；当具有签名请求时，原始签名人生成委托书，并基于变色龙哈希函数和普通数字签名算法计算签名授权发送给代理签名人；代理签名人对收到的签名授权进行有效性验证，若有效，则基于变色龙哈希函数碰撞性生成代理签名，而无需对消息再进行数字签名；当验证者收到委托书和代理签名后，首先验证委托书是否有效，确认有效后，再验证代理签名的有效性。本发明的应用，代理签名处理效率高、代理签名长度短，适用于计算能力和网络带宽比较受限的移动网络、无线网络等环境中。