python实现基于埃拉托斯特尼筛法快速生成素数的优化

作者: 评论: 2条 时间: 2017-03-26 浏览: 993 次

0x00 埃拉托斯特尼筛法

埃拉托斯特尼筛法,也就是我们常说的素数筛选法的一种方法:

0x02 优化

使用了python的生成器方法生成一个超大的字典,这样做的方法是为了减少内存的消耗,循环只需到n的平方根square_root就行了,然后测试一下,最大的8位数基本40s能求出所有质因子。用到一些小优化,在python 2 中while 1:要比while True:要快,if value:要比if value == True:,不相信的话可以测试一下,然后看一下它们生成的操作码,另外大数计算中最好不用for循环,而用while循环。

0x02 实现

#!/usr/bin/env python
# coding=utf-8
# author:admin[@hackfun.org]
# license:GPL v3
# blog:hackfun.org

def gen_super_dict(n):
    """use python generator to generate super dictionary and save memory"""
    i = 2 # 0 and 1 is not prime
    while 1:
        if i > n:
            break
        yield i
        i += 1

def gen_prime_list(n):
    """use prime screen method to generate all prime numbers less than n"""
    super_dict = {}
    primes_list = []

    for x in gen_super_dict(n):
        super_dict[x] = True

    i = 2
    while 1:
        if i > n:
            break
        j = i * i
        while 1:
            if j > n:
                break
            if super_dict[i]:
                super_dict[j] = False
            j += i
        i += 1

    for key,value in super_dict.items():
        if value:
            primes_list.append(key)
    return primes_list

python实现基于米勒拉宾素性检测算法最快的超大数素性检测

作者: 评论: 暂无 时间: 2017-03-26 浏览: 928 次

0x00 米勒拉宾素性检测算法伪代码

米勒拉宾素性检测算法的伪代码:

Input #1: n > 3, an odd integer to be tested for primality;
Input #2: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime

write n − 1 = (2 ^ r) * d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      x ← x^2 mod n
      if x = 1 then
         return composite
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

0x01 实现

一开始针对这个米勒拉宾素性检测算法里的幂模运算,我以为用蒙哥马利算法-快速幂模要比pow()函数更快,结果还是内置的pow()更快:

# x = a^d n n
def montgomery(a, d, n):
    x = 1
    while d:
        if (d & 1):
            x = (x * a) % n
        d >>= 1  
        a = (a * a) % n
    return x

上面的伪代码中a的选取是可以优化的,可以看到下面代码有实现,原理看一下wikipedia

