第3章节基础数论幻灯片.ppt

连分数 3.8 连分数 定义 任何以下形式的数均称为连分数 其中，q1、q2、……为整数 连分数 性质 令 为一实数，其连分数表达式为 其中， 而其各项连分数的收敛值为： 当中 满足递推关系及初始条件 连分数 定理： 令 （且 ）为实数x的某项连分数的收敛值 密码安全伪随机数生成器 3.9 密码安全伪随机数生成器 BlumBlumShub() { do { p=RandomPrime(); }while (p%4!=3); do { q=RandomPrime(); }while (p%4!=3); //p,q为随机质数且 = 3 mod 4 n=p*q; do{ s=RandomInteger(1,n); }while(gcd(s,n)!=1); //gcd(s,n)=1且s为随机数种子 x[0]=s; for(i=1;i=k;i++) { x[i]=x[i-1]*x[i-1]%n; b[i]=x[i]1;//取最末位 }; return(b[1],b[2],...,b[k]); } 算法 Blum-Blum-Shub 伪随机数字生成器 密码安全伪随机数生成器 算法 RSA 伪随机数字生成器 RSA_PseudomBitGen() { p=RandomPrime(); q=RandomPrime(); n=p*q; phi=(p-1)*(q-1); do { e=RandomInteger(2,phi-1); }while(gcd(e,phi)!=1); //gcd(e,phi)=1 x[0]=RandomInteger(1,n-1); //x[0]为随机数种子 for(i=1;i=k;i++) { x[i]=PowerMod(x[i-1],e,n); //x[i]=x[i-1]?e%n b[i]=x[i]1; //取最末位 }; return(b[1],b[2],...,b[k]); } * 返回总目录 第3章基础数论 教学目的 了解模运算及辗转相除法 了解中国余式子定律 了解Lagrange定理与费马小定理 了解原根、二次剩余、Galois域等概念 了解质数理论和连分数 了解密码安全伪随机数字生成器 ? 模运算与辗转相除法 本章内容 ? 中国余式子定律 ? Lagrange定理与费马小定理 ? 原根 ? 二次剩余 ? Galois域 ? 连分数 ? 质数理论 ? 密码安全伪随机数字生成器 模运算与辗转相除法 3.1 模运算与辗转相除法 假设今天是星期五，请问10000天后是星期几？ （即5+10000除以7的余数） 即：10000天后是星期二 同余 定义（同余，Congruence）：令 。令 为两整数，称a同余b模n，记为 ，当n整除b-a。而所有与a同余的整数所组成的集合，即 称为a的同余类。所有同余类所形成的集合 同余类 同余类满足的性质： （1）（反身性，Reflexivity） （2）（对称性，Symmetry） 若 则 （3）（迁移性，Transitivity） 若 则 例： 令 则 模运算 加法： （1）封闭性：若同余类 则 （2）交换律：若同余类 则 （3）结合律：若同余类 则 （4）存在加法单位素：存在 ，使得 （5）存在加法反元素：对任一 存在 使得 减法： 乘法： 交换群 定义（交换群） 考虑 ，其中G为集合，而*为运算。令公理： （1）封闭性： 则； （2）交换律： 则； （3）结合律： 则； （4）存在单位素： ， ，使得 （5）存在反元素： ， ，使得 若公理1、3、4、5成立，称为群(Group)； 若以上公理1～5都成立，称为交换群。 交换环 此时除