20070506, 19:59  #1 
"Ben"
Feb 2007
13×283 Posts 
interesting P1 result
I just had a rather interesting result from a P1 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^761 I was surprised to find in my logfile a C90! Using msieve, the C90 = P45*P45 = 929423050985198068638864635036910757233824911* 935342943029689776082424282393833755687543541 P1 = 2.3.3.5.7.13.13.19.31.157.7561.7993.8101.43867.98911.2786221.15949441 Q1 = 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 
20070506, 20:21  #2 
"Ben"
Feb 2007
111001011111_{2} 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^781 give a C69 = P35*P35 = 15841128423127506659651289760017421* 15885940667605943736481986477867541 P1 = 2.2.3.5.7.13.29.31.59.67.101.223.241.2251.3457.13729.1407829 Q1 = 2.2.3.5.13.29.31.59.67.223.241.709.2251.3457.13729.1407829 differing by a factor of 709/707  ben. 
20070506, 20:55  #3 
"William"
May 2003
New Haven
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^{76}1 = (315^{19}1)*(315^{19}+1)*(315^{38}+1) (there is a bit more because each of these is divisible by (3151),(315+1) and (315^{2}+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^{n} ± 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^761 at http://www.alpertron.com.ar/ECM.HTM Last fiddled with by wblipp on 20070506 at 21:08 Reason: Mention alpertron 
20070506, 21:11  #4 
"Ben"
Feb 2007
13×283 Posts 
I know a little about algebraic factors  these factorizations came about during a test of P1 and bigint software I'm writing (as a hobby), where I just step through a bunch of k and n for k^n1. I don't algebraicly factor anything before running P1 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. 
20070506, 22:42  #5  
"William"
May 2003
New Haven
3·7·113 Posts 
Quote:
If you're looking for useful tests, I'd love to see you extend Brent's results for p^q1 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 75130 digits that haven't yet had enough ECM work to be released to the oddperfect composites page for NFS aficionados. William 

20070507, 01:29  #6  
"Ben"
Feb 2007
13·283 Posts 
Quote:
Quote:


20070507, 01:49  #7  
Aug 2004
New Zealand
2·5·23 Posts 
Quote:
Code:
$ time echo '(315^761)/2^4/140915158931'  ecm pm1 10000000 1000000000 GMPECM 6.1.1 [powered by GMP 4.1.4] [P1] Input number is (315^761)/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^761)/2^4/140915158931)/869329291828128573228185789905308051435432918706003543745501428917129867441206149282949851 has 88 digits real 0m19.421s user 0m19.342s sys 0m0.053s 

20070507, 21:15  #8 
Aug 2002
Buenos Aires, Argentina
2×17×43 Posts 
Let an odd number and integer.
has algebraic factors and . Let and , not necessarily primes. Now we want to compute So these small fractions are very common. Last fiddled with by alpertron on 20070507 at 21:21 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some interesting patterns regarding mod  CuriousKit  Miscellaneous Math  24  20150406 18:40 
Interesting observation  MooooMoo  Lounge  15  20061114 03:40 
A new interesting thing about 15k  robert44444uk  15k Search  0  20050406 23:00 
Very interesting K8 paper...  Xyzzy  Hardware  10  20041123 08:24 
Something Interesting  clowns789  Hardware  1  20031220 12:36 