interesting P-1 result

bsquared · 2007-05-06, 19:59

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 · 2007-05-06, 20:21

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.

wblipp · 2007-05-06, 20:55

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

315⁷⁶-1 = (315¹⁹-1)*(315¹⁹+1)*(315³⁸+1)

(there is a bit more because each of these is divisible by (315-1),(315+1) and (315²+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 aⁿ ± 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

bsquared · 2007-05-06, 21:11

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.

wblipp · 2007-05-06, 22:42

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

bsquared · 2007-05-07, 01:29

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.

sean · 2007-05-07, 01:49

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
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

alpertron · 2007-05-07, 21:15

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.

2007-05-06, 19:59	#1
bsquared "Ben" Feb 2007 7223₈ 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 = P45P45 = 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:55	#3
wblipp "William" May 2003 Near Grandkid 3×7×113 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 315⁷⁶-1 = (315¹⁹-1)(315¹⁹+1)(315³⁸+1) (there is a bit more because each of these is divisible by (315-1),(315+1) and (315²+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 aⁿ ± 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-07, 21:15	#8
alpertron Aug 2002 Buenos Aires, Argentina 2²·373 Posts	Let $b$ an odd number and $n>0$ integer. $a^{(b2^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
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

2007-05-06, 20:21	#2
bsquared "Ben" Feb 2007 111010010011₂ 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 = P35P35 = 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, 21:11	#4
bsquared "Ben" Feb 2007 E93₁₆ 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.