《大素数的验证》课程设计

信息安全原理及应用信息安全原理及应用 课程设计报告课程设计报告 大素数的验证大素数的验证 姓姓 名名 班班 级级 学学 号号 指导教师指导教师 成成 绩绩 完成时间完成时间 2010 12 20 完成地点完成地点 软三实验室软三实验室 1 一 一 设计题目描述和要求设计题目描述和要求 通过课程设计 加深对信息安全技术及其应用的理论知识的理解 掌握一 些大素数验证的算法 能够单独或合作完成一个大素数验证算法的过程并用软 件展示出来 完成课程设计报告 这次课程设计是以小组为单位进行的 组长为胡艳敏 成员分别为杜国骏 贺瑞杰 马赛 于丛丽 全菲 王新洁 袁红 肖丹丹 乔良 我们组做的是 大素数验证的算法 素数又称质数 指在一个大于 1 的自然数中 除了 1 和此 整数自身外 没法被其他自然数整除的数 换句话说 只有两个正因数 1 和 自己 的自然数即为素数 RSA 公钥密码算法是目前网络上进行保密通信和数 字签名的最有效的安全算法之一 RSA 算法的安全性基于数论中大素数分解的 困难性 二 二 详细设计详细设计 1 大素数验证原理 1 费马小定里 如果 n 是一个素数 而且 a 不是 n 倍数 则有 a n 1 1 mod n 虽然费马小定里通常称为 素性判定 它们实际上是 合数判定 因为 此方法只给出了对合数完全肯定的回答 费马小定里判定对大的 n 相当准确 如果它判定一个数是合数 那么一定是正确的 如果宣布可能是素数 那么很 可能是素数 因此 费马小定理只是个必要条件 符合费马小定理而非素数的数叫做 Carmichael 前 3 个 Carmichael 数是 561 1105 1729 Carmichael 数是非常少的 在 1 100000000 范围内的整数中 只有 255 个 Carmichael 数 为此又有二次探 测定理 以确保该数为素数 2 二次探测定理 二次探测定理 如果 p 是一个素数 0 x p 则方程 x 2 1 mod p 的解为 x 1 p 1 根据以上两个定理 如到 Miller Rabin 算法的一般步骤 2 1 先计算出 m j 使得 n 1 m 2 j 其中 m 是正奇数 j 是非负整数 2 随机取一个 b 2 b 2 计算 v b m mod n 4 如果 v 1 通过测试 返回 5 令 i 1 6 如果 v n 1 通过测试 返回 7 如果 i j 非素数 结束 8 v v 2 mod n i i 1 9 循环到 5 Miller Rabin 是随机算法得到的结果的正确率为 75 所以应该多次调用该 函数 使正确概率提高为 1 1 4 p 2 Java 实例 1 编程 新建工程 向窗口中田间一个静态控件 一个编辑控件和两个按钮控件 界面如图 1 所示 2 主要代码如下 package bigprimenum import org jdesktop application Action public class BigPrimeNumAboutBox extends javax swing JDialog public BigPrimeNumAboutBox java awt Frame parent super parent initComponents getRootPane setDefaultButton closeButton package bigprimenum import org jdesktop application Application 3 import org jdesktop application SingleFrameApplication public class BigPrimeNumApp extends SingleFrameApplication Override protected void startup show new BigPrimeNumView this Override protected void configureWindow java awt Window root public static BigPrimeNumApp getApplication return Application getInstance BigPrimeNumApp class public static void main String args launch BigPrimeNumApp class args BigInteger num null BigInteger i null BigInteger l null try num new BigInteger jTextField1 getText boolean a true l new BigInteger 0 i new BigInteger 2 BigInteger t new BigInteger 1 BigInteger z new BigInteger 0 double s Math sqrt num doubleValue BigInteger b new BigInteger String valueOf int s System out print new BigInteger String valueOf int s for i new BigInteger 2 pareTo b 0 i i add t if num mod i compareTo z 0 a false 4 l i break 3 结果说明 运行该程序后 在上边的文本框中输入要验证的一串数字 输入完毕后按 Test 按钮对输入的数字进行验证 并在下边的文本框中显示验证的数是否为 素数以及判断的依据 如图 1 所示 图 1 图 2 5 三 三 小结小结 经过短短几周的不断努力学习和设计 开发 此次课程设计开发完成 前几周刚刚开始接触大素数验证的算法时 那真是云里雾里 对大素数验 证的算法理解非常的少 几乎是等于零 后来在樊老师的讲解下和悉心指导下 才拨开云雾见月明 才懂得了大素数验