CODEWITHSUNDEEP
javaprimesbigintegerbrute-forcefactorization
erp
erp

Reputation: 3034

brute force BigInteger Factorization

as you can tell by the title, I am working on trying to brute force the factorization of large integers whose factors are 2 primes. I was wondering if there was a way to use a for loop inside a for loop for this. I know this is a TERRIBLE way to do it but i would like to do it anyways. ( I was going to use fermats factorization theorem but u cant sqrt BigIntegers without some extra method / library and I cannot do that) So just try and see if you can help me with what I am doing. Someting along the lines of this:

BigInteger n = new BigInteger("270653957405596110781");  // this is what i need the factors of
BigInteger TWO = new BigInteger("2");
for( BigInteger i = new BigInteger("1"); i < n.divide(TWO); i.nextProbablePrime() ){
    for( BigInteger k = new BigInteger("1"); k < n.divide(TWO); k.nextPossiblePrime){
        if(i.Multiply(k) = n){
            //i and k are the factors, and return them
        }
     }
 }

obviously thats atrocious and i know that you cannot just increase to the next prime by saying i.nextPossiblePrime(), you would need it to say i = i.nextpossible prime, I was just showing you of kind of how i wanted it to work; but thats why I am asking because idk if something like this is even possible!

Please let me know if this route is possible and how i could fix this bad code to function like i am visualizing it!

Thanks!

Upvotes: 0

Views: 1860

Answers (2)

Josh Horowitz
Josh Horowitz

Reputation: 665

I'm still pretty new to computer science (8 months), and this is my first time answering a question, so sorry if I'm not much of a help. Please correct me if I'm wrong (seriously, I'm trying to learn) but I think what you're looking for is Quadratic Sieve. http://en.wikipedia.org/wiki/Quadratic_sieve You seem to be more advanced than me but I was able to implement it with a days work. It's pretty effective at factoring large numbers.

I don't know anything about Fermat's factorization method, but couldn't you just inherit BigInteger into a new class and make your own implementation of it, complete with a square root function? I don't know what kind of accuracy you need but you could always base it off of BigDecimal instead.

Hope this is helpful

EDIT: I'm guessing you didn't test your code. You can't use operators like < with BigInteger. You need to use BigInteger.compareTo(BigInteger)

Upvotes: 1

user448810
user448810

Reputation: 17866

I refuse to "just help you do what you are doing." It won't work.

I modestly recommend the essay Programming with Prime Numbers at my blog. The pollard-rho algorithm discussed there will factor your number without difficulty. A java implementation using BigInteger is included.

By the way, 270653957405596110781 = 7588940707 * 35664260383.

Upvotes: 4

Related Questions