mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-04-22, 20:53   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

28810 Posts
Default 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.
lukerichards is offline   Reply With Quote
Old 2018-04-22, 21:00   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

3·2,801 Posts
Default

Quote:
Originally Posted by lukerichards View Post

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.
science_man_88 is offline   Reply With Quote
Old 2018-04-22, 21:11   #3
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
https://en.wikipedia.org/wiki/Integer_factorization. What's the number in question ? That may help.
I've already been on that page. Looking for some advice.

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

Last fiddled with by lukerichards on 2018-04-22 at 21:12
lukerichards is offline   Reply With Quote
Old 2018-04-23, 00:09   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

24×11×13 Posts
Default

FWIW, the denominator not withstanding, and just from the form it is easy to find imaginary integer factors based on the composite exponent.
a1call is offline   Reply With Quote
Old 2018-04-23, 01:27   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

24·11·13 Posts
Default

If I am not mistaking
89134853
is a factor.
Corrections/Verifications are appreciated.
a1call is offline   Reply With Quote
Old 2018-04-23, 02:32   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

7×857 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-23, 05:38   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default

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!)
lukerichards is offline   Reply With Quote
Old 2018-04-23, 06:10   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

A mere typo.

504206 = 2 · 23 · 97 · 113

Doc, could you either post the C factors or put them in the FDB?
Dubslow is offline   Reply With Quote
Old 2018-04-23, 12:51   #9
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
lukerichards is offline   Reply With Quote
Old 2018-04-23, 13:10   #10
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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?
lukerichards is offline   Reply With Quote
Old 2018-04-23, 16:07   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110100112 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odds of Finding a Factor Gordon Factoring 18 2015-09-20 20:33
how much ECM without finding an existing factor dbaugh PrimeNet 4 2013-01-11 16:31
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
Chances of finding a factor with ECM smh Factoring 16 2004-03-30 18:49
possibility of finding a factor there_is_no_spoon Math 10 2004-03-11 20:05

All times are UTC. The time now is 20:06.


Thu Oct 6 20:06:20 UTC 2022 up 49 days, 17:34, 0 users, load averages: 1.54, 1.32, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