0

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!

1
  • brute force factorization is the same algorithm whether it's applied on BigIntegers, or regular integers. You can find its pseudocode e.g. here or a working Java code here.
    – Will Ness
    Apr 17, 2013 at 7:25

2 Answers 2

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.

1
  • 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, 2013 at 2:18
1

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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.