2
$\begingroup$

I have this large number:

1728098743723095094470726818328193358068864405124007684733613106475812450278961107574624070107782941006379

which is the multiplication of two unknown large prime numbers. I try to factorize it with the "Yafu" tool, but i get an error of "time exceeded.

How can I factorize it? How many time will it take?

| improve this question | |
$\endgroup$
3
$\begingroup$

FWIW magma took 61+ hours ("Time: 221003.960") running on germain.harvard.edu to obtain the factorization

$40234782465449057005624875587624394161353466559301303 \cdot 42950368756363249557996836702278286314269822003688493\;.$

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ What kind of machine is that? $\endgroup$ – CodesInChaos Dec 4 '15 at 22:03
  • $\begingroup$ Dear Elkies,always your good answer encourage me for searching a different way for solving problems. Thanks. $\endgroup$ – Meysam Ghahramani Jan 8 '16 at 20:36
3
$\begingroup$

Two years experience with MAGMA show me that it is one of the best program for pure math. But in several cases such as the RSA numbers factoring, there are programs that are more stronger than it. I think one of these program is CrypTool. With Intel core-i7 3632QM 2.2 GHz CPU (4 physical cores) and 8GB RAM on my laptop I factored this number with this program in 4 hours and 16 minutes using the "Quadratic Sieve" method. The prime factors are as follows:

$40234782465449057005624875587624394161353466559301303$

$42950368756363249557996836702278286314269822003688493$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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