Java中大型BigInteger的更快素数分解 - java

所以我现在正在处理Java代码。我已经知道它可以很好地工作了,但是赋值的重点是使它分解大数(超过30位数字)。它可以这样做,但是可能要花15分钟以上才能完成,这是不好的。我的教授向我保证,我正在使用的算法可以处理高达2 ^ 70的数字,并且应该在大约五分钟内完成。我一直在试图找到一种方法(将2而不是1递增,等等),但是我似乎并没有真正想出如何在不跳过某些因素的情况下使其更快地移动的方法。有任何想法吗?我还认为椭圆曲线方法会更好,但是他告诉我现在不要处理。

这是我的代码(ps,sqrt是我自己的函数,但我确定它可以正常工作):

public String factorizer(BigInteger monster){
    System.out.println("monster =" + monster); 
    String factors = "";  
    BigInteger top = maths.monsterSqrt(monster);   
    if(monster.mod(two).equals(0));
        BigInteger jump = two;
    for(BigInteger bi = two; bi.compareTo(top) <= 0; bi = bi.add(jump)){
        while(monster.mod(bi).equals(zero)){
            factors +=  "+" + bi + ""; 
            monster = monster.divide(bi); 
            jump = one; 
        }
    }
    if(monster.compareTo(BigInteger.ONE) == 1){
        factors  += "+" + monster; 
    } 
    return factors; 
} 

参考方案

这是我通过试验除法进行的整数分解的版本:

public static LinkedList tdFactors(BigInteger n)
{
    BigInteger two = BigInteger.valueOf(2);
    LinkedList fs = new LinkedList();

    if (n.compareTo(two) < 0)
    {
        throw new IllegalArgumentException("must be greater than one");
    }

    while (n.mod(two).equals(BigInteger.ZERO))
    {
        fs.add(two);
        n = n.divide(two);
    }

    if (n.compareTo(BigInteger.ONE) > 0)
    {
        BigInteger f = BigInteger.valueOf(3);
        while (f.multiply(f).compareTo(n) <= 0)
        {
            if (n.mod(f).equals(BigInteger.ZERO))
            {
                fs.add(f);
                n = n.divide(f);
            }
            else
            {
                f = f.add(two);
            }
        }
        fs.add(n);
    }

    return fs;
}

我的博客上的essay中解释了此代码,其中还解释了Pollard的rho算法,该算法可能更适合分解大整数。

顺便说一下,最近30位数并不是一个特别大的分解问题。超过几秒钟的时间太长。

Java:BigInteger,如何通过OutputStream编写它 - java

我想将BigInteger写入文件。做这个的最好方式是什么。当然,我想从输入流中读取(使用程序,而不是人工)。我必须使用ObjectOutputStream还是有更好的方法?目的是使用尽可能少的字节。谢谢马丁 参考方案 Java序列化(ObjectOutputStream / ObjectInputStream)是将对象序列化为八位字节序列的一种通用方法。但…

JAVA:字节码和二进制有什么区别? - java

java字节代码(已编译的语言,也称为目标代码)与机器代码(当前计算机的本机代码)之间有什么区别?我读过一些书,他们将字节码称为二进制指令,但我不知道为什么。 参考方案 字节码是独立于平台的,在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的,如果在Windows x86中编译,则它将仅在Win…

java:继承 - java

有哪些替代继承的方法? java大神给出的解决方案 有效的Java:偏重于继承而不是继承。 (这实际上也来自“四人帮”)。他提出的理由是,如果扩展类未明确设计为继承,则继承会引起很多不正常的副作用。例如,对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是,持有对本来应该扩展的类的引用,然后委托给它。这是与Eric…

Java-如何将此字符串转换为日期? - java

我从服务器收到此消息,我不明白T和Z的含义,2012-08-24T09:59:59Z将此字符串转换为Date对象的正确SimpleDateFormat模式是什么? java大神给出的解决方案 这是ISO 8601标准。您可以使用SimpleDateFormat simpleFormat = new SimpleDateFormat("yyyy-MM…

Java:从类中查找项目名称 - java

仅通过类的实例,如何使用Java反射或类似方法查找项目名称?如果不是,项目名称(我真正想要的是)可以找到程序包名称吗? 参考方案 项目只是IDE使用的简单组织工具,因此项目名称不是类或JVM中包含的信息。要获取软件包,请使用Class#getPackage()。然后,可以调用Package#getName()将包作为您在代码的包声明中看到的String来获取…