brute force BigInteger Factorization

Question

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!

brute force factorization is the same algorithm whether it's applied on BigIntegers, or regular integers. You can find its pseudocode e.g. [here](http://stackoverflow.com/a/15292911/849891) or a working Java code [here](http://stackoverflow.com/a/12046123/849891). — Will Ness, Apr 17 '13 at 07:25

score 4 · Answer 1 · answered Apr 15 '13 at 01:59

4

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.

answered Apr 15 '13 at 01:59

user448810

17,381
4
34
59

Thanks for the tip but I really just wanted to know if the way I was saying was possible, i cant really copy all of that code from your essays and use it. though thanks for the link – erp Apr 15 '13 at 02:18

Josh Horowitz · Answer 2 · 2013-04-16T08:23:23.930

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)

brute force BigInteger Factorization

2 Answers2