大家好,这是上班以后的第一篇blog,预计后边算法还有2篇。也就是说这是本人算法系列倒数第3篇,感谢大家的指正,今天是说明随机化算法。
随机数发生器
真正的随机性在计算机上,是不可能的!因为这些数的生成依赖于算法,从而不可能是随机的。所以计算机产生的都是 伪随机数
基本理论
生产随机数的最简单办法是 线性同余数发生器 。

线性同余数发生器公式
从上面的公式可知:
- 为了开始这个序列必须给出x0( x0叫做种子 )。如果x0=0,那么这个序列绝不会是随机的。
- M为素数,则xi绝不会是0.
如果A和M选择的正确,那么1<=x0< M 都是等概率出现的。
举例说明A和M选值的重要性
- M=11,A=7,x0=1,所生成的随机数为: 7 ,5,2,3,10,4,6,9,8,1, 7 ,… 在M-1=10后,该序列将重复。 所以M必须为非常大的素数
- A的选择也将影响随机性 ,例如A=5,M=11,x0=1 将有一个短周期: 5,3,4,9,1,5,…
Java中实现
在Java中使用修改后的48比特线性同余数发生器, 并只返回高32位 。以防止低阶bit位上循环的问题。

Java中48线性同余数发生器公式
其中: multiplier=25214903917,B=48,addend=11 而x0采用 (8682522807148012L*181783497276652981L )与系统当前纳秒时间进行异或。
private static final Long multiplier=25214903917l; private static final long addend = 11l; private static final long mask = (1L << 48) - 1; private AtomicLong seed;//保证线程安全 public MyRandom2(){ this.seed = new AtomicLong((8682522807148012L*181783497276652981L )^System.nanoTime()); } public int nextInt() { return next(32); } private int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) % mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); } 复制代码
随机化算法应用之素性测试
素性测试介绍
近似确定一个大数是否是素数。 素性测试宣称一个数不是素数,那么可以肯定这个数不是素数,若宣称一个数是素数,那么这个数将以高概率是素数。 素数测试依赖于两个定理,下面介绍。
两个定理
- 费马小定理 如果一个数P是素数,那么0<A<P,那

费马小定理
数论中非常著名的定理 例如: 11是素数

费马小定理举例说明1
该定理为高概率确定一个数是否是素数提供了理论依据,我们只需校验是否

费马小定理举例说明2
,若不成立P一定不是素数。反之有可能是素数 实验表明,运行50次素数,算法错误的概率为25%。
- 如果P是素数,0<A<P,那么

扩展定理
仅有两个解 A=1或者A=P-1。 因此在计算

扩展定理1
的任意时刻,发现违背该定理,即可确认该数不是素数。
代码
结合两个定理,以随机数生产A,的素性测试代码如下:
package chapter10.random; import java.util.Random; /** * 一种概率,测试一个数是否是素数 * 依据 * 1.费马小定理:如果P是素数,且0<A<P,那么A^(P-1)≡(1 mod P)<br/> * 2. 如果P是素数且 0<A<P,那么X^2≡(1 mod P),仅有两个解X=1,P-1<br/> * @author Administrator */ public class Witness { /** * A^(P-1)≡(1 mod P) * 此处P-1 对应变量n */ private static long witness(long a,long n,long p){ if(n==0){ return 1; } long x=witness(a,n/2,p); if(x==0){ return 0; } //校验定理2 long y=(x*x)%p; if(y==1&&x!=1&&x!=p-1){ return 0; } //校验定理2结束 if(n%2!=0){//奇数,修正A^p-1的解 y=(a*y)%p; } return y; } /** * 尝试五次 */ public static final int TRIALS = 5; /** * 素性测试 */ public static boolean isPrime( long n ){ Random r = new Random( ); for( int counter = 0; counter < TRIALS; counter++ ) if( witness( r.nextInt( (int) n - 3 ) + 2, n - 1, n ) != 1 ) return false; return true; } public static void main(String[] args) { for(int i=100;i<200;i++){ if(isPrime(i)){ //101 103 107 109 113 //127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 //199 System.out.println(i); } } } } 复制代码
原文
https://juejin.im/post/5d64a51af265da03d063af57
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 随机化算法与素性测试