mersenneforum.org Factor-finding algorithms (and software)
 Register FAQ Search Today's Posts Mark Forums Read

 2018-04-22, 20:53 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25·32 Posts Factor-finding 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 $a \cdot b^c+d$.
2018-04-22, 21:00   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24×3×52×7 Posts

Quote:
 Originally Posted by lukerichards Any suggestions for algorithms to find factors of large integers? Especially when the integer has been trial factored up to,say, 10^10.
https://en.wikipedia.org/wiki/Integer_factorization. What's the number in question ? That may help.

2018-04-22, 21:11   #3
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts

Quote:
 Originally Posted by science_man_88 https://en.wikipedia.org/wiki/Integer_factorization. What's the number in question ? That may help.

The number is $(3^{504206}+1)/150049833940377672648926239930$

Last fiddled with by lukerichards on 2018-04-22 at 21:12

 2018-04-23, 00:09 #4 a1call     "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.
 2018-04-23, 01:27 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 43578 Posts If I am not mistaking 89134853 is a factor. Corrections/Verifications are appreciated.
2018-04-23, 02:32   #6
Dr Sardonicus

Feb 2017
Nowhere

176616 Posts

Quote:
 Originally Posted by lukerichards I've already been on that page. Looking for some advice. The number is $(3^{504206}+1)/150049833940377672648926239930$
There is an obvious algebraic (cyclotomic) factorization.

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 Pari-GP could carry out the pseudoprime test; it's a BIG-honkin' number.

In addition to the prime factors mentioned, we also have

70601370627701

798087896392921

31181934032520084217683832052280453426721598216094871026492932287412448715951254226575121

and a number of composite factors, denoted with a C.

 2018-04-23, 05:38 #7 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 4408 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!)
 2018-04-23, 06:10 #8 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2018-04-23, 12:51   #9
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Quote:
 Originally Posted by lukerichards 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!)
My mistake! Tried typing it into Python in a rush this morning to double check them, I must have copied across wrong.

So - huge thanks to Doc.

2018-04-23, 13:10   #10
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Quote:
 Originally Posted by Dr Sardonicus There is an obvious algebraic (cyclotomic) factorization. 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
Can anyone perhaps explain where the -9 comes from in the above function?

2018-04-23, 16:07   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24×3×52×7 Posts

Quote:
 Originally Posted by lukerichards Can anyone perhaps explain where the -9 comes from in the above function?
polcyclo(n,{a = 'x}): n-th cyclotomic polynomial evaluated at a.
subst(x,y,z): in expression x, replace the variable y by the expression z.

Both from PARI/GP help.

 Similar Threads Thread Thread Starter Forum Replies Last Post Gordon Factoring 18 2015-09-20 20:33 dbaugh PrimeNet 4 2013-01-11 16:31 JuanTutors Software 20 2004-09-26 09:47 smh Factoring 16 2004-03-30 18:49 there_is_no_spoon Math 10 2004-03-11 20:05

All times are UTC. The time now is 08:55.

Sun Oct 2 08:55:11 UTC 2022 up 45 days, 6:23, 0 users, load averages: 0.68, 1.00, 1.18