python中Miller Rabin检验中的素数计数问题

文章/答案/技术大牛

发布

1回答

python、jupyter-notebook

我正在尝试用米勒拉宾测试来计算质数，上面的带子和下面的带子，比如在1000和1000000之间会产生多少个质数我错过了计数函数，这里有谁能帮我解决这个问题，你的意见和建议将非常感谢，并将米勒拉宾代码粘贴在下面，等待你的好意反馈import time lower=int(input(

浏览 21提问于2020-05-14得票数 1

1回答

如何更好地产生大素数:筛选，然后随机采摘或随机采摘，然后检查？

rsa、prime-numbers

我正在编写RSA算法，我想知道选择初始素数(p和q)的最佳和/或通常方法是什么。我知道有两种方法可以实现这一点，一种是基于素数筛子，另一种是基于素数测试：随机挑选一个数字，然后测试它是否是素数。从安全和效率的角度来看，什么是最好的方法？

浏览 0提问于2012-02-04得票数 9

回答已采纳

3回答

测试Miller Rabin时的Stackoverflow异常

java、exception、primes

全, } { }在

浏览 7提问于2010-12-05得票数 0

回答已采纳

1回答

用Python优化Miller-Rabin素数检验

python、performance、primes

我在用Python写一个Miller-Rabin原始性测试。当我简要地观察了其他人是如何处理这个问题的时候，我决定自己尝试解决这个问题。除了我选择的语言之外，我如何优化这段代码呢？任何建议都是受欢迎的，不要犹豫，要残忍地诚实。def miller_rabin_primality_test(n): m = n - 1 n = n

浏览 0提问于2018-03-05得票数 4

4回答

最想要的素数

code-golf、sequence、primes

输出如下形式的所有素数的序列：123...91011...(n-1)n(n-1)..11109...321。也就是说，升序十进制数一直到某个n，然后是一个降尾，所有这些都是串联的。背景1 -> 12345678910987654321 (n=10)没有更多的术语是已知的，但它很可能有无限多。

浏览 0提问于2021-12-18得票数 14

1回答

生成大的(512 bit+)素数Python3.6

rsa、primes、python-3.6

在过去的一周半的时间里，我一直在尝试用Python for RSA加密来生成大质数，但没有成功。费马质数测试在512比特的规模上是不可行的，我也不能完全理解米勒-拉宾。(我13岁)所有的在线脚本似乎都适用于我正在使用的Python版本以下的版本。我应该怎么做才能生成大量的素数？(是的，概率素数是可以的。)

浏览 48提问于2017-08-29得票数 2

1回答

Python素数测试程序中的内存错误

python-3.x、primality-test

check = False result = (result ** 2) % mreturn check 我需要编写一个原始测试python程序来测试非常大的数字，比如至少100位数字。以上代码是Miller Rabin确定性素数检验代码的一部分，用于重复平方。对于大量的数据来说，它的工作速度非常慢。我怎样才能加快速度？这是为了一个项目。谢谢!

浏览 2提问于2016-04-26得票数 0

回答已采纳

1回答

索菲娅·杰曼素数的有效算法

prime-numbers、safe-prime

高效查找大型索菲·杰曼素数的行业标准是什么？在我的应用程序中，作为请求处理的一部分，我需要生成Paillier密钥。我目前的方法是生成一个伪随机(可能是由Miller-Rabin测试支持的素数q )，然后设置p = 2q + 1，并用Miller-Rabin和Baillie检查p是否也是素数。这是重复的，直到p成为素数。ran

浏览 0提问于2018-06-26得票数 3

回答已采纳

2回答

gmpy源代码

python、primes、gmp

有什么方法可以查看gympy的源代码吗？具体来说，gmpy2.is_prime。 MZ ÿÿ ¸ @ ð º ´ Í!¸LÍ!其余的都是胡言乱语。我想要写一个非常快的质数检查器，这是我到目前为止遇到的<

浏览 2提问于2013-03-04得票数 0

回答已采纳

1回答

为什么PGP仍然使用费马素数检验？如果它碰到了卡迈克尔的一个数字呢？

rsa、prime-numbers、pgp

由于费马素数检验不太可靠，大多数应用程序仅用于预测试。维基百科说PGP仍然使用它：另一个只依赖于Fermat测试的著名程序是PGP，它只用于测试自生成的大型随机值(开源对应的GNU隐私保护使用Fermat预测试，然后是Miller-Rabin测试)。

浏览 0提问于2021-02-17得票数 4

回答已采纳

1回答

C#随机BigInt发生器

c#、biginteger、dsa

我即将实现，但有一个问题：如何实现这个数字的随机生成器？Int64“只有”63位长。

浏览 4提问于2010-06-03得票数 12

回答已采纳

4回答

SICP练习1.28 - Miller-Rabin* -“至少一半的数字将显示一个1模n的非平凡平方根”*

scheme、primes、sicp、primality-test

SICP练习1.28 费马试验的一个不能被愚弄的变体叫做米勒-拉宾试验(Miller 1976；Rabin 1980)。这是从Fermat小定理的另一种形式出发，即如果n是素数，a是小于n的正整数，则把n提升到(n - 1)st幂等于1模n，用Miller-Rabin检验n的素数，用expmod过程选取一个随机数a<n，然而，当我们在expmod中执行平

浏览 2提问于2019-05-03得票数 2

回答已采纳

2回答

Python中大型‘N’的快速素数测试

python、math、primes

我正在做一个项目，要求我找出极大的数字是否是素数。虽然概率选项比蛮力快一个数量级，但是对于n的大输入(例如，已知的素数10**9999 + 33603)，它们仍然非常慢。在Python中，这样的函数如下所示 if p == 2 or p == 3: if p == 0 or，则保证以上内容返回true，但真正的结果并不意味着p是素数

浏览 6提问于2020-05-01得票数 1

回答已采纳

2回答

应该使用多少个Rabin-Miller迭代来生成密码安全素数？

cryptography、key-generation

我正在为Diffie-Hellman型密钥生成一个2048位的安全素数，这样p和(p-1)/2都是素数。我能在p和(p-1)/2上使用多少次Rabin迭代，并且仍然对加密强密钥有信心？在我所做的研究中，我听到了从6到64次的1024位普通素数的迭代，所以在这一点上我有点困惑。一旦确定了，如果你生成的是一个安全的素数，而不是一个普通的素

浏览 0提问于2011-06-13得票数 14

回答已采纳

1回答

为什么方案中的Miller-Rabin过程在代码似乎错误的情况下工作呢？

scheme、lisp、sicp

在练习1.28中有关米勒-拉宾试验.我有这样的代码，我知道这是错误的，因为它没有遵循练习的指示。 (= (remainder x 2) 0)) (try-it(remainder (* base (expmod base (- exp 1) m)) m)))) (cond ((= times 0)

浏览 1提问于2014-04-17得票数 2

回答已采纳

1回答

寻找素数的概率(使用miller-rabin检验)

python、cryptography、primes

我已经实现了Miller-Rabin素数测试，每个功能似乎都独立地正常工作。然而，当我试图通过生成70位的随机数来寻找一个素数时，我的程序在找到一个通过Miller-Rabin测试的数字之前，平均生成了100000多个数字(10步)。随机数发生器是否有可能以极低的概率抛出素数？我想不是..。任何帮助都是非常受欢迎的。import random def miller</e

浏览 2提问于2016-05-03得票数 2

回答已采纳

1回答

python中的米勒-拉宾素数测试:为什么我总是得到decimal.Overflow：[<class‘class’十进制。

python、primality-test

我试图在python中做。我在维基百科上基于编写了如下代码：from numpy import * continue return True 但是，当我运行代码并输入像5336101这样的素数时我得到了以

浏览 5提问于2020-03-16得票数 0

回答已采纳

2回答

Fibonacci序列:寻找复合材料问题

python、fibonacci

我正在寻找一对GCD (最大公分母)为1的数字，这是序列X0，X1，……的第一个N项。XN都是合成的。对于我的代码，由于某种原因，当我== 15、j == 878和k == 78时，它会被卡住。当在列表中的最后两个项上运行is_prime()时，它会陷入困境。

浏览 5提问于2021-06-15得票数 1

回答已采纳

1回答

RSA的随机数是如何产生的？

rsa、random-number-generator

RSA公钥加密需要两个非常大的素数作为加密过程的一部分，作为秘密。它们通常是由某种加密安全的随机数生成器生成的。然而，随机数生成器产生随机比特；它们不专门生成素数；证明一个数字是素数需要尝试对其进行因子化--这正是RSA很难实现的问题。在RSA中，质数是如何找到的？

浏览 0提问于2014-12-27得票数 12

2回答

输入整数X并判断它是否为素数

python、input、output

输入整数X并判断它是否为素数。如果它是素数，输出'Y‘如果不是，输出'N’和最小素数因子。但我只想打印一次“Y”或“N”。我也不知道如何在我的程序结果中显示最小的素因子。谢谢你们帮助我

浏览 4提问于2022-10-20得票数 -1

点击加载更多