brute force BigInteger Factorization

Question

제목으로 알 수 있듯이 나는 인자가 2 소수 인 큰 정수의 인수 분해를 무력화하려고 노력하고 있습니다. for 루프를 for 루프 안에 사용하는 방법이 있는지 궁금합니다. 나는 이것이 이것을하기위한 끔찍한 방법이라는 것을 알고 있지만 어쨌든 그것을하고 싶습니다. (나는 fermats factorization theorem을 사용할 것이지만 sqrt BigIntegers를 약간의 추가 방법/라이브러리없이 사용할 수는 없다. 그래서 나는 그것을 할 수 없다.) 그래서 내가하고있는 것을 도와 줄 수 있는지 알아 보자. 이 라인을 따라가 someting :

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 
     } 
    } 
} 

분명히 잔인한 이잖아 그리고 난 그냥 i.nextPossiblePrime는(), 당신이 그것을 내가 말을해야 말을하여 다음 주요 증가 할 수 없다는 것을 알고 = i.nextpossible 프라임, 나는 당신에게 그것이 내가 일하기를 원했던 방식의 종류를 보여주고 있었다. 하지만 그 이유는 idk 때문에 이런 일이 가능할지 물어 보는 이유입니다!

이 경로가 가능하고 내가 시각화하는 것처럼이 나쁜 코드를 어떻게 해결할 수 있는지 알려 주시기 바랍니다!

감사합니다.

Answer 1

나는 "네가하고있는 일을 돕는 것"을 거부한다. 그것은 작동하지 않습니다.

나는 내 블로그에서 에세이 Programming with Prime Numbers을 알맞게 추천한다. 여기서 논의 된 폴라드 - ρ 알고리즘은 어려움없이 사용자의 수를 고려합니다. BigInteger를 사용한 Java 구현이 포함되어 있습니다. 그런데

, 270653957405596110,781 = 7,588,940,707 * 35664260383.

Answer 2

난 아직도 컴퓨터 과학 (8 개월) 꽤 새로운 해요, 나는 많은 아니에요 경우이, 미안 내 처음으로 질문에 답이다 도움. 내가 틀렸다고 정정 해주세요. (진지하게, 나는 배우려고 노력하고 있습니다.) 그러나 당신이 찾고있는 것은 Quadratic Sieve입니다. http://en.wikipedia.org/wiki/Quadratic_sieve 당신은 나보다 진보 된 것처럼 보이지만 나는 일간의 일로 그것을 구현할 수있었습니다. 많은 수를 고려할 때 꽤 효과적입니다.

나는 Fermat의 인수 분해 방법에 대해 아무것도 모르지만, 단지 BigInteger를 새로운 클래스로 상속받지 않고 제곱근 함수를 사용하여 직접 구현할 수는 없습니까? 어떤 종류의 정확성이 필요한지 모르지만 대신 BigDecimal을 기본으로 설정할 수 있습니다.

희망이 도움이

편집이다 : 나는 당신이 당신의 코드를 테스트하지 않았다 같은데요. BigInteger에는 <과 같은 연산자를 사용할 수 없습니다. BigInteger.compareTo (BigInteger)를 사용할 필요가 있습니다.