标签: factorization

我只是计算机科学的初学者.我学到了一些关于跑步的知识,但我无法确定我的理解是对的.所以请帮助我.

所以整数分解目前不是多项式时间问题,而是素数测试.假设要检查的数字是n.如果我们运行一个程序只是为了决定从1到sqrt(n)的每个数字是否可以除以n,如果答案是肯定的,则存储该数字.我觉得这个程序是多项式时间,不是吗？

我错误的一种可能方式是分解程序应该找到所有素数,而不是发现的第一个素数.也许这就是原因所在.

但是,在公钥加密中,找到大量的主要因素对于攻击密码学至关重要.由于通常大量(公钥)只是两个素数的乘积,找到一个素数就意味着找到另一个素数.这应该是多项式时间.那为什么攻击很难或不可能？

我开始研究计算复杂性,BigOh表示法等等,我的任务是做整数分解算法并确定其复杂性.我编写了算法并且它正在运行,但我在计算复杂性方面遇到了麻烦.伪代码如下:

DEF fact (INT n)
BEGIN
    INT i

    FOR (i -> 2 TO i <= n / i STEP 1)
    DO
        WHILE ((n MOD i) = 0)
        DO
            PRINT("%int X", i)
            n -> n / i
        DONE
    DONE

    IF (n > 1)
    THEN
        PRINT("%int", n)

END

我想,我试图做的是非常错误的:

f(x)= n-1 + n-1 + 1 + 1 = 2n

所以

f(n)= O(n)

我认为这是错误的,因为分解算法应该在计算上很难,它们甚至不能是多项式的.那么你有什么建议来帮助我？也许我在这个晚上太累了,我搞砸了这一切:(

先感谢您.

我们使用递归来查找因子并且正在接收StackOverflow异常.我们已经读过x64计算机上的C#编译器执行尾调用优化:

在运行优化代码而不是调试时,JIT肯定会执行tailcals.

跑步dotnet --configuration release在我们的计划中得到了这么多:

...                      
7214 is a factor of 1234567890
7606 is a factor of 1234567890
10821 is a factor of 1234567890
11409 is a factor of 1234567890                

Process is terminated due to StackOverflowException.

为什么没有发生尾调用优化？

class Program
{
    static void Main(string[] args)
    {
        const long firstCandidate = 1;
        WriteAllFactors(1234567890, firstCandidate);
    }

    private static void WriteAllFactors(long number, long candidate)
    {
        if (number % candidate == 0)
        {
            System.Console.WriteLine($"{candidate} is a factor of {number}");
        }

        candidate …

所以我只想找到给定数字的所有除数(除了数字本身).目前,我有这个:

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    toreturn.Add(1);
    int i = 0;
    int j=1;
    int z = 0;
    while (primes.ElementAt(i) < Math.Sqrt(x))
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            toreturn.Add(x / primes.ElementAt(i));
            j = 2;
            z = (int)Math.Pow(primes.ElementAt(i), 2);
            while (z < x)
            {
                if (x % z == 0)
                {
                    toreturn.Add(z);
                    toreturn.Add(x / z);
                    j++;
                    z = (int)Math.Pow(primes.ElementAt(i), j);
                }
                else
                {
                    z = x;
                }
            }
        }
        i++;
    }
    toreturn = …

在回答另一个,我偶然发现了这个问题其实我怎么能找到一个整数的所有因素,而不该符号数学工具箱.

例如:

factor(60)

收益:

 2     2     3     5

unique(factor(60))

因此会返回所有素数因子,"1"缺失.

 2     3     5

我正在寻找一个可以返回所有因子的函数(1和数字本身并不重要,但它们会很好)

预期输出x = 60:

 1     2     3     4     5     6    10    12    15    20    30    60     

我想出了那个相当庞大的解决方案,除了它可能是矢量化之外,是不是有任何优雅的解决方案？

x = 60;

P = perms(factor(x));
[n,m] = size(P);
Q = zeros(n,m);
for ii = 1:n
    for jj = 1:m
        Q(ii,jj) = prod(P(ii,1:jj));
    end
end

factors = unique(Q(:))'

我认为,这个解决方案对于某些大数字会失败,因为perms需要一个<11的向量长度.

我开发了一种算法来查找给定数字的因子.因此,它还有助于查找给定数字是否为素数.我觉得这是查找因子或素数的最快算法.

该算法在5*N(其中N是输入数字)的时间帧中查找给定数是否为素数.所以我希望我可以称之为线性时间算法.

如何验证这是否是最快的算法？有人可以帮忙解决这个问题吗？(比GNFS和其他已知的更快)

算法如下

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is …

(这源于最近完成的编程竞赛)

您将获得两个10 ^ 5整数的数组,范围为1..10 ^ 7,包括:

int N[100000] = { ... }
int D[100000] = { ... }

想象一下,有理数X是将N的所有元素相乘并除以D的所有元素的结果.

修改两个数组而不更改X的值(并且不指定任何元素超出范围),使得N的乘积和D的乘积没有公因子.

一个天真的解决方案(我认为)会起作用......

for (int i = 0; i < 100000; i++)
    for (int j = 0; j < 100000; j++)
    {
        int k = gcd(N[i], D[j]); // euclids algorithm

        N[i] /= k;
        D[j] /= k;
    }

......但这太慢了.

什么是少于10 ^ 9次操作的解决方案？

例如,考虑数字96.可以用以下方式编写:

1. 96
2. 48 * 2
3. 24 * 2 * 2
4. 12 * 2 * 2 * 2
5. 6 * 2 * 2 * 2 * 2
6. 3 * 2 * 2 * 2 * 2 * 2
7. 4 * 3 * 2 * 2 * 2
8. 8 * 3 * 2 * 2
9. 6 * 4 * 2 * 2
10. 16 * 3 * 2
11. 4 * 4 * …

任何人都可以指向一个库/代码,允许我在python(numpy)中对Cholesky分解进行低级更新吗？Matlab将此功能作为一种称为"cholupdate"的功能提供.LINPACK也有这个功能,但它(据我所知)尚未移植到LAPACK,因此不能用于scipy.

我发现scikits.sparse提供了一个基于CHOLMOD的类似函数,但我的矩阵很密集.

有没有可用于python的代码,'cholupdate'的功能与numpy兼容？

谢谢!

因此,对于我的任务,我必须编写一个程序,要求用户输入整数,然后打印出该数字的素数因子分解.这就是我所拥有的:

import java.util.Scanner;

public class PrimeFactor {
    public static void main(String[] args) {
        System.out.print("Enter a positive number: ");
        Scanner scanner = new Scanner (System.in);
        int number = scanner.nextInt();
        int count;
        for (int i = 2; i<=(number); i++) {
            count = 0;
            while (number % i == 0) {
                number /= i;
                count++;
                if (count == 0) {
                    continue;
                }
            }
            System.out.println(i+ "**" + count);
        }
    }
}

我现在的问题是,每当我有一样,数量15453运行它,我得到各个因素的列表,从1到100的指数时,我只想要质因子,和我被困在如何继续.