mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-06, 19:59   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

CC116 Posts
Default 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
bsquared is offline   Reply With Quote
Old 2007-05-06, 20:21   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

CC116 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2007-05-06, 20:55   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2·32·131 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2007-05-06, 21:11   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2007-05-06, 22:42   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
wblipp is offline   Reply With Quote
Old 2007-05-07, 01:29   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5×653 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 View Post
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.
bsquared is offline   Reply With Quote
Old 2007-05-07, 01:49   #7
sean
 
sean's Avatar
 
Aug 2004
New Zealand

3·73 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
GMP-ECM 6.1.1 [powered by GMP 4.1.4] [P-1]
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
On a moderately loaded Intel(R) Core(TM)2 Quad CPU @ 2.40GHz
sean is offline   Reply With Quote
Old 2007-05-07, 21:15   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001010002 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some interesting patterns regarding mod CuriousKit Miscellaneous Math 24 2015-04-06 18:40
Interesting observation MooooMoo Lounge 15 2006-11-14 03:40
A new interesting thing about 15k robert44444uk 15k Search 0 2005-04-06 23:00
Very interesting K8 paper... Xyzzy Hardware 10 2004-11-23 08:24
Something Interesting clowns789 Hardware 1 2003-12-20 12:36

All times are UTC. The time now is 22:21.

Sun Jul 12 22:21:43 UTC 2020 up 109 days, 19:54, 1 user, load averages: 1.48, 1.73, 1.63

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.