文档章节

随机化算法与素性测试

温安适
 温安适
发布于 2017/02/11 09:08
字数 1095
阅读 476
收藏 13

前言

大家好,这是上班以后的第一篇blog,预计后边算法还有2篇。也就是说这是本人算法系列倒数第3篇,感谢大家的指正,今天是说明随机化算法。

随机数发生器

真正的随机性在计算机上,是不可能的!因为这些数的生成依赖于算法,从而不可能是随机的。所以计算机产生的都是伪随机数

基本理论

生产随机数的最简单办法是线性同余数发生器

线性同余数发生器原理

从上面的公式可知:

  1. 为了开始这个序列必须给出x0(x0叫做种子)。如果x0=0,那么这个序列绝不会是随机的。
  2. M为素数,则xi绝不会是0.

如果A和M选择的正确,那么1<=x0< M 都是等概率出现的。

举例说明A和M选值的重要性

  1. M=11,A=7,x0=1,所生成的随机数为: 7,5,2,3,10,4,6,9,8,1,7,... 在M-1=10后,该序列将重复。所以M必须为非常大的素数
  2. 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 )与系统当前纳秒时间进行异或。

具体实现如下(以下代码为自实现,非java源代码):

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));
    }

随机化算法应用之素性测试

素性测试介绍

近似确定一个大数是否是素数。 素性测试宣称一个数不是素数,那么可以肯定这个数不是素数,若宣称一个数是素数,那么这个数将以高概率是素数。 素数测试依赖于两个定理,下面介绍。

两个定理

  1. 费马小定理 如果一个数P是素数,那么0<A<P,那

费马小定理

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

费马小定理举例说明1

该定理为高概率确定一个数是否是素数提供了理论依据,我们只需校验是否

费马小定理举例说明2

,若不成立P一定不是素数。反之有可能是素数 实验表明,运行50次素数,算法错误的概率为25%。

  1. 如果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);
			}
		}
	}
}

总结

  • 线性同余数发生器是生成伪随机数的基础。
  • Java中使用48位线性同余数发生器,并只返回高32位。

代码地址

github地址

仿Java实现随机化算法

素性测试地址

码云地址

仿Java实现随机化算法

素性测试地址

© 著作权归作者所有

温安适

温安适

粉丝 117
博文 30
码字总数 49620
作品 0
朝阳
后端工程师
私信 提问
加载中

评论(2)

温安适
温安适 博主

引用来自“田舍先生”的评论

算法是一个非常细致的东西,这样深入的研究非常有内涵,手动点赞。
感谢支持
O龙猫O
O龙猫O
算法是一个非常细致的东西,这样深入的研究非常有内涵,手动点赞。
Pollard Rho算法浅谈

Pollard Rho介绍 Pollard Rho算法是Pollard[1]在1975年[2]发明的一种将大整数因数分解的算法 其中Pollard来源于发明者Pollard的姓,Rho则来自内部伪随机算法固有的循环 Pollard Rho算法在其他...

A_Fool
05/26
0
0
米勒罗宾素数检测(Miller-Rabin)

适用范围:较大数的较快素性判断 思路: 因为有好的文章讲解具体原理(见参考文章),这里只是把代码的大致思路点一下,读完了文章如果还有些迷糊,可以参考以下解释 原理是费马小定理:如果...

小张人
07/28
0
0
自动化测试之随机化测试思想

自动化测试发展到今天,已经越来越平台化和智能化了。 就平台化而言,我们可以在平台上管理元素对象、管理用例、调度执行、生成结果和报告,从而让我们写的代码中更多的只体现具体用例的实现...

测试开发栈
2017/04/24
0
0
Pollard-rho的质因数分解

思路:见参考文章(原理我是写不粗来了) 代码: 用到了快速幂,米勒罗宾素性检验。 1 #include 2 #include 3 #include 4 using namespace std; 5 long long an[] = {2,3,5,7,11,13,17,61}; ...

小张人
07/28
0
0
前沿 | 从虚拟世界伸到现实的机械臂,靠摄像机就能玩转任何物体

  选自OpenAI   机器之心编译      OpenAI 训练了一个机械臂,能够非常灵巧地控制物体。据介绍,该系统名为 Dactyl,经过了完全模拟训练,能够把知识迁移到现实中,即使用 OpenAI 一...

机器之心
2018/07/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部