问题标签 [primality-test]

我有一个作业问题，要求我描述一个接受L = {a^n: n is prime}. 我不知道该怎么做。我知道吗？我是否使用as 作为一元数字并计算它们？我可以忽略字符串，只测试 n 的主要部分吗？或者是已知的素数，因此只有那些单元格位置是接受状态，我可以像正常一样读取数据？

我该怎么办？

我想为一个大学项目实现一个 RSA 密码系统算法，我正在尝试决定使用哪种编程语言。我对C非常熟悉，所以这将是一个方便的选择。然而，该算法必须处理非常大的数字（它将包括一个 Primality 子例程），而且我听说使用 Python 会产生更好的实现。那正确吗？

先感谢您。

所以我对 Haskell 完全陌生，希望它不会显示太多。无论如何，我试图创建一个函数来确定一个数字是否是素数。基本思想是这样的：给定一个数，看看它是否能被任何比它小的数整除。如果是，则返回 false。如果不是，则为素数，返回 true。到目前为止的代码（已知有效）是这样的：

产生：

我想做的是稍微优化一下，因为我只需要检查小于或等于 sqrt(x) 的值。问题是，当我尝试实现它时，事情变得疯狂：

除了它看起来很糟糕（我说我是新手）之外，它并没有给出正确的结果：

我试图弄清楚发生了什么变化，因为：

似乎给了我正确的号码。我知道这是一个小问题，但我很困惑......

我试图根据FIPS 186-3 C.3.1 中的描述实施 Miller-Rabin 素数测试。无论我做什么，我都无法让它发挥作用。说明非常具体，我认为我没有遗漏任何内容，但我得到true了非主要价值。

我做错什么了？

这：

给我：

我刚进入haskell。我正在尝试编写一个质数生成器，它会根据我给它的位数返回一个质数。我是否使用某种埃拉托色尼筛？这会是最快的方法吗？目前，我已经有一个 Miller-Rabin 的素数检查器。有正确的方法和错误的方法吗？此外，我希望能够非常快速地生成大量数据。

前任。生成一个 32 位的素数

代码到此为止。

将库函数与 RSA 一起使用：

谢谢大家，我真的很感谢你的帮助。

我正在寻找一种算法，它可以证明任何大数的素数。大数是指其中至少有 100,000,000 个十进制数字的数字，不能用梅森素数等简单的公式表示。

以下是我的要求：

1-它必须完全正确

2-它必须可以在基本的家用计算机上运行

3- 它必须在几周或几个月内完成它的课程。

我的内存限制是 8 GB 的内存（我可以设置我的选项来决定有多少缓存可用），在具有 1 TB 硬盘驱动器的专用机器上。在几个月的时间里，我将一次次考虑排名第一。

Edit1：我很清楚这是一个很难竞争的竞技场，如果使用当前的方法几乎不可能的话。我没有使用当前的方法，我需要一种方法来证明我的方法对于非常大的数字是正确的。

Edit2：我需要一种非概率方法的部分原因是因为这将是对 EFF 奖项的尝试，并且在那里成功获得第二个 EFF 奖项。如果我的方法是正确的（这是一个按喇叭的 IF），我应该可以用我的笔记本电脑完成所有这些工作。

我知道它已经讨论过很多次了；我读过它，但不知怎的，我无法得到它。我想编写一个程序来确定输入的数字是否为素数。

我在 Internet 某处找到的实现之一：

这里有几个问题：

• 在上面，什么是i，为什么它的起始值为2？
• 在这个程序中做什么i = i + 1？
• 解释器如何知道何时打印'is a prime number.'，即使它不在正文循环中？

我想问一下这是否是检查数字是否为素数的正确方法？因为我读到 0 和 1 不是质数。

我正在尝试为我作为练习编写的 RSA 实现实现素数测试。我主要使用 Rabin-Miller，但我确实有一个埃拉托色尼筛法，制定了一个低于 1000 个素数的列表，用于快速测试以确定候选人是否将其中一个作为素数。

相关功能是：

其中 primeList 是 Sieve 生成​​的素数列表。这在 to_test 值为 2^55 左右的情况下非常有效，但超过了这一点

语句总是计算为 0.0，即使当我将它交给拉宾米勒确定为素数的 to_test 时也是如此。我不确定这可能是什么。我不太清楚 Python 如何处理非常大的数字，但据我所知 2^55 似乎不会是任何类型的溢出边界。使用 Sieve 时，该功能明显更快，并且为 2048 位实现生成密钥需要一段时间，所以即使这是一个练习，我想看看我是否可以让 Sieve 工作。

提前致谢。

这里是...

我从关于Miller-Rabin primality test的维基百科文章中得到了这个。但我一直无法理解它......我不想理解它背后的数学，而只是在程序中实现它。在我看来，这个算法有点令人困惑。一个更好、更简单的伪代码或在 vb.net 中的实现会很有帮助。

编辑到目前为止编写的代码：