在C#中找到任何bigInteger的除数的最快方法是什么 [英] What is the fastest way to find divisor of any bigInteger in c#

问题描述

我想运行类似下面的代码，以便我能够找到约30至40长度的除数，而不必检查数百万种可能性，甚至直到其平方根.找到数字的合法非平凡因数的最快解决方案是什么，或者如何在无需遍历所有可能选项的情况下改进下面的代码以更快地运行.

I want to run something like below code so that i would be able to find a divisor for numbers of ~30-40 length without having to check millions of possibilities even up to their square root. What is the fastest possible solution to find a legitimate non trivial divisor of a number or how can i improve below code to run faster, without having to loop through all possible options.

    static int divisor(string numberToCheck)
    {
        BigInteger n = BigInteger.Parse(numberToCheck);
        BigInteger sqrt = Sqrt(n);
        if (n % 2 == 0)
            return 2;
        for (UInt64 = 3; i <= sqrt; i+=2)
        {
            if (n % i == 0)
                return i;
        }
        return -1;
    }

推荐答案

很难对大量数字进行因子化.太难了，它是许多现代密码学的基础.

Factorization of large numbers is hard. So hard that it's the basis for a lot of modern cryptography.

最好的分解算法也很复杂，最简单的选择可能是使用别人已经编写的库.快速搜索出现了 https://sourceforge.net/projects/msieve/用C语言编写，甚至可以利用GPU加快搜索速度.

The best factorization algorithms are also complicated, and the easiest option is probably to use a library that someone else has already written. A quick search turned up https://sourceforge.net/projects/msieve/ which is written in C, and can even make use of a GPU to speed up the search.

它使用常规数字字段筛选(GNFS)算法.

It uses the General number field sieve (GNFS) algorithm.

这篇关于在C#中找到任何bigInteger的除数的最快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！