Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I tried to factor the numbers $1013^{13}+331\#$ and $98!+76!+54!+32!+1$ with GMP-ECM because the quadratic sieve takes very much time. Perhaps someone factors one of those numbers for me. The second number has a prime factor of 25 digits, namely $1005693665747024080598971$. For those who are not familiar with the number theory notations: $!$ is the factorial $n!=1\cdot 2\cdot 3\cdot\ldots\cdot n$ and $n\#$ is the product of primes up to $n$: $n\#=2\cdot 3\cdot 5\cdot 7\cdot\ldots\cdot n$, if $n$ is a prime. And please do not ask why I am interested in these factorization. It is just curiousity because in the net it is stated that such numbers are already quite easy to factor. Useful programs are GMP-ECM or msieve downloadable from the net.

share|improve this question
    
The first, as 1013^13 + 331, gives 336 * prime number. Prehaps the # stands for something different? –  wendy.krieger May 27 '13 at 7:04
    
Wendy : Please read the whole text, I explained the '#'. –  Peter May 27 '13 at 7:07
    
Peter, this is the third account you created: math.stackexchange.com/users/79589/peter , math.stackexchange.com/users/79596/peter and this one. Please ask a moderator to merge them! I flagged your account to draw a moderator's attention... –  draks ... May 27 '13 at 7:22
1  
@draks... Mods can't do that anymore. The user has to contact SE directly math.stackexchange.com/help/user-merge –  Double AA May 27 '13 at 7:24
1  
I assume (the other) Peter might be referring to the fact that 512-bit moduli are considered to be weak for crypto schemes like RSA due to being factorable withing reasonable time-frame. –  Peter Košinár May 27 '13 at 7:36

1 Answer 1

The first one took about 60 hours of NFS-ing on a moderately slow machine with unoptimized factoring settings while the machine was being used for other purposes too:

1013^13 + 331# = 13660997293197200778560512676198053659658942317253 *
469117945090530664165653254310752426123381482366114189309329070591871468575459348391

The other one took about 64 hours; the smallest factor being discovered by ECM pretty quickly and the rest of the time spent on NFS-ing (again, unoptimized, running in background, ...):

98!+76!+54!+32!+1 = 1005693665747024080598971 * 
79146647927616255967923163095656379252005739066059813 *
118432315205629597504117998137752645490949757279339848413269947393226465090487

Altogether, this supports the statement that numbers of this size are quite easy to factor with current hardware. The time could be cut down to about one day on a dedicated, reasonably modern workstation and further cuts would be possible with better tuning of the factoring settings.

share|improve this answer
    
+1 respect..... –  draks ... Jun 4 '13 at 19:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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