mersenneforum.org > YAFU Partial factorization of 100 000 digits number
 Register FAQ Search Today's Posts Mark Forums Read

 2020-01-08, 18:05 #1 PrimeInteger   Jan 2020 5 Posts Partial factorization of 100 000 digits number I´m new here and I want to partial factorize some 100 000 digits number with YAFU - ECM. Unfortunately, it crashed, It´s possible to make it work for that big numbers? Remember that I want only PARTIAL factorization, not complete. Thanks.
 2020-01-08, 19:03 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 32×7×71 Posts Regular GMP-ECM is going to be very, very slow with a 100k digit number. Prime95 has a different ECM implementation that is quite a bit faster for large inputs, but only works for inputs of a particular form. What form does your number have? How far have you gone with trial division?
2020-01-08, 20:12   #3
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by PrimeInteger I´m new here and I want to partial factorize some 100 000 digits number with YAFU - ECM. Unfortunately, it crashed, It´s possible to make it work for that big numbers? Remember that I want only PARTIAL factorization, not complete. Thanks.
What are you trying to accomplish? Finding small factors of Mersenne numbers has
a purpose. Are these numbers of some special form?

In general, the only method for finding small factors of 100K digit integers will be
trial division. Modular multiplication on general 100K digit numbers is just too slow
to make ECM viable. A Schonhage-Strassen implementation of ECM might
be workable for small B1/B2, but I don't know of any such implementation.

Note also that for general integers one not only has to do the multiplication, but the
modular reduction as well. For Mersenne numbers, we get the latter "for free" when
we use weighted irrational base transforms.

The same problem applies if you try to use (say) Pollard Rho.

May I ask the purpose of these partial factorizations?

Last fiddled with by R.D. Silverman on 2020-01-08 at 20:14

2020-01-08, 20:25   #4
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by R.D. Silverman A Schonhage-Strassen implementation of ECM might be workable for small B1/B2, but I don't know of any such implementation.
Wow, that would be a neat project!

 2020-01-09, 15:47 #5 PrimeInteger   Jan 2020 5 Posts The number has been randomly generated. I tested trial division using YAFU-GUI, but it does not accepts numbers of that size. How can I alter the trial division bound? I want to remove small factors from very big number.
2020-01-09, 16:28   #6
bsquared

"Ben"
Feb 2007

334110 Posts

Quote:
 Originally Posted by PrimeInteger The number has been randomly generated. I tested trial division using YAFU-GUI, but it does not accepts numbers of that size. How can I alter the trial division bound? I want to remove small factors from very big number.
The only GUI I'm aware of for yafu was put together by EdH. But even if the first bottleneck is GUI related I'm sure that any number of problems will come up in yafu itself. It was designed for complete factorizations and therefore has not been tested with numbers like this in mind. Sorry, you will probably have to look elsewhere to accomplish this goal.

2020-01-09, 16:40   #7
CRGreathouse

Aug 2006

2×2,969 Posts

Quote:
 Originally Posted by PrimeInteger The number has been randomly generated.
So why factor it?

Quote:
 Originally Posted by PrimeInteger I tested trial division using YAFU-GUI, but it does not accepts numbers of that size. How can I alter the trial division bound? I want to remove small factors from very big number.
You'll want to use special algorithms for numbers of that size. It's worth testing single-word trial division against an asymptotically fast gcd of a tree of small potential divisors. Cache-friendliness is key here.

2020-01-09, 17:23   #8
PhilF

Feb 2005

22216 Posts

Quote:
 Originally Posted by CRGreathouse You'll want to use special algorithms for numbers of that size. It's worth testing single-word trial division against an asymptotically fast gcd of a tree of small potential divisors. Cache-friendliness is key here.
Not only that, but if the smallest factor is beyond a pretty small number of digits, trial factoring could take beyond the sun burning out before finding the first factor.

2020-01-09, 22:23   #9
R.D. Silverman

Nov 2003

723210 Posts

Quote:
 Originally Posted by CRGreathouse So why factor it?
A valid question.

 2020-01-10, 01:02 #10 Dr Sardonicus     Feb 2017 Nowhere 24·3·79 Posts If you're content with really small factors, you can use Pari-GP. I "randomly generated" a 100,000 digit number n, digit by digit, using random(10). Then I tried M = factor(n, 2^26); (2^26 was my primelimit). It didn't take very long. The ; at the end of the command is there so Pari doesn't barf the matrix M all over the screen. Then, I checked how many factors had been found using print(#M[,1]) and discovered that M had 2 rows. The first row held a prime factor < 2^26. The command print(M[1,1]) then told me the prime factor; using M[1,] instead would have given the exponent as well. Of course, M[2,1] held the cofactor.
 2020-01-11, 20:13 #11 PrimeInteger   Jan 2020 516 Posts I want to factorize randomly generated number for fun - how far can I get (in reasonable amount of time). I have problems with PARI-GP. I increased parisizemax to 500MB. But factorization with factorint(num, 2^2) didn´t completed after 2 minutes. num contains 1000 digits. btw, how can I set num to be file my_number.txt?

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ PrimeNet 15 2018-06-10 18:40 storm5510 Other Mathematical Topics 14 2010-08-31 01:16 grobie 15k Search 13 2005-09-29 21:57 Unregistered Math 11 2004-11-30 22:53 dsouza123 Factoring 6 2004-04-26 16:57

All times are UTC. The time now is 23:19.

Wed Nov 25 23:19:55 UTC 2020 up 76 days, 20:30, 3 users, load averages: 1.79, 1.42, 1.35