Pythorn Library for Primes Algorithms
nprime的Python项目详细描述
安装
要安装软件包，请使用pip:
pip install nprime
简介
关于素数的一些算法。您可以在 文件nprime/pryprime.py
算法开发：
- 埃拉托舍内斯筛基
- 费马检验（基于费马定理）
- 素数生成函数
- miller-rabin预测算法
规格
- 语言：python3.5.2
- 包装：
- 首选基本的python包
- matplotlib v2.0-图形和数学
数学
下面是一些有助于理解某些算法的信息
同余
“≡”表示全等，a ≡ b (mod m)表示 m / (a-b), ∃ k ∈ Z验证a = kn + b
这意味着：
a ≡ 0 (mod n) <-> a = kn <-> "a" is divisible by "n"
强伪素数
强壮的 pseudoprime到 基a是带有n-1 = d·2^s的奇数复合数n（对于 d奇数）其中a^d = 1(mod n)或a^(d·2^r) = -1(mod n) 对于一些r = 0, 1, ...,s-1
埃拉托斯坦筛
如何使用
发现素数和 他们的组合达到了极限。它返回一个字典：-键是 n以内的素数-该值是这些素数的组合列表 最大N
fromnprime.pyprimeimportsieve_eratosthenes# With as a parameter the upper limitsieve_eratosthenes(10)>>{2:[4,6,8],3:[6,9],5:[],7:[]}
理论
这个筛子标记为每个质数的倍数。它是一个 找到素数的有效方法。对于n ∈ N和n > 2，对于 ∀ a ∈[2, ..., √n]则n/a ∉ N为真。
费马定理
如何使用
取t随机数a的概率算法及其测试 关于n > 1素数概率的fermat定理是正确的 1 - 1/(2^t)如果n通过测试，则返回布尔值：true。
fromnprime.pyprimeimportfermat# With n the number you want to testfermat(n)
理论
如果n是素数，则∀ a ∈[1, ...,n-1]
a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 1
米勒拉宾
如何使用
一种概率算法，用于确定给定数（n>； 1）是否为质数。miller_rabin测试重复了t次 得到更准确的结果。如果n通过 测验。
fromnprime.pyprimeimportmiller_rabin# With n the number you want to testmiller_rabin(n)
理论
对于n ∈ N和n > 2，随机查找a ∈ {1,...,n−1}。 d和s，例如使用n - 1 = 2^s * d（使用d odd）if (a^d)^2^r ≡ 1 mod n对于0到s-1中的所有r，则n是 最好的。
测试输出为n中可能的“a值”的1/4，因此 试验重复t次。
欢迎加入QQ群-->： 979659372
