mersenneforum.org interesting P-1 result
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-06, 19:59 #1 bsquared     "Ben" Feb 2007 E2316 Posts interesting P-1 result I just had a rather interesting result from a P-1 factorization that I thought I'd share... apologies if this has been found before, although a google seach on the factors didn't turn up any hits. Using B1=10^7 and B2=10^9 on 315^76-1 I was surprised to find in my logfile a C90! Using msieve, the C90 = P45*P45 = 929423050985198068638864635036910757233824911* 935342943029689776082424282393833755687543541 P-1 = 2.3.3.5.7.13.13.19.31.157.7561.7993.8101.43867.98911.2786221.15949441 Q-1 = 2.2.3.3.5.7.13.13.19.31.79.7561.7993.8101.43867.98911.2786221.15949441 which differ by a factor of 158/157 are such things 'common'? - ben
 2007-05-06, 20:21 #2 bsquared     "Ben" Feb 2007 7×11×47 Posts hmm, evidently not that uncommon. I just found another one (I swear I'm not constructing these!) B1=10^7, B2=10^9 on 708^78-1 give a C69 = P35*P35 = 15841128423127506659651289760017421* 15885940667605943736481986477867541 P-1 = 2.2.3.5.7.13.29.31.59.67.101.223.241.2251.3457.13729.1407829 Q-1 = 2.2.3.5.13.29.31.59.67.223.241.709.2251.3457.13729.1407829 differing by a factor of 709/707 - ben.
 2007-05-06, 20:55 #3 wblipp     "William" May 2003 New Haven 2,371 Posts If you start with two composites of the same size, it's not that unusual to find largest factors of the same size. The simple algebraic factors of your numbers are 31576-1 = (31519-1)*(31519+1)*(31538+1) (there is a bit more because each of these is divisible by (315-1),(315+1) and (3152+1)). Your C45s are the largest factors of the two first two terms. NOTE: YOU ARE WASTING COMPUTER POWER FACTORING THIS WAY. YOU SHOULD MANUALLY SEPARATE OUT THE ALGEBRAIC FACTORS If you need to study up on algebraic factors, you can check the Cunningham Book. I also made an attempt to explain them in the Elevensmooth Math FAQ http://elevensmooth.com/MathFAQ.html#Algebraic Once you learn how algebraic factors work, you will want to be become familiar with Richard Brent's list. He collects factors of an ± 1 witn a and n both < 10,000. Your number is completely factored there; you can find these factorizations much more quickly and save your computing power for factorization not yet known, which you can then email for inclusion in the next update. If you just want the factors, Dario Alpern's java factoring applet knows about the algebraic factors and knows about Richard Brent's list of factors. So the fastest way to get the factors is to enter 315^76-1 at http://www.alpertron.com.ar/ECM.HTM Last fiddled with by wblipp on 2007-05-06 at 21:08 Reason: Mention alpertron
 2007-05-06, 21:11 #4 bsquared     "Ben" Feb 2007 1110001000112 Posts I know a little about algebraic factors - these factorizations came about during a test of P-1 and bigint software I'm writing (as a hobby), where I just step through a bunch of k and n for k^n-1. I don't algebraicly factor anything before running P-1 during this test/benchmark, and it didn't occur to me to check after the fact. I guess I got too excited to see the routine pull out a 90 digit factor... I didn't know about Richard Brent's tables... thanks I will check that out. - ben.
2007-05-06, 22:42   #5
wblipp

"William"
May 2003
New Haven

2,371 Posts

Quote:
 Originally Posted by bsquared these factorizations came about during a test of P-1 and bigint software I'm writing (as a hobby),
Ahh. Leaving the algebraic factors in place might be an inspired test strategy because it greatly increases the chances there are large P-1 factors to find, even if they aren't previously unknown factors.

If you're looking for useful tests, I'd love to see you extend Brent's results for p^q-1 with primes p and q. I expect most such factors to eventually be of interest to oddperfect.org. Or perhaps run through my list of composites of 75-130 digits that haven't yet had enough ECM work to be released to the oddperfect composites page for NFS aficionados.

