大素数生成.txt

大素数生成算法的实现

import java.util.*;
import java.lang.*;
class BigInt{
public final long JINGZHI=0x40000000;
public final int ARRAY=10;
public long s[]=new long[2*ARRAY]; /*存放大数*/
public int length;
public BigInt(){
this.itarray();
}
public BigInt(long a[]){
for(int i=0;i this.s[i]=a[i];
this.length=a.length;
}
public BigInt(BigInt a){
this.mov(a);
}
public void itarray()/*初始化类*/
{
int i;
for(i=0;i<2*ARRAY;i++)
{
this.s[i]=0;
}
this.length=1;
}
public void mov(BigInt b)/*复制类*/
{
int i;
for(i=0;i {
this.s[i]=b.s[i];
}
this.length=b.length;
}
public void mov(long b){
this.itarray();
this.s[0]=b;
}
public int cmp(BigInt b)/*比较两个大数*/
{
int i;
if(this.length>b.length) return 1;
if(this.length for(i=this.length-1;i>=0;i--)
{
if(this.s[i]>b.s[i]) return 1;
if(this.s[i] }
return 0;
}
public int cmp(long b){
int i;
if(this.length>1) return 1;
else if(this.s[0]>b) return 1;
else if(this.s[0] return 0;
}
public void add(BigInt b)/*加法运算*/
{
int k=0,i,length;
long temp,origin;
if(this.length>=b.length) length=this.length;
else length=b.length;
for(i=0;i {
temp=this.s[i]+k;
if(temp>=JINGZHI) k=1;
else k=0;
origin=temp%JINGZHI;
this.s[i]=origin;
temp=this.s[i]+b.s[i];
if(temp>=JINGZHI) k++;
origin=temp%JINGZHI;
this.s[i]=origin;
}
if(k!=0) {this.s[i]=k;this.length=length+1;}
else {this.length=length;}
}
public void add(long a){
int k=0,i,length;
long temp,origin;
temp=this.s[0]+a;
if(temp>=JINGZHI) k=1;
origin=temp%JINGZHI;
this.s[0]=origin;
for(i=1;i {
temp=this.s[i]+k;
if(temp>=JINGZHI) k=1;
else k=0;
origin=temp%JINGZHI;
this.s[i]=origin;
}
if(k!=0) {this.s[i]=k;this.length=this.length+1;}
}
public void sub(BigInt b) /*减法运算*/
{
int z,k=0,i;
BigInt e=new BigInt();
for(i=0;i {
if(this.s[i]-k>=b.s[i])
{
e.s[i]=this.s[i]-b.s[i]-k;
k=0;
}
else
{
e.s[i]=this.s[i]+JINGZHI-b.s[i]-k;
k=1;
}
}
while(i>0&&e.s[i-1]==0) i--;
if(i!=0) e.length=i;
else e.length=1;
this.mov(e);
}
public void sub(long a)
{
int k=0,i;
BigInt e=new BigInt();
e.s[0]=this.s[0]-a;
if(e.s[0]<0) {e.s[0]+=JINGZHI;k=1;}
for(i=1;i {
if(this.s[i]-k>=0)
{
e.s[i]=this.s[i]-k;
k=0;
}
else
{
e.s[i]=this.s[i]+JINGZHI-k;
k=1;
}
}
while(i>0&&e.s[i-1]==0) i--;
if(i!=0) e.length=i;
else e.length=1;
this.mov(e);
}
public void mul(BigInt b) /*乘法运算*/
{
BigInt c,temp;
int i,j,k,length;
c=new BigInt();
temp=new BigInt();
for(i=0;i {
c.itarray();
c.length=this.length;
for(j=0;j {
c.s[i+j]=c.s[i+j]+this.s[j]*b.s[i];
c.s[i+j+1]=c.s[i+j]>>30;
c.s[i+j]=c.s[i+j]%JINGZHI;
}
if(c.s[i+j]!=0)
{
c.length=i+j+1;
}
else c.length=i+j;
temp.add(c);
}
this.itarray();
this.mov(temp);
}
public void mul(long a){
long m,k=0;
int i;
for(i=0;i {
m=this.s[i];
m=m*a+k;
this.s[i]=m%JINGZHI;
k=m>>30;
}
if(k>0) {this.s[i]=k;this.length++;}
}
public void div(BigInt a)
{
BigInt x,y,z,temp;
int i,len;
long num,div;
if(a.length==1) this.div(a.s[0]);
else
{
x=new BigInt();
y=new BigInt(this);
z=new BigInt();
temp=new BigInt();
while(y.cmp(a)>=0)
{ 
div=y.s[y.length-1];
num=a.s[a.length-1];
len=y.length-a.length;
if((div==num)&&(len==0)){x.add(1);break;}
if((div<=num)&&len>0) {len--;div=(div<<30)+y.s[y.length-2];}
div=div/(num+1);
z.mov(div);
if(len>0)
{
z.length+=len;
for(i=z.length-1;i>=len;i--) z.s[i]=z.s[i-len];
for(i=0;i }
x.add(z);
temp.mov(a);
temp.mul(z);
y.sub(temp);
}
this.mov(x);
}
}
public void div(long a)
{
long div,mul;
long carry=0;
BigInt b=new BigInt();
b.mov(this);
if(b.length==1){b.s[0]=b.s[0]/a;}
else
{
for(int i=b.length-1;i>=0;i--)
{
div=carry;
div=(div<<30)+b.s[i];
b.s[i]=div/a;
mul=(long)(div/a)*a;
carry=(div-mul);
}
}
if(b.s[b.length-1]==0) b.length--;
this.mov(b);
}
public void mod(BigInt a)
{
BigInt y,z,temp;
y=new BigInt(this);
z=new BigInt();
temp=new BigInt();
int i,len;
long num,div;
while(y.cmp(a)>=0)
{ 
div=y.s[y.length-1];
num=a.s[a.length-1];
len=y.length-a.length;
if((div==num)&&(len==0)){y.sub(a);break;}
if((div<=num)&&len>0) {len--;div=(div<<30)+y.s[y.length-2];}
div=div/(num+1);
z.mov(div);
z.mul(a);
if(len>0)
{
z.length+=len;
for(i=z.length-1;i>=len;i--) z.s[i]=z.s[i-len];
for(i=0;i }
y.sub(z);
}
this.mov(y);
}
public void mod(long a){
long carry,div;
if(this.length==1) this.s[0]=this.s[0]%a;
else{
carry=0;
for(int i=this.length-1;i>=0;i--)
{
div=this.s[i];
div=div+(carry<<30);
carry=div%a;
}
this.s[0]=carry;
this.length=1;
}
}
public BigInt mon(BigInt b,BigInt c) /*蒙哥马利算法求a^b%c*/
{
BigInt x,z,temp;
long m,n=30;
x=new BigInt(this);
z=new BigInt(b);
temp=new BigInt();
for(int i=z.length-1;i>=0;i--)
{
m=z.s[i];
n=30;
while((m&JINGZHI)==0) {m=m<<1;n--;}
if(i==z.length-1) {m=m<<1;n--;}
while(n>=0)
{
if((m&JINGZHI)==JINGZHI)
{ 
temp.mov(x);
x.mul(temp);
x.mod(c);
x.mul(this);
x.mod(c);
}
else
{
temp.mov(x);
x.mul(temp);
x.mod(c);
}
n--;
m=m<<1;
}
}
return x;
}
}

public class Even{
public static int primetable[]=
{ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 
359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 
479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 
557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 
613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 
673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 
743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 
821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 
953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 
1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 
1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 
1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 
1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 
1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 
1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 
1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 
1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 
1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 
1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063,
2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 
2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 
2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 
2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 
2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 
2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 
2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 
2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 
2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,
2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001,
3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 
3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 
3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343,
3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 
3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 
3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581,
3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 
3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 
3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 
3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 
3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001
};
public BigInt even=new BigInt();
public final long JINGZHI=0x40000000;
public final int ARRAY=10; 
public void bignum()/*随机产生大数*/
{
int i;
long greatvalue=JINGZHI-1;
for(i=0;i {

this.even.s[i]=(long)Math.round(Math.random()*greatvalue);
}
this.even.s[ARRAY-1]=this.even.s[ARRAY-1]|0x30000000;
this.even.s[0]=this.even.s[0]|1;
this.even.length=ARRAY;
}
public void get_even() 
{
int i=0,j;
long from,to;
BigInt a,temp;
Date t;
t=new Date();
from=t.getTime();
while(i==0)
{
this.bignum();
this.print();
j=0;
while(j<=64*ARRAY)
{
i=this.rm();
if(i==1) break;
this.even.add(2);
if(this.even.s[2*ARRAY-1]>=JINGZHI) break;
j++;
} 
}
t=new Date();
to=t.getTime();
System.out.println("用了"+(to-from)/1000+"秒");
}
public int rm() /*Rabin-Miller算法测试大素数*/
{
int i,j,pass;
long num,odd;
BigInt m,a1,a2,z,p;
m=new BigInt(this.even);
for(i=0;i {
m.mod(primetable[i]);
if(m.s[0]==0&&m.length==1) return 0;
m.mov(this.even);
}
Even a=new Even();
a1=new BigInt();
a2=new BigInt();
z=new BigInt();
m.mov(this.even);
m.s[0]--;
for(i=0;i {

a.even.s[i]=(long)Math.round(Math.random()*this.even.s[i]);
}
a.even.length=ARRAY;
for(i=0;i<5;i++)
{
pass=0;
a.even.sub((long)Math.round(Math.random()*(JINGZHI-1))); 
a2.mov(m);
while((a2.s[0]&1)==0)
{
for(j=0;j {
a2.s[j]=a2.s[j]>>1;
if((a2.s[j+1]&1)==1) a2.s[j]=a2.s[j]|0x20000000;
}
if(a2.s[a2.length-1]==0) a2.length--;
z=a.even.mon(a2,this.even);
if(z.cmp(m)==0) {pass=1;break;}
}
if((z.length==1)&&(z.s[0]==1)) pass=1;
if(pass==0)return 0;
}
return 1;
}
public void print()
{ BigInt e1,e2;
int out[]=new int[1024];
int i,j;
char ch;
e1=new BigInt();
e2=new BigInt();
e1.mov(this.even);
i=0;
while(e1.length>0&&e1.s[e1.length-1]>0)
{
e2.mov(e1);
e2.mod(10);
out[i]=(int)e2.s[0];
e1.div(10);
i++;
}
for(j=i-1;j>=0;j--)
System.out.print(out[j]);
System.out.println();
System.out.println(i);
}
}
class check{
public static void main(String args[]){
Even a=new Even();
a.get_even();
a.print();
}
}