例1:设p是一个素数,a是一个整数满足1≤a<p,a模除p的指 数( index)是满足a1modp)的最小正整数i。它等于集合 X={ [al mod p|j21}的势,即i=|Ⅺ 例如,2模除31的指数等于5:25mod31=1, X={21mod31,22mod31,23mod31,24mod31,25 mod 31] 5模除31的指数是3,即53mod31 3模除31的指数是30。 由费马 (Fermat)定理(ap1≡1(modp)可知,a模p的指数总 是恰好整除p-1 例如,设p=31,若a=2,则30÷5=6; 若a=5,则30÷3=10 因此,X中的j至多为p-1,由此可得一种在X中随机,均匀和 独立地取一个元素的算法
11 例1：设p是一个素数，a是一个整数满足1≤a<p， a模除p的指 数(index)是满足a i≡1(mod p)的最小正整数i。它等于集合 X={aj mod p | j ≥ 1}的势，即i=|X|。 例如，2模除31的指数等于5：2 5 mod 31=1, X={2 1 mod 31, 2 2 mod 31, 2 3 mod 31, 2 4 mod 31, 2 5 mod 31}; 5模除31的指数是3，即5 3 mod 31 = 1, 3模除31的指数是30。 由费马(Fermat)定理(ap-1 ≡1(mod p))可知，a模p的指数总 是恰好整除p-1. 例如，设p=31，若a=2，则30÷5=6； 若a=5，则30÷3=10。 因此，X中的j至多为p-1，由此可得一种在X中随机，均匀和 独立地取一个元素的算法
ModularExponent(a, j, p ∥求方幂模s= al mod p,注意先求a可能会溢出 s←-1 while j>o do t if( j is odd)s←s· a mod p; a←a2modp j←jdv2; return s: Draw(a, p ∥在X中随机取一元素 j← uniforn(1.p-1); return ModularExponent (a,j,p);∥在X中随机取一元素
12 ModularExponent(a, j, p){ //求方幂模s=aj mod p, 注意先求a j可能会溢出 s ← 1; while j>0 do { if (j is odd) s ← s·a mod p; a ← a 2 mod p; j ← j div 2; } return s; } Draw (a, p) { // 在X中随机取一元素 j ← uniform(1..p-1); return ModularExponent(a, j, p); // 在X中随机取一元素 }
伪随机数发生器 在实用中不可能有真正的随机数发生器,多数情况 下是用伪随机数发生器代替。 大多数伪随机数发生器是基于一对函数 s:X→X,这里X足够大,它是种子的值域 R:X→Y,Y是伪随机数函数的值域 使用S获得种子序列:x0=9,X=S(xX,0 然后使用R获得伪随机序列:y=R(x,i20 该序列必然是周期性的,但只要S和R选的合适,该 周期长度会非常长。 Tc中可用rand和 srand(time),用GNUc更好
13 ◼ 伪随机数发生器 在实用中不可能有真正的随机数发生器，多数情况 下是用伪随机数发生器代替。 大多数伪随机数发生器是基于一对函数： S: X → X, 这里X足够大，它是种子的值域 R: X → Y, Y是伪随机数函数的值域 使用S获得种子序列：x0=g, xi=S(xi-1 ), i>0 然后使用R获得伪随机序列：yi=R(xi ), i ≥ 0 该序列必然是周期性的，但只要S和R选的合适，该 周期长度会非常长。 TC中可用rand()和srand(time), 用GNU C更好
§1概率算法的分类 1.基本特征 随机决策 在同一实例上执行两次其结果或过程)可能不 同 在同一实例上执行两次的时间亦可能不太相同 2.分类 Numerical, Monte Carlo, Las vegas, Sherwood 很多人将所有概率算法(尤其是数字的概率算法) 称为 Monte carlo算法
14 1. 基本特征 随机决策 在同一实例上执行两次其结果(或过程)可能不 同 在同一实例上执行两次的时间亦可能不太相同 2. 分类 Numerical, Monte Carlo, Las Vegas, Sherwood. 很多人将所有概率算法(尤其是数字的概率算法) 称为Monte Carlo算法 §1.2 概率算法的分类
§1概率算法的分类 ①数字算法 随机性被最早用于求数字问题的近似解 例如,求一个系统中队列的平均长度的问题,确定算 法很难得到答案 ●概率算法获得的答案一般是近似的,但通常算法执行 的时间越长,精度就越高,误差就越小 ●使用的理由 现实世界中的问题在原理上可能就不存在精确解 例如,实验数据本身就是近似的,一个无理数在计 算机中只能近似地表示 精确解存在但无法在可行的时间内求得 有时答案是以置信区间的形式给出的
15 ① 数字算法 随机性被最早用于求数字问题的近似解 例如，求一个系统中队列的平均长度的问题，确定算 法很难得到答案 ⚫ 概率算法获得的答案一般是近似的，但通常算法执行 的时间越长，精度就越高，误差就越小 ⚫ 使用的理由 – 现实世界中的问题在原理上可能就不存在精确解 例如，实验数据本身就是近似的，一个无理数在计 算机中只能近似地表示 – 精确解存在但无法在可行的时间内求得 有时答案是以置信区间的形式给出的 §1.2 概率算法的分类