如何确定是否一个令人难以置信的大量是素数？ [英] How to determine if an incredibly large number is prime?

问题描述

我想弄清楚的数字是这种形式（举例）：

The numbers I'm trying to figure out are in this form (some examples):

2 ^ 7 - 1 ， 2 ^ 31 - 1 ， 2 ^ 127 - 1 ，等等

这是不是一个家庭作业问题，我只是素数研究和大量的信息是怎么回事了一下我的头（傅立叶变换）。本来我只是用一个函数是这样的：

This is not a homework question I was just researching primes and a lot of the information is going a bit over my head (Fourier transformations). Originally I was just using a function like this:

public static bool IsPrime(int candidate)
{
    if ((candidate & 1) == 0)
    {
        return candidate == 2;
    }

    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
            return false;
        }
    }

    return candidate != 1;
}

但是，停止工作，一旦数字了过大。我也看了到筛但显然这仅适用于小得多大小的数字。

But that stopped working once the numbers got too big. I also looked in to the Sieve of Eratosthenes but apparently that only works for numbers of much smaller size.

要澄清，我并不想编写一个程序来的查找的质数，而是确定一个给定的数字是素数。我一直在寻找到的BigInteger 结构中。 NET框架和它看起来很有希望，如果我可以只写一个高效的足够的算法（我会解决的东西，在天完成）。

To clarify, I'm not looking to write a program to find prime numbers, but rather, to determine if a given number is prime. I was looking in to the BigInteger structure in the .NET Framework and it looks promising if I could just write an efficient enough algorithm (I'd settle for something that finished in days).

我不知道，如果一个数学证明是在这种情况下更好，但我并没有在这方面的很多知识，而不是编程，但是如果有一个证明，专门从事这类数字，那肯定会值得仔细研究的。

I'm not sure if a mathematical proof would be better in this circumstance but I do not have much knowledge in that area as opposed to programming but if there was a proof that specialized in these kinds of numbers, that'd definitely be worth looking in to.

感谢。

推荐答案

保号是一个大问题。事实上，这很难是现代密码学的基础。

Factoring numbers is a big deal. The fact that it's difficult is the basis of modern cryptography.

根据你有多大的号码是......你可以得到所有质数的列表取决于你正在寻找数的平方根。这将是显著低于只是每次都涨了2。这个问题将是找到一个列表较大。如果你有一个数字是10的100次方，那么你需要的10 ^ 50，少的所有素数，这仍然是一个庞大的数字。

Depending on how large your number is... You could get a list of all prime numbers up to the square root of the number you're looking for. This will be significantly less than just going up by 2 every time. The problem would be finding a list that large. If you have a number that's 10^100, then you'd need all primes of 10^50 and less, which is still a huge amount of numbers.

这篇关于如何确定是否一个令人难以置信的大量是素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！