primefac 1.1

PrimeFac版本1.1

这是一个用于分解整数的模块和命令行实用程序。作为一个模块，我们提供了一个素性测试、几个用于提取整数的非平凡因子的函数，以及一个生成一个数的所有素性因子（具有多重性）的生成器。作为一个命令行实用程序，该项目旨在用一个更通用的实用程序替换gnu的 factor 命令-特别是，该实用程序可以对任意大的数进行操作，并行使用多个内核，使用更好的算法，以反波兰符号处理输入，并且可以通过命令行标志进行调整。具体来说，

< Buff行情>

• gnu的 factor命令的factor不会大于2 ¹²⁷ -1。primefac处理任意大的整数。如果可用，则导入 gmpy 或 gmpy2 ，后者优先于前者。

• gnu的 factor 命令使用pollard的rho算法。虽然这样可以快速提取小因素，但大因素需要一段时间才能找到。primefac使用了椭圆曲线方法，它在提取大因子方面效率更高。

• gnu的 factor 命令是一个单线程应用程序。primefac默认使用五个线程来利用现代机器上通常可用的多个内核。这些线程中的每一个都使用不同的算法来计算数字：

  • 一个线程在pollard的rho算法上运行brent的变体。这有利于快速提取小因素。
  • 一个线程运行pollard的 p -1方法的两阶段版本。这有助于找到因子 p ，其中 p -1是小素数的乘积。
  • 一个线程运行williams' p +1方法。这有助于找到因子 p ，其中 p +1是小素数的乘积。
  • 一个线程运行椭圆曲线方法。当提取的因子很小时，这比pollard的rho算法要慢一些，但它在困难因子上有更好的性能。
  • 一个线程运行多个多项式二次筛。这是最好的算法分解"硬"数，而不是可怕的复杂的通用数域筛。但是，相对而言，当数字很小时，它的速度会慢一些，所需的时间只取决于被分解的数字的大小，而不是像pollard的rho算法和椭圆曲线方法那样，取决于被提取的因子的大小，所以我们使用前面的算法来处理这些问题。

• 我们还扩展了该实用程序，将命令行参数解释为反向波兰表示法的表达式，并在解释完成时分解求值堆栈上剩余的数字。例如，命令：

  python -m primefac 24 ! 1 - 38 ! 1 +
  

< Buff行情> 将把数字24计算在内！-1=620448401733239439359999和38！+1=52302261746660111760007224100074291200000001。