因子分解法（共8篇）
因子分解法 篇1
0引言
铸造充型过程被认为是一个不可压缩流的非定常流动现象, 其液态金属流动时所遵循的质量守恒定律和牛顿第二定律采用连续性方程、动量方程描述。目前求解Navier-Stokes方程的主要方法有SIMPLE法、MAC法和SOLA法等。SOLA法是最常用的方法, 但求解压力场和速度场时, 需要在连续性方程和动量方程之间进行多次迭代, 计算效率不高[1-4]。
本文为提高计算效率, 采用近似因子分解法进行压力场和速度场的计算, 由于这一过程的每一步均可采用托马斯算法求解三对角方程, 所以计算简单, 计算效率较高。建立了基于有限差分法 (FDM) 的流动场数值模拟程序, 采用重力砂型铸造, 铸件材质为纯铝, 针对Benchmark件进行充型过程流动场数值模拟, 并将模拟结果与实验结果进行比对, 验证了数学模型的正确性。
1理论分析
铸造充型过程的守恒型控制方程如下[5?8]:
式中, u、v、w分别为三个坐标轴方向的速度分量;t为时间;ρ为流体的密度;p为压力;gx、gy、gz分别为重力加速度在三个坐标轴方向上的分量;τxx、τyy、τzz为正应力;τxy、 τxz、τyx、τyz、τzx、τzy分别为不同方向上的切应力。
根据梯形法则及式 (1) , 通过第n个时间段和第n+1个时间段的平均, 建立如下隐式差分方程:
式 (2) 是一个非线性差分方程, 根据Beam- Warming方法[5]将其线性化, 具体过程如下:
由于ρ、gx、gy和gz保持不变, 故有Jn+1=Jn。引入单位矩阵, 式 (6) 可以写为
进一步分析式 (7) 可知, 等号右边全都是第n个时间段上的已知量, 所有的未知量均出现在等号的左边, 由于方程左边出现了x方向、y方向和z方向的导数, 就需要包含七个点的有限差分方程模型来满足差分格式。式 (7) 左边出现的七个未知量分别是构成了七对角矩阵, 求解这一方程组的计算量非常巨大。
本文采用近似因子分解法解决以上问题, 这种方法本质上是将式 (1) 所描述的非定常三维问题在每个时间步上分解为三个独立的一维问题:第一步是在时间段n+1/3上计算出与x方向导数有关的未知量, 得到容易求解的三对角方程;第二步是在中间时间段n+2/3上计算出与y方向导数有关的未知量, 也可得到容易求解的三对角方程;第三步是在第n+1时间段上计算出与z方向导数有关的未知量, 同样求解的也是三对角方程。在从第n时间段推进到第n+1时间段的过程中, 通过三次求解三对角方程来解决问题, 具体过程如下。
根据Beam-Warming方法, 将式 (7) 表达为因子形式, 即
如果将式 (8) 左右两边的两个因子相乘, 将会发现式 (8) 与式 (7) 并不完全相同, 多出的项包含因子 (Δt) 3, 不影响式 (7) 所具有的二阶精度, 于是我们用式 (8) 替代式 (7) , 在式 (8) 中出现的因子形式称为近似因子分解。
引入记号ΔUn≡Un+1-Un, 则式 (8) 可写为
式 (9) 为增量形式, 通过求解式 (9) , 得到ΔUn, 然后由Un+1=ΔUn+Un得到下一时间段上Un+1的值。具体过程如下:
综上所述, 通过求解式 (10) , 得到ΔU, 由于式 (10) 中仅包含关于x的导数, 采用中心差分格式, 将得到关于 ΔU的三对角方程组, 利用托马斯算法求解;将 ΔU代入式 (11) , 由于式 (11) 中仅包含关于y的导数, 采用中心差分格式, 将得到关于 ΔU的三对角方程组, 易求得 ΔU;将 ΔU代入式 (12) , 由于式 (12) 中仅包含关于z的导数, 采用中心差分格式, 将得到关于ΔUn的三对角方程组;最后, 将 ΔUn代入式 (13) , 求得Un+1。这一过程的优点在于每一步均可采用托马斯算法求解三对角方程, 计算简单, 可有效提高计算效率。
2算例分析与验证
构造铸件三维实体模型如图1所示, 投影图如图2所示, 网格剖分图 (网格尺寸:2.0mm×2.0mm×2.0mm) 如图3所示[9,10,11]。铸件材质为纯铝, 重力砂型铸造, 浇注速度为0.7m/s, 浇注温度为700℃, 其他参数见表1。计算效率见表2。
铸件充型过程数值模拟结果与实验结果对比如图4~图7所示。
对比图4~ 图7发现, 模拟结果与实验观察结果基本吻合, 说明本文所开发的基于FDM充型过程流动场数值模拟程序是正确的。由表2可知, 由于计算过程中每一步均可采用托马斯算法求解三对角方程, 计算简单, 所需计算时间较短。
3结语
应用近似因子分解法进行速度场和压力场的计算, 将式 (1) 所描述的非定常三维问题在每个时间步上分解为三个独立的一维问题, 由于过程的每一步均可采用托马斯算法求解三对角方程, 所以计算简单, 可有效提高计算效率。
本文建立了基于有限差分法的流动场数值模拟程序, 为验证计算模型的正确性, 采用重力砂型铸造, 铸件材质为纯铝, 针对Benchmark件进行充型过程流动场数值模拟, 并将模拟结果与实验结果进行比对, 发现模拟结果与实验观察结果基本吻合, 说明本文所开发的基于FDM充型过程流动场数值模拟程序是正确的。
参考文献
[1]李德群, 李阳, 陈立亮, 等.材料成形过程模拟技术及其应用[J].中国机械工程, 2006, 17 (19) :2005-2009.Li Dequn, Li Yang, Chen Liliang, et al.Simulation Technology and Application for Materials Forming Processes[J].China Mechanical Engineering, 2006, 17 (19) :2005-2009.
[2]杨小宁, 卜昆, 刘金钢, 等.陶瓷型芯结构对涡轮叶片型面精度影响的仿真研究[J].中国机械工程, 2012, 23 (22) :2689-2693.Yang Xiaoning, Pu Kun, Liu Jingang, et al.Research on Ceramic Core Structure Influences on Surface Accuracy of Hollow Turbine Blade on Numerical Simulation[J].China Mechanical Engineering, 2012, 23 (22) :2689-2693.
[3]牛晓峰, 梁伟, 侯华.基于分数步长法的镁合金挤压铸造充型过程数值模拟[J].铸造技术, 2013, 34 (5) :576-579.Niu Xiaofeng, Liang Wei, Hou Hua.Numerical Simulation of Mg-alloy Filling Process in Squeeze Casting Based on Fraction Step Method[J].Foundry Technology, 2013, 34 (5) :576-579.
[4]赵宇宏, 牛晓峰, 侯华.基于FDM/FEM的镁合金挤压铸造温度场数值模拟[J].兵器材料科学与工程, 2011, 34 (5) :1-4.Zhao Yuhong, Niu Xiaofeng, Hou Hua.Numerical Simulation of Temperature Field During Squeeze Casting Solidification Process Based on FDM/FEM[J].Ordnance Material Science and Engineering, 2011, 34 (5) :1-4.
[5]Niu Xiaofeng, Liang Wei, Zhao Yuhong, et al.A New Implicit Finite Difference Algorithm of Thermal Melt Flow in Filling Process Based on Projection Method[J].Journal of Computational and Theoretical Nanoscience, 2012, 9:1374-1378.
[6]Niu Xiaofeng, Liang Wei, Zhao Yuhong, et al.New Algorithm for Solving 3DIncompressible Viscous Equations Based on Projection Method[J].Transactions of Nonferrous Metals Society of China, 2011, 21:1826-1832.
[7]Anderson J D.Computational Fluid Dynamics[M].New York:McGraw-Hill, 2007.
[8]吴颂平, 刘赵淼.计算流体力学基础及应用[M].北京:机械工业出版社, 2007.
[9]熊守美, 许庆彦, 康进武.铸造过程模拟仿真技术[M].北京:机械工业出版社, 2004.
[10]Zhao Haidong, Bai Yanfei, Ouyang Xiaoxian.Simulation of Mold Filling and Prediction of Gas Entrapment on Practical High Pressure Die Castings[J].Transactions of Nonferrous Metals Society of China, 2010, 20 (11) :2064-2070.
[11]Zhao Haidong, Zhu Jindong.Modeling of Mold Filling of Al Gravity Casting and Validation with X-ray In-situ Observation[J].Applied Mathematical Modelling, 2008, 32 (2) :185-194.
因子分解法 篇2
上海市民办中芯学校
张莉莉 教学目标：
1．理解分组分解法在因式分解中的重要意义．
2．在运用分组分解法分解因式时，会筛选合理 的分组方案． 3．能综合运用各种方法完成因式分解．
教学重点： 理解分组分解法的概念.掌握用分组分解法分解含有四项的多项式.教学难点： 筛选合理的分组方案和综合运用各种方法完成因式分解 教学过程： 一
复习引入
1.什么是因式分解？
2.学过几种因式分解的方法？
3.思考：如何将多项式(1)axaybxby分解因式？
二
新知探究
环节1
内容 ：因式分解(1)axaybxby
教师：提出问题
指导学生一题多解
引入定义
学生：思考 回答 板书练习
意图：1.通过一题多解，培养学生的发散思维
2.使学生整体感悟因式分解的方法，再局部的把握知识。
3.探索 讨论 总结分组的原则
要点：对于四项式的各项没有共同的公因式，而且也没有供四项式作
分解的公式可用，所以用我们前面学过的基本方法都无法直接达到分解的目的．但如果分组后在局部分别分解，然后在组与组直接再看看有没有公因式，就可以创造整体分解的机会．
试一试：分解因式（1）
xy2xy2
（2）abab1
22（4）x4yx2y
（4）9ab3ab
22环节2
如何将多项式(2)a2abb1分解因式？
教师：提出问题：两两分组可行吗？多项式有什么特征？
学生：尝试 探索 总结
意图：拓展学生的思维 再一次认识如何合理分组？ 要点：组和组之间存在平方差的联系
巩固练习：（1）x10xy25yx5y
（2）a3aab3b
222（3）x2xa2a 22
三
课堂小结：引导学生从知识，技能，方法，整体等方面自主小结如何合理分组，教师点评，总结
四
作业布置：练习册：9.16
补充思考题：
环节3 巩固练习：
1.多项式x2yxyx运用分组分解法分解因式，分组正确的是（）A.(x2y)(xyx)
B.(x2xy)(yx)C.x2(yxyx)
D.(x2yxy)x
2.多项式x-a-2a1运用分组分解法分解因式，分组正确的是（）A.(x2-a2)(-2a1)
B.x2-(a22a1)C.(x2-a2-2a)1
D.(x2-2a)(-a21)
3.多项式 x2xy2y运用分组分解法分解因式，分组正确的是（）22A.(x2x)(y2y)
B.(x2y2)(xy)
C.(x2y)(y2x)
D.(x2xy)y2 5.因式分解.（1）abab1
（2）a2abacbcb（3）x2x4y22y
（4）a4b12bc9c
教师：指导学生分组的方法不唯一，而合理地选择分组方案，会使分解过程简单.学生：实践巩固 应用问题 意图：举一反三 触类旁通
注意：分组的方法不唯一，而合理地选择分组方案，会使分解过程简单.三 归纳小结
渗透学法
22222按字母分组四项多项式如何分组？两两分组
符合平方差公式的两项分组差公式三一分组先完全平方公式后平方作业布置：练习册9.16 补充思考题：
（1）x4y
（2）x3xy36y
22（3）x-4xy4y2x-4y
（4）18a32b18a24b
22444224提示：（3）是三项多项式，但不是完全平方式的形式，也不能用十字相乘法分解，应该怎么处理？可以在原式的基础上增减项使得配成完全平方式的形式
x43x2y236y4x412x2y236y49x2y2(x412x2y236y4)9x2y2(4)的思路同（3）
(1)把有公因式的各项归为一组，并使组之间产生新的公因式，这是正确分组的关键，因此，设计分组方案是否有效要有预见性.(2)分组的方法不唯一，而合理地选择分组方案，会使分解过程简单.(3)分组时要用到添括号法则，注意添加带有“－”号的括号时，括号内每项的符号都要改变.(4)实际上，分组只是为完成分解创造条件，并没有直接达到分解的目的．
把一个多项式化成几个整式的积的形式，这种式子变形叫做把这个多项式因式分解，也叫做把这个多项式分解因式。
提公因式法¨22)平方差公式:ab(ab)(ab（适用两项的多项式）公式法222完全平方公式:a2abb(ab)（适用三项的多项式）十字相乘法（适用三项的多项式）
【分析】（1）这是一个四项式，它的各项没有公因式，而且也没有供四项式作分解的公式可用，所以用我们前面学过的基本方法都无法直接达到分解的目的．但是，如果分组后在局部分别分解，就可以创造整体分解的机会．（2）符合公式的两项分组
（3）观察多项式，前三项符合完全平方公式
森林凋落物分解及其影响因子研究 篇3
第七次全国森林资源清查结束后, 我国人工林面积位居世界第一位, 天然林面积、蓄积持续增长, 森林覆盖率达20.36%, 森林质量有所提高。森林生态系统作为陆地生态系统的主体不仅自身维持着巨大的碳库, 还能吸收人类活动所排放的CO2, 在维持全球碳平衡和调节全球气候, 减缓温室效应上扮演着非常重要的角色[1]。
森林凋落物是森林植物生长发育过程中新陈代谢的产物, 作为分解者的物质和能量来源, 借以维持生态系统功能的所有有机质的总称。近年来, 随着全球气候变暖、CO2浓度升高、氮沉降等问题日益突出, 凋落物分解作为陆地生态系统物质循环和能量流动核心环节之一, 在维持林地土壤肥力, 提供植物生长发育的必要养分, 促进全球养分循环方面都有着举足轻重的作用[2]。国内外学者对凋落物分解的过程为对象, 已展开了一系列研究, 从外界环境条件如, 林下植被情况、分解起始时间、光降解、微生物活动、温度等方面, 以及凋落物组成、凋落物质量等内因方面对凋落物分解的影响作用, 均开展了详细的调查。
1 凋落物的作用及功能
凋落物作为森林生态系统中的第二个功能层, 由于其结构疏松、透水性与持水能力强, 能够增加地表层粗糙度, 变地表径流为地下径流, 具有阻滞坡地径流的效应, 因此有着涵养水源, 加强水土保持与防护, 减缓水土流失, 缓解旱季缺水的作用。
在森林凋落物的生态水文功能中, 凋落物对降水的截留作用是凋落物最为主要的功能之一。而凋落物的截留作用主要取决于凋落物蓄积量和持水特性两个方面。同时, 由于森林类型的差异, 凋落物分解程度的不同, 以及凋落物组成的不同, 也会表现出不同的持水特性和截留作用。
森林生态系统中, 凋落物的分解是生态系统物质循环和能量流动的重要环节之一, 对维持土壤肥力、植物生长发育及生态系统可持续发展有重要作用。凋落物的分解对森林生态系统养分的循环与利用, 以及碳氮分配格局均有一定的影响。凋落物的组成种类是影响养分循环利用的重要原因之一。
2 影响凋落物分解的因子
凋落物分解过程与凋落物的组成类型有关。单一种类凋落物与混合组成凋落物的分解率在相同条件下有一定差异。已有研究表明, 阔叶凋落物促进了针叶凋落物的分解, 反之, 针叶凋落物阻滞了阔叶凋落物的分解。需要有合适的组成比例, 才能具有较快的养分归还能力, 有利于森林立地生产力的可持续。同时, 不同类型的森林生态系统也会导致凋落物分解过程上的差异。
凋落物分解过程与微生物动态相关, 微生物是影响凋落物分解过程最为关键的因子之一, 凋落物质量的损失量与微生物多样性种类呈正相关。有研究证明, 不管是在生长季节, 还是冻结期, 微生物对于凋落物分解过程均具有重要的作用。生长期微生物量较高会提高凋落物的分解率, 而冻结期微生物的活动也有一定含量的微生物量, 促进微生物生长。
温度, 常被理解为影响凋落物分解的一个重要因子, 但这一因子要综合其他诸多因子同时考虑。温度对凋落物分解过程的直接影响并不显著。有学者发现, 温度的变化并没有引起凋落物分解过程中质量变化的显著差异, 却导致木质素以及碳水化合物的含量变化很大, 而引起这些变化的温度与微生物的活动呈正相关。说明微生物的活动是影响凋落物分解的过程的主导因子。
同时, 影响凋落物分解过程的因子还有其他因素的影响:土壤可用N积累对凋落物分解影响显著, 解释为土壤中酶活动的增加;与地表分解相比, 浅埋能显著提高凋落物的分解率;林下植被是否剔除, 在短期内对凋落物半分解层的过程也具有显著影响;凋落物凋落的起始时间也可能影响其分解率;光降解对微生物的活动起着一定的影响, 从而影响着凋落物的分解, 但其关系较复杂, 二者谁占到更主要的低位还尚未能确定等;诸多方面的因子同时影响着凋落物的分解过程。
3 研究方法
研究凋落物分解过程的主要方法为分解袋法, 即将所需研究的凋落物样品取回处理后, 放入带空隙的尼龙网袋内, 再置于研究地点样地进行分解试验, 一定天数后, 取一定数量分解袋带回试验室分析其分解程度, 研究其组成成分的变化与外界条件的关系, 当研究方面过于复杂时可取其主要成分的变化表示其变化。而样地的设置重点在于要选择有典型代表性的功能完整的森林生态系统。在试验样地中划分20×20m2或30×30m2的样方若干。须具有代表性, 完整性, 有不同的立地条件和环境因子, 以及不同的优势树种及林下植被, 再根据试验研究的对象不同设定在不同区域做不同处理, 以进行对照试验。
主要测定对象为以下几种:
(1) 凋落物质量损失:从试验地点取回样品后, 在60℃下干燥, 漂洗, 烘干, 粉碎, 测定。
(2) 凋落物C、N含量测定:采用油浴加热K2Cr2O7-H2SO4容量法测定;土壤全氮和植物全氮均采用半微量凯氏定氮法测定。
(3) 凋落物木质素, 碳水化合物测定:样品中的木质素的浓度, 使用热硫酸消化法重力测量估计;样品中的总碳水化合物由苯酚硫酸法测定。
(4) 微生物种类及活动:凋落物中的微生物采用改良培养基培养, 分别进行独立培养, 出现新孢子与菌丝便转移到新培养基, 这样即可得知优势菌的种类和数量。微生物生物量采用化学分析的方法进行测定。
(5) 数据分析:运用数理统计方法分析数据, 方差分析, 拟线性方程等;以及运用软件SAS, SPSS等辅助处理数据。
4 生态学意义与用途
凋落物具有持水特性, 其持水量与凋落物积累量及组成有关。凋落物能够保持一定的水分, 将一部分降水保存在凋落物层。有凋落物覆盖的土壤表面可以减少被雨水的冲刷, 凋落物能够截留雨水, 使地表径流变为地下径流, 增强水分渗透, 涵养水源, 从而减少土壤被雨水侵蚀, 泥沙冲走的现象, 防止泥石流的发生, 具有涵养水源, 水土保持与防护的作用。
由于森林生态系统不断的遭受人类的破坏, 植被被砍伐利用, 生态系统稳定性被破坏, 土壤性质被改变, 动物被捕杀, 造成森林生态系统的逐渐减少与单一化, 则加剧了全球气候的变暖, 由于“C汇”功能的减弱, 大气中CO2的积累量也会增多, 加速全球变暖, 致使生态环境被破坏。森林生态系统具有重要的“C汇”功能, 尤其是土壤-枯落物分室是C与N的重要储存库。对于大气中CO2排放过多的现象, 可以将其转化为有机碳的形式固定在森林生态系统中。不仅可以为森林生态系统中的群落提供物质和能量基础, 保持生态系统的稳定性, 同时也可以解决全球气候的变化, 吸收CO2, 维持稳定的碳循环。
随着凋落物的分解会将有机C分解形成CO2释放入大气, 以形成森林生态系统C循环的模式。然而随着全球气温的上升, 森林生态系统中群落的稳定性将会被打破, 种群生长方式改变的现象将会发生在很多区域内。由于全球气候的改变, 出现森林生态系统初级生产力大于凋落物分解率的现象, 阻滞区域内的正常C循环, 破坏生态系统稳定性, 会导致种群增长衰退甚至消失的现象。
森林生态系统由于人类的开发与利用已经被严重的破碎化, 已有研究表明, 森林生态系统边缘区域的凋落物分解率及土壤潮湿程度明显低于森林内部区域。凋落物分解率下降, 土壤表层被覆盖且水分缺失, 这样会致使土壤呼吸阻碍, 根系呼吸困难, 植被萎蔫和死亡的现象。因此, 保持森林生态系统的完整性, 减少边缘区域凋落物分解阻滞现象的发生, 应该成为减缓CO2过度排放、减轻全球变暖的重要途径之一。
森林凋落物的生态意义及功能都是不容小觑的, 如何能更好的从中发现规律加以利用来维持全球生态平衡, 以及减缓全球变暖, 启动森林的“C汇”功能已刻不容缓, 需要更多进一步的研究。
参考文献
[1]聂昊, 王绍强, 周蕾, 等.基于森林请查资料的江西和浙江森林植被固碳潜力[J].应用生态学报, 2011, 22 (10) :2581-2588.
因子分解法 篇4
关键词：因子分解,DNA计算机,Pollardp-1算法
1 DNA计算机算法原理及优势
1.1 DNA计算原理
通过DNA结构中存在的特殊双螺旋及碱基互补配对的原则,针对计算问题,作编码处理,将需要运算的对象转化为DNA分子链,在生物酶影响下,试管中的DNA溶液生成各种数据池,然后选择一定规则,将原始问题数据进行运算、高度并行地将数据运算映射为DNA分子链可控生化过程,最后通过分子生物技术获得最终运算结果。
1.2 DNA计算机优势
DNA计算机属于一种新型计算机,开关元件以DNA有机分子来充当,与传统计算机相比,在以下方面存在着巨大优势:
1.2.1 DNA生物算法的高度并行性
DNA计算机运算速度十分快,在Adleman试验中,通过科学估算,认为DNA串并行操作的数目已经达到了1014,甚至有研究学者认为,在当前技术条件下,DNA计算机完全有可能实现在1015-1020串并行操作数目。然而,当前传统的巨型计算机,每秒运行速度仅为1013个操作。DNA计算机的每个操作是较为缓慢的,但DNA计算机存在的并行性优势足以弥补这个缺陷。规模极大的并行性操作可以让DNA计算机在同时攻击同一个计算问题的不同部分,在解决数据加密标准DES组合问题应用中十分有效。
1.2.2 高强密集度
DNA属于信息载体,其储存容量十分之大,在1m3的DNA溶液中,能够存储1万亿亿二进制数据,高强密集度,远远超过了当前电子计算机总储存量。
除了以上两点之外,DNA计算机还具备非常高的可靠性,存在着自我修复能力,属于半永久性计算机。
2 因子分解问题的DNA计算机算法
2.1 Adleman-Linpton模型
该模型是在1995年的时候,由Lipton等相关人员所提出的,在该模型中,一个试管可看成由有限个字母所构成的有限链集合,在该模型中其DNA生物操作的描述主要如下:第一,抽取:在给定的含有短DNA分子链S试管P进行抽取操作,从而产生两个试管,即+(P,S)与-(P,S),其中+(P,S)表示在P中所有包含S均可看作子链的DNA分子链,而在-(P,S)表示P中所有不包括S的均可看作为子链的DNA分子链。第二,合并:利用试管P1和P2,将这两者进行合并,产生出试管U(P1,P2),其主要表示的P1与P2试管中的溶液全部注入到试管U,且不改变该试管中的任何一个DNA分子链。第三,检测,即检测试管P,若该试管中至少包含了一个DNA链,则应该返回“yes”或者“no”。第四,丢弃,即将试管P丢弃。第五,添加头部,即把链Z添加大试管P中的每一个链头部。第六,读取:即读取试管P中每一个DNA分子链的信息。
主要是通过Pollard—1DNA算法来实现因子分解,对于要分解的整数n与预先所制定的界‘B’,事先用平方-乘算法将2B!mod n求出,并记为a,接着再利用欧几里德算法将n的最大公因子d以及a-1计算出来,以此实现分解n的目的,在这里的计算过程主要是通过常规分子生物操作来实现的,其算法主要如下:
2.2 具体算法
主要是通过Pollard—1DNA算法来实现因子分解,对于要分解的整数n与预先所制定的界‘B’,事先用平方-乘算法将2B!mod n求出,并记为a,接着再利用欧几里德算法将n与a-1的最大公因子d计算出来,以此实现分解n的目的,在这里的计算过程主要是通过常规分子生物操作来实现的,其算法主要如下:
2.2.1 利用数字计算机把n、a和B!转换成为二进制
(1)n的二进制转换:在m1,m2,…,md中,m1是最低位,而md是最高位,其,可记为length-n。
(2)a的初始值是2,a的二进制转换主要如下:c2,1,c2,2,…,c2,k,在这其中,c2,1是最低位,c2,k是最高位,其中k可记为length-a
(3)B!二进制转换:,其中bbi通常为0或者1,
(4)该算法主要针对的是平方-乘算法中关于乘法运算两种不同的情况,并初始化乘法器,其中一种是所求的结果乘以a;另外一种则是求所得结果平方,因这两者相似,就具体阐述其中的一种,其算法主要如下:
2.2.2 利用欧几里德DNA计算机算法将因子d求出
在该算法中,首先进行a-1的计算,接着再利用欧几里德DNA计算机算法把n与a-1的最大公因子计算出来,最后进行除法运算,以此得到余数序列nk+2,1…nk+2,k,在该余数序列中,nk+2,1为最低位,nk+2,k为最高位,判断该余数序列,若其余数为0,则读出所得到得结果,且算法停止。
2.2.3 Pollard p-1因子分解的DNA计算机算法分析
通过Pollard p-1因子分解算法,求得DNA大数n的因子。
通过执行Pollard p-1因子分解算法,获得初始化试管T′o值,判断其结果是否为0,如是0,则提取出计算结果,并停止程序运行;如不是0则求出试管T′o中余数,并在试管T′o含有DNA链的时候,将试管试管T′o值读给试管试管To,并作初始化,执行程序,对并试管To中余数判断,如是0,则提取计算结果,如将结果读给试管T′o,不断执行程序,最终求得余数为0,从而求出大数n的一个因子。
3 模拟实验结果
为了证明算法的合理性以及有效性,在此将n=2和B=1作为要求解的实例,同时在此时l=1且d=2,通过上述这些算法来对此进行模拟求解过程,其主要如下:
3.1 DNA编码
进行DNA编码的目的,就是为确保在实际的生化反应操作中,每一个DNA分子信息元可以实现唯一识别,从而降低DNA杂交出错率,进一步提高DNA计算的可靠性与稳定性。采用Braich等人求解20个变量SAT所应用的计算机模型,确定每一个变量对应的两个长度均是15的碱基值序列,通过Windows XP操作系统及Visual C++6.0编译器,最终生成DNA序列,DNA序列编码如图1所示。
3.2 计算过程
首先,将试管To的数值初始化,设定为,1,通过执行计算公式,获得试管T′o对应链为,j值为1,满足程序结束的条件,确定为所求结果,结束程序。
4 结语
随着生物分子学的不断发展,因子分解问题的DNA计算机算法越来越引起了人们的注意。DNA计算机在解决因子分解问题上存在着巨大优势,当前,传统的因子分解方法主要是试除法,提出Pollard p-1算法作为因子分解的DNA计算机算法,实现了平方-乘DNA子算法与欧几里得DNA子算法,最终求解出结果,并通过实践证明,这种因子分解的DNA计算机算法是有效且可行的,在解决因子分解问题上发挥着重要作用。
参考文献
[1]王剑波.基于质粒模型的DNA计算机算法求解背包问题[J].湖南人文科技学院学报,2010,04:77-79,96.
[2]江勇.DNA计算在访问控制查询及其安全性分析中的应用研究[D].湖南大学,2011.
因子分解法 篇5
首先列出A-可因子分解算子的定义。
那么称算子L为A-可因子分解算子。
下面给出A-可因子分解算子的两个性质。
引理1[3]设A-可因子分解算子L1, L2:L2 (Rd) →L1 (Q0) , 则L1=L2当且仅当
现在接着讨论A-可因子分解算子的性质, 首先给出A-可因子分解算子是有界的三个充要条件。
更多的, L是同构算子当且仅当存在常数A, B>0 (A=||L-1||-1, B=||L|| ) 使得对任意的f∈L2 (Rd) 有
在上式中若令g=f, 则可得出算子的范数。
注: 定理3 也可以称为A-可因子分解算子Riesz表示定理。
对于映射到L2 (Rd) 的A-可因子分解算子, 我们可以得到相应的A-范数界。
更多的, L是同构算子当且仅当存在常数A, B>0 (A=| L-1|-1, B=| L| ) 使得对任意的f∈L2 (Rd) 有
定理4 表明A-有界可因子分解算子必须是把A-有界函数映到有界函数。
最后, 我们给出A-可因子分解算子L的对偶算子L*的性质。
定理5 如果算子L:L2 (Rd) →L2 (Rd) 是A-可因子分解算子, 则对任意的f, g∈L2 (Rd) 有
所以由引理1 可得结论。
综上所述, 定理2、定理3 和定理4 建立了A-可因子分解算子是有界的充要条件, 于是可以用这三个定理来判定A-可因子分解算子的有界性, 定理5 对A-可因子分解算子L的对偶算子L*进行了讨论, 给出了对偶算子L*的一个性质。
参考文献
[1]张恭庆, 林源渠.泛函分析讲义[M].北京:北京大学出版社, 2003.
[2]夏道行, 吴卓人.实变函数论与泛函分析[M].北京:高等教育出版社, 2010.
[3]王励冰, 王超杰.Hilbert空间A-可因子分解算子[J].科技展望, 2015, 25 (17) :265.
[4]王励冰, 王超杰.A-内积及其性质[J].佳木斯职业学院学报, 2015 (2) :240-241.
因子分解法 篇6
1976年, Diffie和Hellman[4]首次提出了公钥密码的思想, 使密码学发生了一场变革。随后, 人们利用公钥密码的思想建立了各种不同的密码系统, 其中数字签名就是公钥密码思想的一个主要应用。一般来讲, 一个公钥密码算法的安全性是建立在公认的数学难题基础上的, 如果难题被攻破则相应的密码系统也就不安全了。随着科技的发展和密码学研究的不断进步, 这些相应的难题随时有可能被攻破, 因此一些研究者试图提出建立在多个数学难题上的密码系统, 因为多个数学难题同时被攻破的概率要远远小于一个难题被攻破的概率。1988年, McCurley[5]提出第一个同时基于离散对数问题 (DLP) 和因子分解问题 (FP) 两个数学难题的密钥分配方案后, 一系列同时基于离散对数和因子分解的密码方案被相继提出, 但是大部分方案存在安全漏洞, 没有达到设计要求。
本文针对任俊伟和林东岱提出一个改进的基于两个数学难题的签名方案 (简称RL方案) [3]的错误和安全性进行了分析, 证明了当离散对数可解时该方案是不安全的。
1RL数字签名方案
1.1参数设置
(1) 令P为一个大素数, P=4p1q1+1, 其中p1=2p2+1, q1=2q2+1, p1, p2, q1, q2都是素数。这些参数由一个社会信任的公证机构主持, 用一些不可重复再现的随机数作为原始参数, 由计算机自动生成。一旦生成以后, 只有P是公开数据, 其余素数都销毁, 任何人都不使用它们, 任何人都不知道它们。
(2) 公证机构再选取一个数g, 它的阶为N=p1q1, 即gp1q1=1modP, gp1≠1modP, gq1≠1modP, g公开。
(3) 选取一个单向杂凑函数H (x, y) 并公开。
1.2密钥选取
(1) 每个签名用户随机选取一个秘密密钥x, 使得x满足 (1<x<N/2) , (x, N) =1;
(2) 计算:y=gxmodP;
(3) 选取整数d, 同时计算e满足ed=1modΦ (N) ;
(4) 将x, d保密, y, e公开。
1.3签名算法
如果签名用户A想对消息m签名, 则签名过程如下:
(1) 随机选择一个整数t (1<t<N/2) ;
(2) 计算:r=gtmodP, n=H (r, m) modN;
(3) 计算:s= (t-xn) dmodN;
(4) 将Sig (m) = (r, s) 作为数字签名。
1.4验证算法
如果验证用户B想对Sig (m) = (r, s) 进行验证, 则验证过程如下:
(1) 计算s′=semodN;
(2) 判断等式m=gs′rynmodP是否成立。如果等式成立, 则Sig (m) = (r, s) 是合法签名, 否则为非法签名。
2安全性分析
2.1方案中存在的错误
RL数字签名方案的验证算法以及原文定理2的安全性证明中存在明显错误, 原文的定理2及证明过程如下。
定理2可以描述为:如果签名用户A按上述算法签名, 那么签名用户B一定能接受签名。
证明 因为ed=1modΦ (N) , 所以
s′=se= (t-xn) ed= (t-xn) modN
即gs′=gt-xn。又因为r=gtmodP, y=gxmodP,
所以对于验证等式m=gs′rynmodP,
gs′ryn=gt-xnmg-tgxn=mmodP
所以 (r, s) 是A对消息m的签名, 证毕。
事实上, 我们只能从RL数字签名方案的参数设置和算法得到:
gs′ryn=gt-xngtgxn=g2t≠m (1)
与设计者设想的gs′ryn=gt-xnmg-tgxn=m不符, 即使我们认为设计者笔误, 把验证等式按照 (1) 式改为:
r=gs′ynmodP (2)
但是式 (2) 在验证过程中只用到了签名 (m, r, s) 中的r和s, 没有用到m, 所以根本无法验证收到的消息是否为原发送消息。
因此RL数字签名方案根本达不到设计者预期的验证效果, 所以该方案是不正确的。即使上述验证算法是正确的, 接下来的分析也说明该方案并不象设计者预期的那样是基于两个数学难题的。
2.2安全性分析
当离散对数问题 (DLP) 可解时, RL数字签名方案是不安全的。
(1) 设 (m, r, s) 为用户A对消息m的签名, 当用户A将消息组 (m, r, s) 发送给接收者的时候, 攻击者可以通过监听截获该签名;
(2) 由于离散对数问题 (DLP) 可解, 也就是说攻击者可以通过公钥y, g和y=gxmodP计算出私钥x;同理可由r, g和r=gtmodP计算出用户A随机选取的整数t;
(3) 计算n=H (r, m) modN;
(4) 对于s= (t-xn) dmodN, 由于s, t-xn都为已知值, 同样由于离散对数问题 (DLP) 可解计算出私钥d。
由以上分析可知RL数字签名方案的私钥x, d已经全部暴露, 也就是说RL数字签名方案并不像设计者认为的那样是基于离散对数问题 (DLP) 和因子分解问题 (FP) 的, 仅仅是基于离散对数的。
而且在上述方案中, 暴露私钥d与分解N是等价的, 可由下面的定理来描述。
定理1 若 (N, e) 为公钥, 若给出私钥d, 则可以有效地分解N=p1q1;相反, 若给出N的分解, 则也可以有效地计算私钥d。
证明 若已知私钥d, 可以计算k=de-1, 显然k是Φ (N) 的倍数。由于Φ (N) 是偶数, 则可以将k表示为k=2uv, v是奇数, u≥1。对于群Z
p1=gcd (x-1, n) , q1=gcd (x+1, n)
一个简单的算法是随机选取g∈Z
{gk/2, gk/4, …, gk/2u}
中每个元素至少有一半的可能性成为1的非平凡平方根。计算序列中所有元素的操作时间为O ( (lgn) 3) , 用Euclidean算法计算最大公因数的时间为O ( (lgn) 2) 。因此可以有效地分解N。
相反, 若已知N的分解, 则容易计算出Φ (N) , 所以根据扩展的Euclidean算法能有效地计算d=e-1modΦ (N) 。
3结论
由上述分析可知RL数字签名方案本身存在一个严重的设计错误, 是不正确的。即使我们理解为设计者笔误, 在假设整个方案的设计不存在任何问题的前提下对其进行分析, 得出的结论为:RL数字签名方案不是基于离散对数问题 (DLP) 和因子分解问题 (FP) 两个数学难题的, 仅仅是基于离散对数问题 (DLP) 的。
4结束语
将数字签名方案的安全性建立在困难数学问题上是现代公钥密码体系的实现基础。针对困难问题存在被破解的威胁, 将两个或多个困难的数学问题应用到密码体系的构建中是提高安全性的有效方法。虽然本文分析的RL数字签名方案存在错误和漏洞, 但设计思路还是很新颖且值得借鉴的。如何弥补RL数字签名方案中的错误和修正漏洞将是今后讨论的内容。
参考文献
[1]邵祖华.基于因数分解和离散对数的数字签名协议[J].通信保密, 1998, 76 (4) :36-41.
[2]杨君辉, 张玉峰, 戴宗铎.一个基于两个数学难题的签名方案的分析[J].通信保密, 1999, 80 (4) :42-43.
[3]任俊伟, 林东岱.一种基于因数分解和离散对数的签名算法的分析与改进[J].计算机工程与应用, 2005, 7:132-133.
[4]Diffie W, Hellman M E.New directions in cryptography[J].IEEETrans IT, 1976, 22:644-654.
[5]McCurley K C.A key distribution system equivalent to factoring[J].Cryptology, 1988, 1 (2) :95-106.
[6]李俊, 崔国华, 刘志远.一个群签名方案的密码学分析与改进.电子学报, 2007, 35 (4) :778-781.
因子分解法 篇7
文献[1,3]给出了(mg+m-1,mf-m+1)-图G有一个(g,f)-因子分解。文献[2]已证明:设G是一个(0,mf-m+1)-图,则对任意给定的m-子图,都有一个(0,f)-因子分解。文献[3]已证明:若对任意x∈V(G),都有2k≤f(x),则每个(0,mf-m+1)图G有一个(0,f)-因子分解。本文进一步研究了(0,mf-m+1)图G的正交因子分解问题。证明如下结论:若对任意x∈V(G),都有2k≤f(x),则图G的(0,f)-因子分解一定正交于k个顶点不相交的mˉ子图。
1 预备引理
下面总假设G是一个(0,mf-m+1)-图,设S,T是V(G)的不相交子集,用EG(S,T)表示G中连接S及T的边集,记
引理1[1]:设G是一个(0,mf-m+1)-图,f(x)是定义在V(G)上的非负整数函数,H是G的mˉ子图,
则图G有一个(0,f)因子分解正交于H。
引理2[2,4]:设G是一个图,g和f是定义在V(G)上的两个整数值函数且对每个x∈V(G)有0≤g(x)
引理3[3,5]:设G是一个(0,mf-m+1)-图,f(x)是定义在V(G)上的整数值函数且对每个x∈V(G)有2k≤f(x),这里m≥2,k≥2是整数,则图G有一个(0,f)因子F使得E1哿E(F)且E2∩E(F)=Φ。
2 定理及证明
定理1:设G是一个(0,mf-m+1)-图,f(x)是定义在V(G)上的整数值函数,设H1,H2,…,Hk是G的k个顶点不相交的mˉ子图,则G有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。
下面完成定理1的证明:
证明:当k=1时,由引理1知,定理显然成立,故以下可假设k≥2当m=1时,定理显然成立。
假设定理对m-1成立,这里m≥2,由引理3可知,G有一个(g,f)因子F1使得E1哿E(F1)且E2∩E(F1)=Φ。由g(x)的定义知,F1也是G的一个含E1而不含E2的(0,f)因子。
令G'=G-E(F1),根据g(x)的定义,有
因此,G'是一个(0,(m-1)f-(m-1)+1)图。
令H'i=Hi-E1,1≤i≤k,根据归纳假设可知,G'有一个(0,f)因子分解F'={F2,…,Fm}正交于每个H'i,1≤i≤k。于是,G有一个(0,f)因子分解F={F2,…,Fm}正交于每个Hi,1≤i≤k。
定理1证毕。
参考文献
[1]Alspach B,Heinrich K,Liu G.Contemporary Design Theory a Collection of Surveys[M].New York:wiley,1998:145-148.
[2]Liu G,othogonal(g,f)factoizations in graphs[J].D is crete Math:1997:78-91.
[3]刘金波,刘刚,王淑玲.(0,mf-m+1)图的(0,f)因子分解[J].电脑知识与技术,2011(1).
[4]Liu G.othogonal(g,f)factoizations in graphs[J].D is crete Math,1997:104-110.
因子分解法 篇8
对于多过程的物理综合题, 首先应该按照时间和空间的顺序关系, 把题目描述的复杂物理过程拆分成若干个简单阶段, 也就是子过程, 然后按照程序分析子过程的物理特性, 依据物理模型, 正确选择适用的物理规律, 建立准确的数学表达式来求解。具体说明如下。 (1) 时间顺序分解法:即按照物理过程的先后顺序进行分解。这类题目是几个物理过程先后出现, 一般只涉及单个的物体运动。分解后, 对每个子过程运用物理规律求解即可。 (2) 空间次序分解法:即按照物理过程的空间关系进行分解。这类题目是几个物理过程同时出现, 一般涉及多个物体运动。分解后, 对各个子过程运用物理规律求解即可。 (3) 时间空间分解法:即从时间和空间关系上同时进行分解。这类题目在时间和空间上都存在多个物理过程, 通常涉及多个物体运动。分解后, 对每个子过程运用物理规律求解即可。
2. 根据开放性问题多角度来分解
高中物理中的开放性题目因为具有引领学生开展多方位、多层次、多角度的探究, 培养学生创造性思维习惯的作用, 而越来越受到重视。这类题目通常题设条件模糊, 解题思路不明确, 答案不唯一。
遇到开放性题目, 首先应该从引起题目开放性的原因入手, 把问题转化成若干明确的子题目, 使复杂问题简单化, 整体问题具体化, 再分别分析、解答子题目, 最终把所有结果进行汇总即可。
高中物理常见分类讨论问题如下。 (1) 已知条件具有区间型、方向性、周期性、时空性, 或者已知物理量之间的数量关系不明确。例如, 波传播的方向性、电场及磁场的方向性等问题。 (2) 已知条件不明确, 使物体的状态存在多种可能性。例如, 平衡状态就包括匀速直线运动和静止两种状态。 (3) 已知条件不确定, 使物体的运动状态有多种类型。例如, 单摆中“使绳子不松弛”, 意味着两种情形——物体在做完整的圆周运动或者往复运动。 (4) 解得的物理量不唯一, 需要根据物理原理或者实际情况来讨论、验证。 (5) 题目中的物理量都以字母表示, 而且各个物理量之间的大小关系未定。例如, 弹性碰撞中两个物体质量的大小关系。 (6) 物理对象自身的性质不确定。例如, 硬杆可提供所有可能方向的力;电荷的正负等。
3. 根据知识结构来分解
高中物理包括力、电、磁、光、原子物理等几大块, 综合题通常是这些知识的综合。分析题目时, 应该首先将题目按照知识板块进行拆分, 其次解决已经拆分好的几个子问题, 然后根据各个子问题所涉及的共同因素寻找它们之间的关联, 最终解决整体问题。
4. 根据形式结构来分解
对于结构型综合题目, 就是把几个简单问题用搭积木的方法进行组合, 设计成一个综合题目, 用来考查学生的综合分析能力。这类综合题的解决方法, 首先要把题目按照结构分解成几个子问题, 其次运用相关的物理概念和规律解决各个子问题, 最后根据各个子问题所求的物理量之间的相互关系, 寻找整体问题的解决。
下面通过一个例子具体说明怎样利用“分解法”解决高中物理综合题。
例题:宇航员站在一星球表面上某高度处, 沿着水平方向抛出一小球。经过时间t, 小球落到星球表面, 现测得抛出点与落地点之间的距离为L。若抛出时的初速度增大到原来的2倍, 则抛出点与落地点之间的距离为L。已知两落地点在同一水平面上, 该星球的半径为R, 万有引力常数为G。求该星球的质量M。
解答:根据题目的结构特点, 可将其分解为两个子问题。 (1) 求解星球表面的重力加速度g; (2) 已知星球表面的重力加速度为g, 星球的半径为R, 万有引力常数为G。求星球的质量M。
对于子问题1:设小球抛出时的高度为h, 小球的初速度为v0,
对于子问题2:质量为m的小球在该星球表面受到的重力等于星球对它的引力, 即:
根据两个子问题之间的联系, 解 (4) 、 (6) 式得
综上, 运用“分解法”能够将复杂的高中物理综合问题, 转化为若干易于求解的简单问题, 起到题目化简、思路化简、解答化简的作用, 不失为一种高中物理综合题的解题捷径。
参考文献
[1]陈秉乾, 严宣申.高考考你什么:物理化学[M].北京:当代中国出版社, 2008.