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

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

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 浏览: 85 次

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,277 次

0x00 要求

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

服务端

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

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

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

客户端

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

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

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

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

0x01 代码

阅读全文»

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

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

0x00 要求

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

服务端

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

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

客户端

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

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

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

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

0x01 代码

阅读全文»

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

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

0x00 要求

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

服务端

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

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

客户端

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

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

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

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

0x01 代码

阅读全文»