首页
论坛
课程
招聘
[原创]质因数分解C版
2009-7-3 19:22 5878

[原创]质因数分解C版

2009-7-3 19:22
5878
【原创】质因数分解C版
最大数支持4294967294也就是scanf("%lu")最大的数。
因为分解4294967294只需要
65535的质数表。所以速度很快。

理论上2.5×10^17的分解都可以在很短的时间内分出来。
2.5×10^17需要500000000的质数表。这里的算法我机器用了12.015 s

质数表部分算法参考了arab和erex的算法。并做了一些优化.
http://bbs.pediy.com/showthread.php?t=89497
但是只用到30因为30就可以节省3/4的空间用到2310 也就节省4/5.对速度影响较重。
arab的算法算500000000需要71s
没做空间优化的算法因为会用到虚拟内存速度影响很大。
/**

 *   N*30+1, N*30+7, N*30+11, N*30+13, N*30+17, N*30+19, N*30+23, N*30+29

**/

#include "stdio.h"
#include "math.h"

long unsigned NUM;

char* real;;

long unsigned k;


inline void wtable(register unsigned long a)
{
		register unsigned long b;
		b=a/30;
		a=a%30;
		switch(a)
		{
			case 1:real[b]=real[b]&&!1;break;
			case 7:real[b]=real[b]&&!(1<<1);break;
			case 11:real[b]=real[b]&&!(1<<2);break;
			case 13:real[b]=real[b]&&!(1<<3);break;
			case 17:real[b]=real[b]&&!(1<<4);break;
			case 19:real[b]=real[b]&&!(1<<5);break;
			case 23:real[b]=real[b]&&!(1<<6);break;
			case 29:real[b]=real[b]&&!(1<<7);
			default:;
		}
}

inline int rtable(register unsigned long a)
{
	register unsigned long b;
	if(a>5)
	{
		b=a/30;
		if(real[b]==0)return 0;
		a=a%30;
		switch(a)
		{
			case 1:return real[b]&&1;
			case 7:return real[b]&&(1<<1);
			case 11:return real[b]&&(1<<2);
			case 13:return real[b]&&(1<<3);
			case 17:return real[b]&&(1<<4);
			case 19:return real[b]&&(1<<5);
			case 23:return real[b]&&(1<<6);
			case 29:return real[b]&&(1<<7);
			default:return 0;
		}
	}
	else
	{
		switch(a)
		{
			case 2:return 1;
			case 3:return 1;
			case 5:return 1;
			default:return 0;
		}
	}
}

void suShu()
{


	register unsigned long i=3,j,step;

	for(j=0; j<[COLOR="Red"]NUM/30+1[/COLOR]; j++)
	{
		real[j] = 0xFF;//初始化数组
	}

	while(i<=k)
	{
	if(rtable(i)==0)
		{
			step=i<<1;
			for(j=i*i;j<=NUM;j+=step)
			wtable(j);
		}
		++i;
		++i;
	}

}


int main()
{
	unsigned long in;
	register unsigned long i;
	int f=0;
	printf("please inpout the No.:\n");
	scanf("%lu",&in);
	NUM=(unsigned long)sqrt((long double)in);
	real = new char[[COLOR="red"]NUM/30+1[/COLOR]];
	k = (long)sqrt((double)NUM);
	suShu();
	printf("%lu=",in);
	for (i=2;i<=NUM;i++)
	{
		if(rtable(i)==0)
			continue;
		else
		{
			if(in%i!=0)
				continue;
			else
			{
				in=in/i;
				i--;
				printf("%ld*",i+1);
				f=1;
			}
		}

	}
	if(in==1&f==1)printf("\b");
	else if(f==1)printf("%ld",in);
	else if(in<2)printf("\b can not factorization !");
	else printf("\b is prime number !");

  return 0;
}



ps:2.5×10^17基本上是56-58位2进制。而真正的RSA一般要求512位密匙。所以RSA还是相当安全的.

【公告】看雪团队招聘安全工程师,将兴趣和工作融合在一起!看雪20年安全圈的口碑,助你快速成长!

收藏
点赞0
打赏
分享
最新回复 (4)
雪    币: 143
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
Yangs 活跃值 2009-7-3 22:44
2
0
修改一下。刚刚写错了.应该是空间压缩30倍.
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
游客 活跃值 2009-7-7 23:40
3
0
我写的那个程序只是为了对应梵听的程序, 生成一个可读的质数表而已.
但试除法需要的是质数表本身, 所以还不如直接分配一块内存来存放质数表呢.
按 2^16 * 2^16 = 2 ^ 32 来看, 要分解 2^32 内的任意数, 只需要存放 2^16 内的所有质数即可.
而按 2310 理论, 2 ^ 16 内最多只有 2 ^16 / 2310 * 480 = 13617 个质数, 每个质数占 4 个字节, 总共不过 54K 内存而已.
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
游客 活跃值 2009-7-7 23:45
4
0
建议看看 Miracl 库里的 factor, 里面有各种传统的质因数分解算法.
http://www.shamus.ie/
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-7-8 02:01
5
0
分解RSA模数算法研究
Research on Algorithms for Factoring RSA Modulus
<<微机发展>>2005年 第15卷 第06期
作者: 褚一平, 陈勤,
期刊 ISSN : 1005-3751(2005)06-0091-02
RSA密码系统的安全性是基于大数分解困难问题.文中简要地介绍了目前攻击RSA密码系统的常用大数分解算法.详细阐述了大数分解法二次筛选法(Quadratic sieve,QS)以及它的改进算法MPQS和PPMPQS的理论基础.根据PPMPQS的原理,设计了一种快速寻找PP关系的方法以及分析了算法复杂度,并利用VC6实现了PPMPQS,成功分解了十进制70位的大数.
关键词: RSA, 大数分解算法, 二次筛选法, 多项式二次筛选法, 双大素数二次筛选法,

Source from http://scholar.ilib.cn/A-QCode~wjfz200506031.html
游客
登录 | 注册 方可回帖
返回