William

2007-05-07, 01:29   #6
bsquared

"Ben"
Feb 2007

1110001000112 Posts

Quote:
 Originally Posted by wblipp Ahh. Leaving the algebraic factors in place might be an inspired test strategy because it greatly increases the chances there are large P-1 factors to find, even if they aren't previously unknown factors.
Well, you're giving me a little more credit than I deserve by calling it 'inspired', but these numbers are useful in that they seem to produce more large factors than just picking random large integers. The 'inspiration' for the test cases comes from a birthday in my family: I found a 31 digit factor in 1003^77-1, and then just continued to use numbers that are built from dates... not exactly mathematically rigorous .

Quote:
 Originally Posted by wblipp If you're looking for useful tests, I'd love to see you extend Brent's results for p^q-1 with primes p and q. I expect most such factors to eventually be of interest to oddperfect.org. Or perhaps run through my list of composites of 75-130 digits that haven't yet had enough ECM work to be released to the oddperfect composites page for NFS aficionados.
Of course, I'd rather do tests that are useful, so I'll continue with the things you suggest. Can you post a link to the composites you're talking about? I assume these numbers are not urgent - I doubt my code is nearly as fast as GMP-ECM, for instance. Speaking of which, could someone humor me and repeat the factorization in the first post using P-1 and report the timings (and hardware used)? I'd like to have a baseline to compare against and I don't have access to a build of GMP.

2007-05-07, 01:49   #7
sean

Aug 2004
New Zealand

111001002 Posts

Quote:
 Originally Posted by bsquared Speaking of which, could someone humor me and repeat the factorization in the first post using P-1 and report the timings (and hardware used)? I'd like to have a baseline to compare against and I don't have access to a build of GMP.
Code:
\$ time echo '(315^76-1)/2^4/140915158931' | ecm -pm1 10000000 1000000000
Input number is (315^76-1)/2^4/140915158931 (178 digits)
Using B1=10000000, B2=1054517322, polynomial x^24, x0=255846568
Step 1 took 13506ms
Step 2 took 5835ms
********** Factor found in step 2: 869329291828128573228185789905308051435432918706003543745501428917129867441206149282949851
Found composite factor of 90 digits: 869329291828128573228185789905308051435432918706003543745501428917129867441206149282949851
Composite cofactor ((315^76-1)/2^4/140915158931)/869329291828128573228185789905308051435432918706003543745501428917129867441206149282949851 has 88 digits

real    0m19.421s
user    0m19.342s
sys     0m0.053s

 2007-05-07, 21:15 #8 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·112 Posts Let $b$ an odd number and $n>0$ integer. $a^{(b*2^n)}-1$ has algebraic factors $a^b-1$ and $a^b+1$. Let $\large p = \frac {a^b-1}{a-1}$ and $\large q = \frac{a^b+1}{a+1}$, not necessarily primes. Now we want to compute $\large \frac{p-1}{q-1}$ $\large \frac{p-1}{q-1} = \frac{\frac {a^b-1}{a-1}-1} {\frac{a^b+1}{a+1}-1} = \frac{\frac {a^b-a}{a-1}} {\frac{a^b-a}{a+1}} = \frac{a+1}{a-1}$ So these small fractions are very common. Last fiddled with by alpertron on 2007-05-07 at 21:21

 Similar Threads Thread Thread Starter Forum Replies Last Post CuriousKit Miscellaneous Math 24 2015-04-06 18:40 MooooMoo Lounge 15 2006-11-14 03:40 robert44444uk 15k Search 0 2005-04-06 23:00 Xyzzy Hardware 10 2004-11-23 08:24 clowns789 Hardware 1 2003-12-20 12:36

All times are UTC. The time now is 01:38.

Sat Jun 25 01:38:01 UTC 2022 up 71 days, 23:39, 0 users, load averages: 0.91, 0.91, 0.98

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.

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