20200108, 18:05  #1 
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. 
20200108, 19:03  #2 
"Curtis"
Feb 2005
Riverside, CA
3^{2}×7×71 Posts 
Regular GMPECM 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? 
20200108, 20:12  #3  
Nov 2003
2^{6}·113 Posts 
Quote:
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 SchonhageStrassen 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 20200108 at 20:14 

20200108, 20:25  #4 
Aug 2006
2·2,969 Posts 

20200109, 15:47  #5 
Jan 2020
5 Posts 
The number has been randomly generated.
I tested trial division using YAFUGUI, 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. 
20200109, 16:28  #6 
"Ben"
Feb 2007
3341_{10} Posts 
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.

20200109, 16:40  #7 
Aug 2006
2×2,969 Posts 
So why factor it?
You'll want to use special algorithms for numbers of that size. It's worth testing singleword trial division against an asymptotically fast gcd of a tree of small potential divisors. Cachefriendliness is key here. 
20200109, 17:23  #8 
Feb 2005
Colorado
222_{16} Posts 
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.

20200109, 22:23  #9 
Nov 2003
7232_{10} Posts 

20200110, 01:02  #10 
Feb 2017
Nowhere
2^{4}·3·79 Posts 
If you're content with really small factors, you can use PariGP.
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. 
20200111, 20:13  #11 
Jan 2020
5_{16} Posts 
I want to factorize randomly generated number for fun  how far can I get (in reasonable amount of time).
I have problems with PARIGP. 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? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PArtial factorization of 2^8523486591  ET_  PrimeNet  15  20180610 18:40 
Number Of Digits; I Hate To Ask  storm5510  Other Mathematical Topics  14  20100831 01:16 
Number of digits display  grobie  15k Search  13  20050929 21:57 
how do you find number of digits of a 2^n number?  Unregistered  Math  11  20041130 22:53 
5dpf, 5 digits from the end partial factors  dsouza123  Factoring  6  20040426 16:57 