By

更新日期:

文章目录

　　这学期刚开始那会儿的时候，付贵抛了一道题目给我，是关于大数的素数判定与合数分解的。
　　具体的题目如下：

　　根据j的取值不同老师给不同的评分标准，j越高越牛逼，付贵那家伙毫不犹豫的选了10，本身p就是个10位的数，也就是说最后的目标数的大小是10的80次方后头还要加个i，i是一到100。

　　当时我就被震惊了，我的天，这么大的数，不得算死。然后付贵就开始倒腾算法，最开始我们两对Rho算法各种鄙视，后来他就开始到处搜罗算法，啥多项式二次筛选法之类的，我也不大懂。他们那边分解80位数的另一个团队光Factor Base分解基就有400万个，无语了都。

　　我那时候刚刚开始自学java，菜鸟一枚，就会造轮子（现在还在造轮子~~~）。结果他丫的把那么挫的一个算法抛给我让我来实现，直接影子都没有。

　　他们那边最牛逼的队伍分解出了十几个数，结果付贵毛都没分解出来，%>_<%。然后告诉我准备抱着必死的信念，明年再修一次这个高级算法课。他那门课这门课，320分满分，两个project，三个作业，一共320分。 125分就给过。结果他小子rp爆棚，审他的居然是个中国的博士生，付贵果断利用母语优势把他对算法的研究大吹特吹一通，结果不知是真被唬住了还是看都是同胞不好意思太残忍，结果还给了他20分，其他两个作业凑足125分还是很有希望的。对此我只能说，小伙子，你太机智了。

　　当然也不是说完全没有收获，起码是了解了大数分解相关的一些基础知识。最后完成了一个小与2^63次方的数的素数判定与合数分解。其实这个2^63就是long型能表示的范围，用long型可以直接进行位运算，对数进行乘除2的运算只要直接左右位移就可以了，所以运算速度非常快，以我的电脑为例，基本上都是秒算。

　　下面po上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
package challenge;

import java.util.Arrays;
import java.util.Scanner;

public class LongRho {

	//判定部分
	//Miller_Rabin()算法素数判定
	//是素数返回true.(可能是伪素数，但概率极小)
	//合数返回false;
	final static int S=20;//随机算法判定次数，S越大，判错概率越小
	public static boolean millerRabin(long n){
		if(n<2)return false;
	    if(n==2)return true;
	    if((n&1)==0) return false;//偶数
	    long x=n-1;
	    long t=0;
	    while((x&1)==0){x>>=1;t++;}
	    for(int i=0;i<S;i++)
	    {
	        long a=(long) (Math.random()*(n-1)+1);//rand()需要stdlib.h头文件
	        if(check(a,n,x,t))
	            return false;//合数
	    }
	    return true;
	}

	//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
	//一定是合数返回true,不一定返回false
	static boolean check( long a, long n, long x, long t)
	{
	     long ret=pow_mod(a,x,n);
	     long last=ret;
	    for(int i=1;i<=t;i++)
	    {
	        ret=mult_mod(ret,ret,n);
	        if(ret==1&&last!=1&&last!=n-1) return true;//合数
	        last=ret;
	    }
	    if(ret!=1) return true;
	    return false;
	}
	
	//计算  x^n %c
	 public static long pow_mod( long x,long  n, long mod)//x^n%c
	{
	    if(n==1)return x%mod;
	    x%=mod;
	     long tmp=x;
	     long ret=1;
	    while(n!=0)
	    {
	        if((n&1)!=0) ret=mult_mod(ret,tmp,mod);
	        tmp=mult_mod(tmp,tmp,mod);
	        n>>=1;
	    }
	    return ret;
	}
	 
	 
	//计算 (a*b)%c.   a,b，直接相乘可能溢出的
	//  a,b,c <2^63
	 public static long mult_mod( long a, long b, long c)
	{
	    a%=c;
	    b%=c;
	    long ret=0;
	    while(b!=0)
	    {
	        if((b&1)!=0){ret+=a;ret%=c;}
	        a<<=1;
	        if(a>=c)a%=c;
	        b>>=1;
	    }
	    return ret;
	}
	 
	//pollard_rho 算法进行质因数分解
		 static long factor[]=new long[100];//质因数分解结果（刚返回时是无序的）
		 static int tol;//质因数的个数。数组小标从0开始

		 static long gcd( long a, long b)
		{
		    if(a==0)return 1;
		    if(a<0) return gcd(-a,b);
		    while(b!=0)
		    {
		         long t=a%b;
		        a=b;
		        b=t;
		    }
		    return a;
		}

		 static long Pollard_rho( long x, long c)
		{
		     long i=1,k=2;
		     long x0=(long) (Math.random()*x);
		     long y=x0;
		    while(true)
		    {
		        i++;
		        x0=(mult_mod(x0,x0,x)+c)%x;
		         long d=gcd(y-x0,x);
		        if(d!=1&&d!=x) return d;
		        if(y==x0) return x;
		        if(i==k){y=x0;k+=k;}
		    }
		}
		static //对n进行素因子分解
		void findfac( long n)
		{
		    if(millerRabin(n))//素数
		    {
		        factor[tol++]=n;
		        return;
		    }
		     long p=n;
		    while(p>=n)p=Pollard_rho(p,(long) (Math.random()*(n-1)+1));
		    findfac(p);
		    findfac(n/p);
		} 
	
	public static void main(String[] args) {
		System.out.println("please enter the number to be deal!");
		Scanner s=new Scanner(System.in);
		String str3=s.next();
		
		long n=Long.parseLong(str3); ;
		System.out.println(n+" is prime number or not?");
		boolean flag=millerRabin(n);
		if (flag) {
			System.out.println("yes");
		}else {
			System.out.println("no");
		}			
        findfac(n);
        if (!flag) {
			System.out.println("How to resolve this number:");
        System.out.print(n+"=");
        for(int i=0;i<tol;i++){
        	if (i==tol-1) {
        		System.out.print(factor[i]);
			}else{
        	System.out.print(factor[i]+"*");}
        	}
		}
        
		
	}

}

　　接下来是运算的测试截图：

　　那两个数是我瞎敲的，如有需要欢迎有爱自取。

　　如何利用这个算法解决之前的10的80次方那个数的问题，有兴趣的同学可以继续倒腾。我的想法是利用一个数组来模拟实现按位运算，再用这个数组存储大数，来实现对大数的快速位运算，不过最后把大数2进制转10进制输出倒是个麻烦事。

　　之前从网上还了解到一种处理方式，是用mapreduce来做的，提交到服务器集群上来跑，可是我没这个条件，所以就没有继续尝试，感兴趣的可以自行百度。

如果觉得文章很有趣或对你带来了帮助，欢迎请我喝杯咖啡哦~

rho大数合数分解
研究僧呀
分享到：微信QQ空间新浪微博FacebookTwitter
文章目录