计算数字中最大素因子的最佳方法是什么？

我认为效率最高的是以下内容:

1. 找到干净分配的最低素数
2. 检查除法结果是否为素数
3. 如果没有,找到下一个最低点
4. 转到2.

我基于这个假设,因为它更容易计算小的素因子.这是对的吗？我应该研究哪些其他方法？

编辑:我现在已经意识到,如果有超过2个素因子,我的方法是徒劳的,因为当结果是两个其他素数的乘积时,步骤2失败,因此需要递归算法.

再次编辑:现在我已经意识到这仍然有效,因为最后找到的素数必须是最高的,因此对步骤2的非素数结果的任何进一步测试都会导致较小的素数.

我正在寻找一种实现或清晰的算法,用于在python,伪代码或其他任何可读的内容中获得N的素数因子分解.有一些要求/事实:

• N介于1到20位之间
• 没有预先计算的查找表,但是memoization很好.
• 不需要在数学上证明(例如,如果需要,可以依赖于Goldbach猜想)
• 不需要精确,如果需要,可以是概率/确定性的

我需要一个快速素数因子分解算法,不仅适用于自身,还适用于许多其他算法,如计算Euler phi(n).

我已经尝试了维基百科的其他算法,但要么我无法理解它们(ECM),要么我无法从算法(Pollard-Brent)创建工作实现.

我对Pollard-Brent算法非常感兴趣,因此对它的任何更多信息/实现都会非常好.

谢谢!

编辑

搞砸了一下后,我创建了一个非常快速的素数/分解模块.它结合了优化的试验分割算法,Pollard-Brent算法,米勒 - 拉宾素性测试和我在互联网上发现的最快的素数.gcd是常规Euclid的GCD实现(二进制Euclid的GCD 比常规GCD 慢得多).

赏金

哦,快乐,可以获得赏金!但我怎么能赢呢？

• 在我的模块中找到最优化或错误.
• 提供替代/更好的算法/实现.

最完整/最具建设性的答案得到了赏金.

最后模块本身:

import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N …

我错误地认为RSA加密的安全性通常受已知素数的限制吗？

要破解(或创建)私钥,必须组合正确的素数对.

是否无法发布RSA使用范围内所有素数的列表？或者这个列表足够大,以使这种暴力攻击不太可能？难道不会有"常用"素数吗？

制作一个简单的筛子很容易:

for (int i=2; i<=N; i++){
    if (sieve[i]==0){
        cout << i << " is prime" << endl;
        for (int j = i; j<=N; j+=i){
            sieve[j]=1;
        }
    }
    cout << i << " has " << sieve[i] << " distinct prime factors\n";
}

但是当N非常大并且我无法在内存中保存那种数组时呢？我已经查找了分段筛选方法,它们似乎涉及到找到素数直到sqrt(N),但我不明白它是如何工作的.如果N非常大(例如10 ^ 18)怎么办？

在我已经阅读过关于公钥加密的解释中,据说通过将2个极大的素数相乘来得出一些大数.由于对大质量产品进行分解几乎不可能耗费时间,因此您具有安全性.

这似乎是一个可以通过彩虹表轻易解决的问题.如果您知道所使用的素数的大致大小并且知道其中有2个,您可以快速构建彩虹表.它是一个强大的表,但它可以完成,任务可以跨硬件并行化.

为什么彩虹表不是基于乘以大素数而击败公钥加密的有效方法？

免责声明:显然,数以万计的疯狂智能安全意识的人不会错过几十年我在下午想到的事情.我认为我误解了这一点,因为我正在阅读简化的外行解释(例如:如果使用超过2个数字),但我还不知道我的知识差距在哪里.

编辑:我知道"彩虹表"涉及在查找表中使用预先计算的哈希,但上面的声音听起来像彩虹表攻击所以我在这里使用这个术语.

编辑2:如答案中所述,没有办法存储所有素数,更不用说它们的所有产品.

• 这个网站说有这么多512位素数:((2 ^ 511)*1)/(512 log(2))= 4.35×10 ¹⁵¹
• 太阳的质量为2×10 ³⁰ kg或2×10 ³³ g
• 这是每克太阳2.17×10 ¹²⁴素数.
• 数量.512位数可以适合千字节:1 kb = 1024字节= 8192位/ 512 = 16
• 这可以适合太字节:16*1024*1024*1024 = 1.72×10 ¹⁰
• Petabyte:16*1024*1024*1024*1024 = 1.72×10 ¹³
  
• Exabyte:16*1024*1024*1024*1024*1024 = 1.72×10 ¹⁶

即使1 exabyte重1克,我们也无法达到2.17×10 ¹²⁴所需的能够将所有这些数字装入带有太阳质量的硬盘中

我已经有了素数因子化(对于整数),但现在我想用高斯整数来实现它,但我该怎么做呢？谢谢!

我正在尝试实现一个函数primeFac(),该函数将正整数作为输入,n并返回包含素数因子分解中所有数字的列表n.

我已经做到这一点,但我认为在这里使用递归会更好,不知道如何在这里创建递归代码,什么是基本情况？首先.

我的代码:

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?

加密算法的安全性如何依赖于分解大数？

例如,我在一些数学编程论坛上读过,通过使用Quadratic Sieve或General Number Field Sieve,可以在商用硬件上相对容易地计算256位数.

这如何转化为能够打破RSA,AES等算法的安全性？是否可以将数字的长度系数足够？

有没有人知道加密算法和加密算法能否对它有所了解？

作为我自己的练习,我正在实施Miller-Rabin测试.(通过SICP工作).我理解费马的小定理并且能够成功地实现它.我在米勒 - 拉宾测试中被绊倒的部分是这个"1 mod n"业务.是不是1 mod n(n是一些随机整数)总是1？所以我很困惑"1模数n的非平方根"可能是什么,因为在我看来"1 mod n"在处理整数值时总是1.我错过了什么？

需要考虑的是以下函数,该函数可用于(相对快速地)将64位无符号整数分解为其素因子.注意,因子分解不是概率性的(即,它是精确的).在现代硬件上,该算法已经足够快,可以在几秒钟内找到一个数字是素数或几乎没有很大的因子.

问题:可以对所提出的算法进行任何改进,同时保持它是单线程的,这样它可以更快地考虑(任意)非常大的无符号64位整数,最好不使用概率方法(例如,Miller-Rabin)确定素性？

// system specific typedef for ulong should go here (or use boost::uint64_t)
typedef unsigned __int64 ulong;
typedef std::vector<ulong> ULongVector;

// Caller needs to pass in an empty factors vector
void GetFactors(ULongVector &factors, ulong num)
{
  // Num has to be at least 2 to contain "prime" factors
  if (num<2)
    return;

  ulong workingNum=num;
  ulong nextOffset=2; // Will be used to skip multiples of 3, later

  // Factor out factors of 2
  while (workingNum%2==0)
  {
    factors.push_back(2);
    workingNum/=2;
  }

  // Factor …