看机器学习如何求解多元一次方程？
看机器学习如何求解多元一次方程？
技术的发展
前言很久没写博客了，一直想把自己的一些知识进行沉淀，毕竟时间久了，就很容易忘记。所以想了想，为了不让自己忘记，干脆就写成博客，还可以和大家一起探讨和学习，于是我决定在周末空余时间写写关于人工智能与机器学习应用系列的文章，今天就从最简单的机器学习模型开始。问题起源求解多元一次方程的解似乎看起来不是一件很难的事情，可以通过方程组的合并求解，从技术可行性上是完全没有问题的，但是能否有一个通用的模型帮助我们去求解多元一次方式呢？例如给定下列方程：5x+2y=10x+4y=11通过方程组的合并消元求解，则很容易得x=1，y=0.25。如果写一个求解的该二元一次方程的求解函数，似乎也不是什么难事，但是如果变量不只是两个，对方程组合并消元的复杂度则会加大，甚至造成程序的可读性也变差。机器学习的核心思想源自于数学，方程组合并消元的方法只是数学中人们总结的技巧，但并不是方程组求解的原始思路，此时此刻，我们需要借助最原始的数学思维帮助我们建立一个数学模型，辅助求解多元一次方程组。问题抽象我们将公式进一步抽象，变成程序可理解的数组，如下5x+2y=10转变为数组[5,2,10]x+4y=11转变为数组[1,4,11]我们希望有一个数学模型的输入是两个数组：[5,2,10]，[1,4,11]，输出是方程求解的数组[1,0.25]。即希望有下所示的功能，将数学问题转变了计算机的工程问题，则期望的是如下的工程求解：//定义线性方程组求解模型，2表示变量的个数LinearEquationlinearEquation=LinearEquation(2);//将第一个方程加入到模型中[5,2,10]linearEquation.addEquation(newDouble[]{5.0,2.0},10.0);//将第二个方程加入到模型中[1,4,11]linearEquation.addEquation(newDouble[]{1.0,4.0},11.0);//模型进行训练linearEquation.//输出训练后的x和y的值System.out.println(Arrays.toString(linearEquation.getVariables));模型引入对机器学习而言，永远逃不过两类计算，一个是距离计算，一个是概率计算。而方程式中的x和y我们可以理解为权重，即当x和y为某值时(5x+2y-10)的距离尽可能短，使得几乎等于0，同理(x+4y-11)的距离也尽可能短，使得几乎也等于0，权重或为概率或为距离。类似这样的计算，很容易想到人工神经网络。人工神经网络可以处理线性与非线性的问题，由于本问题是求解多元一次方程，因此是线性问题，可以采用人工神经网络中最基本的模型感知器进行求解，感知器是FrankRosenblatt在1957年就职于Cornell航空实验室（CornellAeronauticalLaboratory）时所发明的一种人工神经网络。它可以被视为一种最简单形式的前馈神经网络，是一种二元线性分类器。感知器使用特征向量来表示的前馈神经网络，把矩阵上的输入x（实数值向量）映射到输出值f(x)上（一个二元的值）。感知器模型如下图所示：通过上图可以看出，感知器模型由一下几个部分组成：1.输入。输入主要是包括n个输入项pi，以及每一个输入项下对应的权重wi2.激活函数。感知器可以灵活选择激活函数。激活函数给神经元引入了非线性因素，使得神经网络可以任意逼近任何非线性函数，这样神经网络就可以应用到众多的非线性模型中。3.输出。感知器的输出则比较容易理解如下公式所示，其中b是偏执项一个较为实际的理解感知器即为:输入的x是对结果y的影响参数，但是每一个输入的x对y的影响都有相应的权重w，最终对y的影响结果则等于每一个输入与权重之和的累积。模型应用与求解多元一次方程感知器的训练过程是使得对应的wi处于某值的时候，输入的xi能够得到相应的y，实际也是在求wi的过程。而在对多元一次方程求解的时候，可以将未知数xi的系数视为wi，则多元一次方程是已知wi，y，求xi的过程。因此，我们可以将方程中的xi视为感知器中wi，方程中的wi视为xi，这样求方程的解，则完全转变为感知器的训练过程。而方程式的系数即可为感知器的训练集。如果方程式有三个未知数，则至少有三个方程（即三个训练集）才可能获得解，应用代码如下所示：//方程式一：10.0*x1+2.0*x2=12.0//方程式二：1.0*x1+1.0*x2=2.0//根据上述方程可知：x1=1.0,x2=1.0com.iveely.ml.application.LinearEquationlinearEquation=newcom.iveely.ml.application.LinearEquation(2);linearEquation.addEquation(newDouble[]{10.0,2.0},12.0);linearEquation.addEquation(newDouble[]{1.0,1.0},2.0);linearEquation.Doubleret=linearEquation.getV//计算结果误差需小于0.1，可以根据学习速率和迭代次数调整精确度assertEquals(1.0,ret[0],0.1);assertEquals(1.0,ret[1],0.1);归纳总结这是机器学习中神经网络最基本的实际应用，感知器能够解决多元一次方程问题的根本原因也是在于线性可分，理论上其它的机器学习模型也是可以做到。如果方程无解，则可以通过最小二乘法，找到一条最佳的直线，尽可能满足点的覆盖。您的朋友：刘凡平（），LinearEquation源码请参见这里，iveely.ml源码参见这里。
本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。
技术的发展
百家号 最近更新：
简介: 新媒体运营信息，新媒体运营商。
作者最新文章2010年10月 专题开发/技术/项目大版内专家分月排行榜第二2010年7月 专题开发/技术/项目大版内专家分月排行榜第二
2011年1月 专题开发/技术/项目大版内专家分月排行榜第三2010年12月 专题开发/技术/项目大版内专家分月排行榜第三2010年8月 专题开发/技术/项目大版内专家分月排行榜第三
2010年6月 专题开发/技术/项目大版内专家分月排行榜第二
2010年4月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。对对称密码的代数攻击及解多元方程组算法的研究--《山东大学》2008年硕士论文
对对称密码的代数攻击及解多元方程组算法的研究
【摘要】：
近些年来,对对称密码体制的一种全新有效的攻击方法——代数攻击,在密码学界中引起了越来越多的关注。与以前传统的“统计”攻击方法不同,使用代数方法对密码体制进行密码分析的攻击方法,统称为代数攻击。其主要思想是,将密码体制内在加密活动描述为输入(密钥)和输出之间的多元方程组,并且通过求解低次超定或稀疏方程组来恢复密钥。这样,求解大型低次超定稀疏多元方程组计算上的困难性,就成为许多现代对称密码体制安全性的一个必要条件,人们也越来越多得关注于寻找求解大型多元方程组的新的快速有效算法。
代数攻击与其它已有的攻击方法相比有很大的优势,其中最引人注意的特色之一就是代数攻击所需要的数据量非常少,有时1个或2个己知明文就足够了,这对攻击者来说是非常有吸引力的。这也正是为什么现在代数攻击虽然还不成熟、效率低,却仍然是潜在得非常有破坏力的原因。代数攻击的另一个优势就是,它是一种全新的分析方法,目前涉足的也许只是代数分析方法的一小部分,还有许多未知的领域没有被探索和研究。因而代数攻击的前景非常广阔,可以有很大得提高和改进,对代数攻击进行研究具有很好的理论意义和应用价值。
代数攻击最早用于对公钥密码及分组密码Rijndael和Serpent的攻击,通过将恢复密钥的问题转化为求解一个多元二次方程组(MQ问题)来进行密码分析。虽然代数攻击对Rijndael和Serpent还没有可行的攻击实例,但其S盒超定稀疏方程的存在已成为Rijndael和Serpent一种本质的威胁。随着解低次多元方程组有效算法——XL算法的提出和改进,对基于LFSR流密码体制的代数攻击成为一个热门课题,其攻击思想是由高阶相关攻击的思想衍变而来的,不再把输出作为输入的函数考虑,而是研究输入流和输出流之间的代数关系。研究表明代数攻击对基于LFSR的流密码体制非常有效,多个基于LFSR的流密码对代数攻击是(本质)脆弱的。近年来对分组密码的代数攻击又有了新的研究成果,采用将MQ问题转化为SAT问题求解的算法可以破解6轮DES(仅使用一个已知明文)和全部轮的KeeLoq密码体制。
本文研究了对基于LFSR流密码和分组密码的代数攻击,既有理论方面的研究,又有对具体密码算法实际的攻击方法,如Toyocrypt、LILI-128、EO、Sfinks、Rijndael、Serpent、DES、KeeLoq等。本文还研究了传统的构造Grobner基的Buchberger算法、XL算法及改进和将MQ问题转化为SAT问题求解等解方程组的算法。相较于前两种算法,第三种算法非常简单有效,而且所需已知明文的个数也相对较少,采用这种算法,可以破解6轮DES和全部轮的KeeLoq,因而研究这种算法对推动代数攻击的发展有非常积极的意义。本文重点探讨了将低次稀疏多元方程组转化为CNF-SAT问题的有效方法,并仅用一个已知明文,固定20个密钥比特,采用S-盒的门电路表示方法,列出了6轮DES 3076个方程的2900元稀疏二次方程组,转化为4203个变元、16880个子句、子句总长度为51514的SAT问题,进而用MiniSAT 2.0求解,恢复出另外36比特密钥。本文最后简单介绍了代数免疫度概念(为抵抗代数攻击产生的新的密码设计标准)的提出和扩展,指出仅用零化子定义布尔函数代数免疫度的概念不能保证所有密码体制抵抗所有类型的代数攻击,必须考察密码体制中非线性函数(如布尔函数和S盒等组件)输入和输出之间的某些“简单”多元代数关系(I/O关系),以此来建立抵抗代数攻击的新的密码设计准则。
【关键词】：
【学位授予单位】：山东大学【学位级别】：硕士【学位授予年份】：2008【分类号】：TN918.1【目录】：
中文摘要8-10
ABSTRACT10-12
第一章 绪论12-16
§1.1 代数攻击的提出和发展12-13
§1.2 代数攻击的贡献和新的研究课题13-14
§1.3 本文的研究重点和内容安排14-16
第二章 对基于LFSR流密码的代数攻击16-30
§2.1 基本模型16-19
§2.1.1 代数攻击的适用场景17-18
§2.1.2 带记忆的组成器18-19
§2.2 快速代数攻击19-21
§2.3 推广的模型和攻击方法21-25
§2.4 攻击实例25-30
§2.4.1 Toyocrypt25
§2.4.2 LILI-12825-26
§2.4.3 EO26-27
§2.4.4 Sfinks27-30
第三章 对分组密码的代数攻击30-42
§3.1 Rijndael和Serpent30-35
§3.1.1 Serpent中S-盒的超定方程32
§3.1.2 Rijndael中S-盒的超定方程32-34
§3.1.3 XSL攻击34-35
§3.2 DES35-39
§3.2.1 S-盒的I/O方程35-37
§3.2.2 求解方程37-38
§3.2.3 "认证的"代数攻击38-39
§3.3 KeeLoq39-42
§3.3.1 算法的简单描述39-40
§3.3.2 直接的代数攻击40-41
§3.3.3 滑动-代数攻击41-42
第四章 解方程组算法的发展42-60
§4.1 Gr(o|¨)bner基方法42-44
§4.2 XL算法44-50
§4.2.1 复线性化和XL算法44-47
§4.2.2 GF(2)上的XL算法47-50
§4.3 MQ问题转化为SAT问题求解50-58
§4.3.1 SAT问题50-51
§4.3.2 转化步骤51-53
§4.3.3 SAT求解器53-54
§4.3.4 6轮DES转化为CNF-SAT问题求解54-58
§4.4 小结58-60
第五章 代数免疫度的提出和发展60-64
§5.1 布尔函数的代数免疫度(零化子)60-61
§5.2 推广的代数免疫度61-64
结束语64-66
附录 第1轮DES中S1的66个方程66-68
参考文献68-70
学位论文评阅及答辩情况表72
欢迎：、、)
支持CAJ、PDF文件格式
【引证文献】
中国博士学位论文全文数据库
李磊;[D];解放军信息工程大学;2012年
中国硕士学位论文全文数据库
史鹏;[D];中南大学;2012年
【参考文献】
中国硕士学位论文全文数据库
张莉;[D];西安电子科技大学;2005年
【共引文献】
中国期刊全文数据库
贾艳艳;胡予濮;高军涛;;[J];电子科技大学学报;2011年05期
贾艳艳;胡予濮;高军涛;;[J];电子与信息学报;2010年12期
路浩;[J];高等学校计算数学学报;1989年03期
吕竹青,周德俊,林彦芬,赵同欣;[J];高等学校计算数学学报;1993年03期
周德俊,林彦芬,田增保;[J];高等学校计算数学学报;1996年04期
修保新;刘忠;张维明;阳东升;;[J];国防科技大学学报;2007年03期
彭昌勇;祝跃飞;康绯;米顺强;;[J];国防科技大学学报;2012年02期
周德俊,赵玉凤,林彦芬;[J];河北地质学院学报;1995年05期
周德俊,李云祥;[J];河北省科学院学报;2002年03期
张梦元;;[J];信息通信;2012年02期
中国博士学位论文全文数据库
王后珍;[D];武汉大学;2010年
张龙;[D];北京邮电大学;2011年
张林生;[D];哈尔滨工业大学;2010年
王磊;[D];西南交通大学;2013年
李顺波;[D];西安电子科技大学;2012年
中国硕士学位论文全文数据库
于坤;[D];解放军信息工程大学;2010年
任成林;[D];西安电子科技大学;2011年
邓生杰;[D];华南理工大学;2011年
刘钊元;[D];上海交通大学;2011年
柯善学;[D];中国人民解放军信息工程大学;2003年
张莉;[D];西安电子科技大学;2005年
徐晓华;[D];扬州大学;2005年
王江峰;[D];国防科学技术大学;2005年
李骏;[D];四川大学;2006年
徐春霞;[D];解放军信息工程大学;2006年
【同被引文献】
中国期刊全文数据库
潘永涛;戚文峰;;[J];电子与信息学报;2006年12期
刘瑞祯;[J];电脑编程技巧与维护;1996年11期
郑士贵;[J];管理科学文摘;1997年09期
耿海峰;;[J];廊坊师范学院学报(自然科学版);2011年03期
崔国华,张友明,洪帆;[J];华中科技大学学报(自然科学版);2003年05期
刘明才，宫豪，王洪君;[J];计算机辅助工程;1996年04期
刘连浩;段绍华;崔杰;;[J];计算机工程;2008年16期
李少芳;;[J];计算机与现代化;2006年08期
李斓,张焕国;[J];通信保密;2000年01期
中国硕士学位论文全文数据库
熊晓雯;[D];国防科学技术大学;2010年
张莉;[D];西安电子科技大学;2005年
李晨;[D];西安电子科技大学;2009年
【二级参考文献】
中国期刊全文数据库
吴文玲,冯登国;[J];电子学报;2000年01期
中国博士学位论文全文数据库
冯登国;[D];西安电子科技大学;1995年
【相似文献】
中国期刊全文数据库
王刚;朱艳琴;林霞;;[J];苏州大学学报(工科版);2005年06期
田仲富,王述洋,谷志新;[J];林业劳动安全;2004年04期
周雪;;[J];信息安全与通信保密;2010年11期
邹德军,李盘林,孟宪福;[J];大连理工大学学报;1997年05期
宋维平;[J];吉林师范大学学报(自然科学版);2005年02期
徐红;唐刚强;;[J];企业技术开发;2006年09期
赵星阳;[J];信息技术;2004年07期
刘志伟;;[J];河池学院学报;2006年02期
曾宪文,高桂革;[J];上海电机学院学报;2005年02期
,胡耀辉;[J];微计算机信息;2005年14期
中国重要会议论文全文数据库
付安民;张玉清;;[A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（下）[C];2006年
赵燕丽;刘志猛;;[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年
杨红菊;;[A];专利法研究（1998）[C];1998年
吴素研;徐冠宁;胡祥义;李文波;;[A];全国计算机安全学术交流会论文集（第二十三卷）[C];2008年
李冬华;赵学秘;李宗伯;李克洲;;[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年
余梅生;叶永飞;高岩;;[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年
丁瑶;于志强;叶松;唐凌;吴渊;王杰斌;鲁昱;;[A];中国通信学会第六届学术年会论文集（下）[C];2009年
刘运毅;覃团发;倪皖荪;张淑仪;;[A];中国声学学会2005年青年学术会议[CYCA'05]论文集[C];2005年
中国重要报纸全文数据库
王延庆;[N];黑龙江日报;2004年
朱杰;[N];中国计算机报;2008年
罗志华;[N];金融时报;2004年
中国博士学位论文全文数据库
罗宜元;[D];上海交通大学;2013年
潘巨龙;[D];浙江大学;2011年
高胜;[D];西安电子科技大学;2012年
李敏;[D];南开大学;2012年
杜承航;[D];山东大学;2011年
张传武;[D];电子科技大学;2003年
易立华;[D];华中科技大学;2009年
范伟;[D];北京邮电大学;2010年
马敏耀;[D];北京邮电大学;2010年
刘光军;[D];西安电子科技大学;2013年
中国硕士学位论文全文数据库
金灿奇;[D];大连理工大学;2013年
陈敏;[D];华东师范大学;2009年
徐连诚;[D];大连理工大学;2001年
宋永林;[D];福州大学;2004年
李志永;[D];南京航空航天大学;2010年
马西保;[D];东北石油大学;2012年
缪立强;[D];电子科技大学;2012年
张辉明;[D];上海交通大学;2007年
刘元锋;[D];解放军信息工程大学;2006年
张峰;[D];北京交通大学;2007年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号