20180422, 20:53  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}·3^{2} Posts 
Factorfinding algorithms (and software)
Wasn't sure whether to post this in here or the software section.
Any suggestions for algorithms to find factors of large integers? Especially when the integer has been trial factored up to,say, 10^10. I've looked into Pollard's Rho algorithm and I'm familiar with this but I'm not sure of the differences and/or advantages of this over other algorithms. Furthermore, any suggested software for running these algorithms? The number in question is not easy to represent in the form . 
20180422, 21:00  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{4}×3×5^{2}×7 Posts 
Quote:


20180422, 21:11  #3  
"Luke Richards"
Jan 2018
Birmingham, UK
440_{8} Posts 
Quote:
The number is Last fiddled with by lukerichards on 20180422 at 21:12 

20180423, 00:09  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,287 Posts 
FWIW, the denominator not withstanding, and just from the form it is easy to find imaginary integer factors based on the composite exponent.

20180423, 01:27  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
4357_{8} Posts 
If I am not mistaking
89134853 is a factor. Corrections/Verifications are appreciated. 
20180423, 02:32  #6  
Feb 2017
Nowhere
1766_{16} Posts 
Quote:
e=50426 = 2*23*97*113 The cyclotomic factors of 3^e + 1 may be expressed subst(polcyclo(1),x,9) = 10 = 2*5 subst(polcyclo(23),x,9) = 886293811965250109593 = 12553493*70601370627701 subst(polcyclo(97),x,9) = 36435389420558953270066024970614489276986756193881275167980104490959189424046938682357297537 = 389*C subst(polcyclo(113),x,9) = 67515512184974521212979319675987068172559200196093720344402244124464181676558236916175760059116297628330433 = 2713*798087896392921*31181934032520084217683832052280453426721598216094871026492932287412448715951254226575121 subst(polcyclo(23*97),x,9) 9852097*C subst(polcyclo(23*113),x,9) C subst(polcyclo(97*113),x,9) C subst(polcyclo(23*97*113),x,9) 114958969*? The ? indicates that I lost patience before PariGP could carry out the pseudoprime test; it's a BIGhonkin' number. In addition to the prime factors mentioned, we also have 70601370627701 798087896392921 31181934032520084217683832052280453426721598216094871026492932287412448715951254226575121 and a number of composite factors, denoted with a C. 

20180423, 05:38  #7 
"Luke Richards"
Jan 2018
Birmingham, UK
440_{8} Posts 
Thank you incredibly, Dr Sardonicus.
Am I right in thinking, however, that you used e=50426 rather than e=504206? Most of the factors you gave are not actually factors (although 1 is!) 
20180423, 12:51  #9  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Quote:
So  huge thanks to Doc. 

20180423, 13:10  #10 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Can anyone perhaps explain where the 9 comes from in the above function?

20180423, 16:07  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{4}×3×5^{2}×7 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odds of Finding a Factor  Gordon  Factoring  18  20150920 20:33 
how much ECM without finding an existing factor  dbaugh  PrimeNet  4  20130111 16:31 
Probability of finding a factor  JuanTutors  Software  20  20040926 09:47 
Chances of finding a factor with ECM  smh  Factoring  16  20040330 18:49 
possibility of finding a factor  there_is_no_spoon  Math  10  20040311 20:05 