mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   interesting P-1 result (https://www.mersenneforum.org/showthread.php?t=8096)

 bsquared 2007-05-06 19:59

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 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[sup]76[/sup]-1 = (315[sup]19[/sup]-1)*(315[sup]19[/sup]+1)*(315[sup]38[/sup]+1)

(there is a bit more because each of these is divisible by (315-1),(315+1) and (315[sup]2[/sup]+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

[url]http://elevensmooth.com/MathFAQ.html#Algebraic[/url]

Once you learn how algebraic factors work, you will want to be become familiar with Richard Brent's list. He collects factors of a[sup]n[/sup] ± 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 [url]http://www.alpertron.com.ar/ECM.HTM[/url]

 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=bsquared;105407]these factorizations came about during a test of P-1 and bigint software I'm writing (as a hobby),[/QUOTE]

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=wblipp;105413]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.[/quote]

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 :wink: .

[quote=wblipp;105413]
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.
[/quote]

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=bsquared;105418]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.[/QUOTE]

[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
[/CODE]

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.

 All times are UTC. The time now is 04:58.