mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2020-01-08, 18:05   #1
PrimeInteger
 
Jan 2020

5 Posts
Default 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.
PrimeInteger is offline   Reply With Quote
Old 2020-01-08, 19:03   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

32×7×71 Posts
Default

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?
VBCurtis is online now   Reply With Quote
Old 2020-01-08, 20:12   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by PrimeInteger View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2020-01-08, 20:25   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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!
CRGreathouse is offline   Reply With Quote
Old 2020-01-09, 15:47   #5
PrimeInteger
 
Jan 2020

5 Posts
Default

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.
PrimeInteger is offline   Reply With Quote
Old 2020-01-09, 16:28   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

334110 Posts
Default

Quote:
Originally Posted by PrimeInteger View Post
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.
bsquared is offline   Reply With Quote
Old 2020-01-09, 16:40   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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

Quote:
Originally Posted by PrimeInteger View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-01-09, 17:23   #8
PhilF
 
PhilF's Avatar
 
Feb 2005
Colorado

22216 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
PhilF is online now   Reply With Quote
Old 2020-01-09, 22:23   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
So why factor it?


A valid question.
R.D. Silverman is offline   Reply With Quote
Old 2020-01-10, 01:02   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24·3·79 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-11, 20:13   #11
PrimeInteger
 
Jan 2020

516 Posts
Default

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?
PrimeInteger is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PArtial factorization of 2^852348659-1 ET_ PrimeNet 15 2018-06-10 18:40
Number Of Digits; I Hate To Ask storm5510 Other Mathematical Topics 14 2010-08-31 01:16
Number of digits display grobie 15k Search 13 2005-09-29 21:57
how do you find number of digits of a 2^n number? Unregistered Math 11 2004-11-30 22:53
5dpf, 5 digits from the end partial factors 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.