分类: 数学 >> 应用数学 提交时间: 2022-11-09
摘要: 近年来,混合整数线性规划(MILP)被广泛用到对称密码的自动化分析中,并逐渐成为一个强有力的工具。在MILP方法中,一个核心的数学问题就是:对给定的Z2n上的高维离散点集S,如何利用尽可能少的不等式刻画它,简称整系数线性不等式完全刻画问题(FLIIIC problem)。该问题是NP-hard的。在这个工作中,我们是首次针对该问题给出了完整的求解理论。我们的方法从Plain集合出发,即由单个线性不等式确定的解集,揭示了其一系列内在属性,包括型、稀疏度、第一类退化、第二类退化,序、极小元、极大元、范数和界。在此基础上我们进一步给出了刻画Plain集合的一个充分必要条件,即集合S是Plain集合的充分必要条件是S集合是good集合。基于上述知识,对任意给定的子集S,我们提出了一个求解S的全部极小闭包和最优线性不等式完全刻画的算法。我们的算法非常高效且实用,可以应用到密码学中各种常见的S盒的刻画。据我们所知,这是首次给出了各种常见S盒的全部极小闭包,且我们得到的所有刻画结果都是目前最好的结果,尤其时在高维S盒刻画方面,我们的结果远优于国内外同行的结果。
分类: 数学 >> 应用数学 提交时间: 2022-10-12
摘要: 随机函数可逆性问题是密码学中一类重要的问题,例如Hash函数原像恢复,分组密码密钥恢复,离散对称问题求解等等。在这个工作中,我们将随机函数可逆性问题从一维推广到高维,并提出了一个新的广义生日碰撞原理。基于该原理,我们给出了多随机函数可逆性问题的一个求解算法。该算法可以解决1980年Hellman在分组密码TMTO攻击中只能使用一对明密文数据而不能使用多个数据的公开问题,以及Biryukov和Shamir在2000年提出的带BSW采样的TMDTO攻击中只能使用极其少量的明密文数据而不是全部数据的公开问题。
分类: 数学 >> 控制和优化 提交时间: 2021-11-29
摘要: 在机器学习和数学优化研究领域, 深度学习优化问题易优性的数学解释极具挑战性. 损失函数存在高维、非凸、不光滑等特质性, 然而也能通过梯度下降法搜索到全局最优值. 损失函数地貌分析成为揭示深度学习优化问题易优性本质的重要研究方向. 为促进可解释、可信的深度学 习在更关键领域的应用, 本文回顾了损失函数地貌特征(局部极小点的数量和空间分布、最优点之间的连通性、临界点的最优性)、梯度下降法收敛性、以及损失函数地貌可视化等方面的研究进展和挑战.
分类: 数学 >> 数学(综合) 提交时间: 2020-02-18
摘要: 2019年12月,新型冠状病毒肺炎(NCP,又称2019-nCoV)疫情从武汉开始爆发,几天内迅速传播到全国乃至海外,对我国的工农业生产和人民生活产生了重要影响。科学有效掌控疫情发展对疫情防控至关重要。本文基于中国卫健委及湖北省卫健委每日公布的累计确诊数,采用逻辑斯蒂模型对数据进行了拟合,以期给该疾病的防控治提供科学依据。通过公布的疫情数据,我们反演了模型的参数,进而有效地模拟了目前疫情的发展,并预测了疫情未来的趋势。我们预测,湖北省疫情还要持续至少2周,而在全国其他地区,疫情可望1周左右达到顶峰。
分类: 数学 >> 计算数学 提交时间: 2019-08-27
摘要: 本文基于阻尼块反幂法与子空间投影算法设计了一种求解特征值问题的广义共轭梯度算法, 同时也实现了相应的计算软件包. 然后对算法和计算过程进行了一系列的优化来提高算法的稳定性、计算效率和并行可扩展性, 使得本文的算法适合在并行计算环境下求解大规模稀疏矩阵的特征值. 所形成的软件包是基于Matrix-Free和Vector-Free设计的, 可以应用于任意的矩阵向量结构. 针对几种典型矩阵的测试结果表明本文的算法和软件包不但具有良好的数值稳定性, 同时相比于SLEPc软件包中的LOBPCG以及Jacobi-Davidson解法器有2-6倍的效率提升. 软件包的网址: https://github.com/pase2017/GCGE-1.0.