def select_a_list(n):
    if n < 2047:
        return [2,]
    elif n < 1373653:
        return [2, 3]
    elif n < 9080191:
        return [31, 73]
    elif n < 25326001:
        return [2, 3, 5]
    elif n < 3215031751:
        return [2, 3, 7]
    elif n < 4759123141:
        return [2, 7, 61]
    elif n < 1122004669633:
        return [2, 13, 23, 1662803]
    elif n < 2152302898747:
        return [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        return [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        return [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    elif n < 3317044064679887385961981:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    else:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

0x02 测试

用这个方法检测素数,100位10进制数平均0.0003,1000位10进制数平均0.09秒,10000位10进制数平均60秒。

0x03 完整代码

#!/usr/bin/env python
# coding=utf-8
# author:admin[@hackfun.org]
# license:GPL v3
# blog:hackfun.org

def select_a_list(n):
    if n < 2047:
        return [2,]
    elif n < 1373653:
        return [2, 3]
    elif n < 9080191:
        return [31, 73]
    elif n < 25326001:
        return [2, 3, 5]
    elif n < 3215031751:
        return [2, 3, 7]
    elif n < 4759123141:
        return [2, 7, 61]
    elif n < 1122004669633:
        return [2, 13, 23, 1662803]
    elif n < 2152302898747:
        return [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        return [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        return [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    elif n < 3317044064679887385961981:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    else:
        return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def calc_r_d(n):
    n -= 1
    r = 0
    d = n
    while 1:
        if n % 2 != 0:
            break
        r += 1
        d = n / 2
        n /= 2
    return r, d

def miller_rabin_primality_test(n):
    """use miller rabin primality test to judge n whether prime"""
    if n < 0:
        n = -n
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    r, d = calc_r_d(n)
    a_list = select_a_list(n)
    for k in xrange(len(a_list)):
        a = random.sample(a_list, 1)[0] # Select one non-repeating random number from the list at a time
        a_list.remove(a)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for t in xrange(r - 1):
            x = pow(x, 2, n)
            if x ==1:
                return False
            if x == n - 1:
                break
        else:
            return False
    return True

Linux平台C语言Socket编程练习之线程专用数据TSD实现

作者: 评论: 暂无 时间: 2016-11-26 浏览: 1,624 次

0x00 要求

采用多线程并发服务器技术,服务器可以同时接受多个客户的请求。具体要求如下:

服务端

接收并显示与之连接的客户端的名称;

接收客户端发来的字符串,显示出来,并对字符串做反转处理,最后将处理后的字符串发回给客户;

在每个用户退出时要显示该用户输入的所有信息。

客户端

根据客户输入的服务器IP地址,向服务器发起建立连接的请求;

接收客户输入的客户端名称,并把该客户端名称发给服务器;

接收客户输入的字符串,将字符串发送给服务器;

接收服务器发回的反转处理后的字符串并显示。继续接受客户输入的字符串,直到用户输入quit时退出。

0x01 代码

阅读全文»

Linux平台C语言Socket编程练习之多线程服务器

作者: 评论: 暂无 时间: 2016-11-25 浏览: 3,609 次

0x00 要求

采用多线程并发服务器技术,服务器可以同时接受多个客户的请求。具体要求如下:

服务端

接收并显示与之连接的客户端的名称;

接收客户端发来的字符串,显示出来,并对字符串做反转处理,最后将处理后的字符串发回给客户。

客户端

根据客户输入的服务器IP地址,向服务器发起建立连接的请求;

接收客户输入的客户端名称,并把该客户端名称发给服务器;

接收客户输入的字符串,将字符串发送给服务器;

接收服务器发回的反转处理后的字符串并显示。继续接受客户输入的字符串,直到用户输入quit时退出。

0x01 代码

阅读全文»

Linux平台C语言Socket编程练习之多进程服务器

作者: 评论: 暂无 时间: 2016-11-25 浏览: 2,831 次

0x00 要求

采用多进程并发服务器技术,服务器可以同时接受多个客户的请求。具体要求如下:

服务端

接收并显示与之连接的客户端的名称;

接收客户端发来的字符串,显示出来,并对字符串做反转处理,最后将处理后的字符串发回给客户。

客户端

根据客户输入的服务器IP地址,向服务器发起建立连接的请求;

接收客户输入的客户端名称,并把该客户端名称发给服务器;

接收客户输入的字符串,将字符串发送给服务器;

接收服务器发回的反转处理后的字符串并显示。继续接受客户输入的字符串,直到用户输入quit时退出。

0x01 代码

阅读全文»

Linux平台C语言Socket编程练习之UDP套接字

作者: 评论: 暂无 时间: 2016-11-25 浏览: 2,928 次

0x00 要求

实现一个基于UDP协议的服务器-客户端程序,要求完成以下功能:

服务端

接收客户的连接请求,并发送欢迎信息,显示客户的IP地址和端口号;
 
循环接收接收客户传来的字符串,反转后传递给客户; 

客户端

从命令行读入服务器的IP地址;并连接到服务器;
 
循环从命令行读入一行字符串,并传递给服务器,由服务器对字符串反转,并将结果返回客户程序,如果用户输入的是quit,则关闭连接;
 
客户程序显示反转后的字符串;

0x01 代码

阅读全文»

Linux平台C语言Socket编程练习之TCP套接字

作者: 评论: 暂无 时间: 2016-11-03 浏览: 2,841 次

0x00 要求

实现一个基于TCP协议的服务器-客户端程序,要求完成以下功能。

服务端:

接收客户的连接请求,并发送欢迎信息,显示客户的IP地址和端口号;

循环接收接收客户传来的字符串,反转后传递给客户; 

客户端:

从命令行读入服务器的IP地址;并连接到服务器;

循环从命令行读入一行字符串,并传递给服务器,由服务器对字符串反转,并将结果返回客户程序,如果用户输入的是quit,则关闭连接;

客户程序显示反转后的字符串;

0x01 代码

服务端:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>

#define PORT 1234
#define MAXNUMCLINET 20
#define MAXDATASIZE 100


int main()
{
    int socketfd,bindfd,listenfd,connectfd,opt=SO_REUSEADDR;
    ssize_t recv_num,send_num;
    struct sockaddr_in server,client;
    socklen_t addrlen;
    char recv_buf[MAXDATASIZE],send_buf[MAXDATASIZE];
    char wel[]="[*] Welcome! You can input 'quit' to exit:)";

    if((socketfd=socket(AF_INET,SOCK_STREAM,0))==-1)
    {
        perror("socket() error.");
        exit(1);
    }

    setsockopt(socketfd,SOL_SOCKET,SO_REUSEADDR,&opt,sizeof(opt));

    bzero(&server,sizeof(server));
    server.sin_family=AF_INET;
    server.sin_port=htons(PORT);
    server.sin_addr.s_addr=htonl(INADDR_ANY);

    if((bindfd=bind(socketfd,(struct sockaddr *)&server,sizeof(server)))==-1)
    {
        perror("bind() error.");
        exit(1);
    }

    if((listenfd=listen(socketfd,MAXNUMCLINET))==-1)
    {
        perror("listen() error.");
        exit(1);
    }

    if((connectfd=accept(socketfd,(struct sockaddr *)&client,&addrlen))==-1)
    {
        perror("accept() error.");
        exit(1);
    }

    if((send(connectfd,wel,sizeof(wel),0))==-1)
    {
        perror("send welcome messages fail.");
        exit(1);
    }

    printf("You got a connection from client IP:%s, PORT:%d\n",inet_ntoa(client.sin_addr),ntohs(client.sin_port));

    while(1)
    {
        if((recv_num=recv(connectfd,recv_buf,MAXDATASIZE,0))==-1)
        {
            perror("recv() error.");
            exit(1);
        }

        printf("[*] Received string:%s\n",recv_buf);

        size_t len=strlen(recv_buf);
        for(int i=0; i<(len/2); ++i)
        {
            char tmp=recv_buf[i];
            recv_buf[i]=recv_buf[len-1-i];
            recv_buf[len-1-i]=tmp;
        }

        strcpy(send_buf,recv_buf);
        printf("[>] Send reverse string:%s\n",send_buf);

        if((send_num=send(connectfd,send_buf,MAXDATASIZE,0))==-1)
        {
            perror("send() error.");
            exit(1);
        }

        if(!strcmp(send_buf,"tiuq"))
        {
            close(connectfd);
            break;
        }
    }
    close(connectfd);
    close(listenfd);
    return 0;
}

客户端:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>

#define PORT 1234
#define MAXDATASIZE 100

int main(int argc,char* argv[])
{
    int socketfd;
    ssize_t send_num,recv_num;
    char send_buf[MAXDATASIZE],recv_buf[MAXDATASIZE],wel[MAXDATASIZE];
    struct hostent* remote_host;
    struct sockaddr_in server;

    if(argc!=2)
    {
        printf("Usage:%s <IP address>\n",argv[0]);
        exit(1);
    }

    if((remote_host=gethostbyname(argv[1]))==NULL)
    {
        perror("gethostbyname() error.");
        exit(1);
    }

    if((socketfd=socket(AF_INET,SOCK_STREAM,0))==-1)
    {
        perror("socket() error.");
        exit(1);
    }

    bzero(&server,sizeof(server));
    server.sin_family=AF_INET;
    server.sin_port=htons(PORT);
    server.sin_addr=*((struct in_addr*)remote_host->h_addr);

    if((connect(socketfd,(struct sockaddr*)&server,sizeof(server)))==-1)
    {
        perror("connect() error.");
        exit(1);
    }

    if ((recv(socketfd,wel,MAXDATASIZE,0))==-1)
    {
        perror("[!] Receive welcome message fail.");
        exit(1);
    }
    wel[sizeof(wel)-1]='\0';
    printf("%s\n", wel);

    while(1)
    {
        printf("[*] Input string:");
        scanf("%s",&send_buf);
        send_buf[strlen(send_buf)]='\0';

        if((strlen(send_buf))>100)
        {
            printf("[!] Only supports sending fewer than 100 characters.");
            exit(1);
        }

        if((send_num=send(socketfd,send_buf,MAXDATASIZE,0))==-1)
        {
            perror("send() error.");
            exit(1);
        }

        if((recv_num=recv(socketfd,recv_buf,MAXDATASIZE,0))==-1)
        {
            perror("recv() error.");
            exit(1);
        }

        printf("[>] Received reverse string:%s\n",recv_buf);
        if(!strcmp(recv_buf,"tiuq"))
        {
            close(socketfd);
            break;
        }
    }
    close(socketfd);
    return 0;
}

0x02 演示

服务端:

Linux C socket programming practice of the TCP socket server demonstration.png

客户端:

Linux C socket programming practice of the TCP socket client demonstration.png

0x03 心得

在编写代码时一定注意程序的逻辑,先做什么,再做什么,同时要注意服务端和客户端的处理同步。在调用函数时要注意传入的参数类型的一致性以及函数返回值的类型,还有调用bind、accept、connect函数是要注意把server,client的sockaddr_in套接字地址结构强制转化为通用套接字地址结构sockaddr,类似:

bindfd=bind(socketfd,(struct sockaddr *)&server,sizeof(server))

中的(struct sockaddr *)&server。还要注意一个坑,在服务端accept函数的第一个参数必须是socket函数产生的套接字描述符,在本例正确的写法是这样的:

...
if((socketfd=socket(AF_INET,SOCK_STREAM,0))==-1)
...
if((connectfd=accept(socketfd,(struct sockaddr *)&client,&addrlen))==-1)
...

如果你像我一开始写成:

if((connectfd=accept(listenfd,(struct sockaddr *)&client,&addrlen))==-1)

就会报类似的错误:

accept() error.: Socket operation on non-socke

原因是虽然socket()、bind()、listen()、accept()等函数返回的值都是int类型的,但是socket()返回值的意义和其他的函数返回值却不相同,socket()返回的是一个套接字描述符,而其他函数调用成功返回0,出错返回-1,并置errno值,所以要注意这个区别。
另外在判断字符是否相同不要用"=="等号去判断:

if(send_buf=="tiuq")

而是最好使用strcmp()函数:

if(!strcmp(send_buf,"tiuq"))

要不然而出现类似的警告:

warning: comparison with string literal results in unspecified behavior [-Waddress]

虽然不会出现error,但是你懂的,处女座( •̀ ω •́ )y
在拷贝字符串数组不要错误地使用"="去赋值:

send_buf[MAXDATASIZE]=recv_buf[MAXDATASIZE];

正确的方法是使用strcpy()函数:

strcpy(send_buf,recv_buf);

wooyun drops乌云知识库全部文章打包离线下载

作者: 评论: 4条 时间: 2016-07-27 浏览: 28,784 次

0x00 前言

乌云网是一个安全研究者集聚地,是一个非常值得推荐学习的地方,特别是各路大牛分享技术文章的乌云知识库,由于近几天乌云在进行升级,导致很多小伙伴看不了乌云知识库里的技术文章,所以分享一份来自JmNkS的乌云知识库全部文章包,一共是1157篇,赶紧下载去学习一波吧!另外正如乌云所说:与其听信谣言不如相信乌云,相信过不了多久乌云会正常回归!

阅读全文»