mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-01-19, 03:16   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default Crandall/Pomerance/Euler series question?

Hello,

In "Prime Numbers: A Computational Perspective", there's a question whether a series will eventually cover all the prime numbers.
Starting with 2. Add 1 to your product of primes, factor that number, use the low prime factor. Repeat.

Here's the resulting series:
2
3
7
43
13
53
5
6221671
38709183810571
...
4357 (last in known list)

From what I've seen it's stuck on the 43rd term, a 180 digit number known to be composite. Does anyone know if this nut has been cracked? I'm interested in factoring it and wouldn't want to duplicate previous work. Forgive me if there's another name for this series.

In addition, I'm curious if anyone has looked at different branches (if you will) of the factor sequence.

For instance, we have 2 * 3 * 7 * 43 +1 = 1807 = 13 * 139. Instead of taking the 13 "low branch", take 139 and see what progress can be made there.

2
3
7
43
139*
5
233
6079
457
...


Thanks,
Grandpa

Last fiddled with by grandpascorpion on 2005-01-19 at 03:18
grandpascorpion is offline   Reply With Quote
Old 2005-01-19, 04:34   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

94116 Posts
Default

http://www.research.att.com/cgi-bin/...i?Anum=A000945

http://www.research.att.com/cgi-bin/...i?Anum=A000946

Looks like no recent progress on either series.
wblipp is offline   Reply With Quote
Old 2005-01-19, 04:50   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

Post that 180-digit composite here, and I will bet that you will find some people interested in trying to factor it. At some point, we may reach the point where we find the smallest factor of the next product+1 by ECM but cannot rigorously prove that the factor is actually the smallest.
philmoore is offline   Reply With Quote
Old 2005-01-20, 04:21   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Thanks for the feedback.

Here's the expression:
2 * 3 * 7 * 43 * 13 * 53 * 5 * 6221671 * 38709183810571 * 139 * 2801 * 11 * 17 * 5471 * 52662739 * 23003 * 30693651606209 * 37 * 1741 * 1313797957 * 887 * 71 * 7127 * 109 * 23 * 97 * 159227 * 643679794963466223081509857 * 103 * 1079990819 * 9539 * 3143065813 * 29 * 3847 * 89 * 19 * 577 * 223 * 139703 * 457 * 9649 * 61 * 4357+ 1

The number is:
2784908410762794071887414394815651793559267258537102016323316206429820623899017418905799635244237826374359490416665
25000702723914662388812510545494307250950777886431051612811386531

For the past 36 hours, I have been trying to factor this at http://www.alpertron.com.ar/ECM.HTM

Current stats:
Limit: B1=1000000, B2=100000000 Curve 328
Digits in factor: > 15 100%; > 20, 100%; > 25, 86%; > 30, 15%; > 35, 2%, > 40, 0
mod mult: 329384000 Step1: 46%

I'm still a newbie to this. As great as it is, it's a Java applet. Perhaps, someone could recommend a different tack or a way to optimize using the applet.

Thanks
grandpascorpion is offline   Reply With Quote
Old 2005-01-20, 09:15   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

3×5×743 Posts
Default

Quote:
Originally Posted by philmoore
Post that 180-digit composite here, and I will bet that you will find some people interested in trying to factor it. At some point, we may reach the point where we find the smallest factor of the next product+1 by ECM but cannot rigorously prove that the factor is actually the smallest.
There is good reason to believe that this number will be factored soon --- in the next five years or so.

There are two cases to consider: the smallest factor is small, under 50 digits or so, or that it is not. If the former, a concerted ECM attack should find it and the co-factor, if not prime, will be relatively easy by GNFS. If the smaller factor is too large, the entire number is just about within reach of GNFS now. The current record is RSA-576 which has 174 digits, if I remember correctly. That's only 6 digits short of the case in question.


Paul
xilman is online now   Reply With Quote
Old 2005-01-20, 09:44   #6
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

1010110011012 Posts
Default

grandpascorpion,
Try using GMP-ECM. It will be much faster than the applet. It is available from Paul Zimmerman's page - just do a google search. Mind you, you need GMp-ECM and not the ECMNET extension. Also, read up Paul Z.'s main page. It will give you information on what bounds to use and what number of factors to run.

From the information you posted about the curves you have already run, it would make sense to start the effort at 30 digits. Also, there are a couple of threads in the factoring forum that talk about running GMP-ECM, so reading them will also be useful.
garo is offline   Reply With Quote
Old 2005-01-20, 12:24   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Thanks, will do.
grandpascorpion is offline   Reply With Quote
Old 2005-01-20, 13:51   #8
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101ร—103 Posts

101000000011102 Posts
Default

Using the applet I have run curves number 800-850.
Uncwilly is offline   Reply With Quote
Old 2005-01-20, 14:49   #9
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

100000110110002 Posts
Default

I've done up through 35 digits (1e6)... We can probably coordinate to do 40 digits very quickly...
Attached Files
File Type: gz ecm.out.gz (26.5 KB, 129 views)
Xyzzy is offline   Reply With Quote
Old 2005-01-20, 14:56   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Sorry another newbie question ... say I pick B1=3000000 (the opt value for a 40 digit factor) and B2=B1*100, is there a chance a smaller factor (say 25 digits) could be missed? (I think Phil Moore may have alluded to this earlier in the thread)

Thanks,
Grandpa
grandpascorpion is offline   Reply With Quote
Old 2005-01-20, 15:04   #11
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

840810 Posts
Default

Quote:
Originally Posted by grandpascorpion
Sorry another newbie question ... say I pick B1=3000000 (the opt value for a 40 digit factor) and B2=B1*100, is there a chance a smaller factor (say 25 digits) could be missed? (I think Phil Moore may have alluded to this earlier in the thread)
In my (limited) experience, if there is a smaller factor it will be found, if you run enough curves... I think the advantage to running the more curves to a smaller bound is you get a greater statistical chance of getting a "winning" sigma value...

Since I've done up to 35 digits entirely any further work needs to be done at 40 digits, so your B1 should be 3e6...

On my K8, with a heavy load, it looks like I can do one curve every 75s or so... So 2900 curves should take about 60h... I plan to run a few other ECM jobs at the same time, so it will take much longer though... The good news is we can all split up the work...

Code:
GMP-ECM 5.0.3 [powered by GMP 4.1.4] [ECM]
Input number is 278490841076279407188741439481565179355926725853710201632331620642982062389901741890579963524423782637435949041666525000702723914662388812510545494307250950777886431051612811386531 (180 digits)
Using B1=3000000, B2=4016636514, polynomial Dickson(12), sigma=4291087327
Step 1 took 38399ms
Step 2 took 36153ms
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carl Pomerance himself about 210 YuL Math 3 2017-06-02 10:51
Exercise 1.23 in Crandall & Pomerance sean Factoring 2 2006-10-23 21:08
The original paper on the Crandall/Fagin DWT Barry Fagin Math 2 2006-01-04 19:46
Crandall & Pomerance Numbers Math 16 2005-10-16 00:53
Question about a power series Orgasmic Troll Math 1 2004-09-13 19:01

All times are UTC. The time now is 19:31.


Wed Jan 26 19:31:06 UTC 2022 up 187 days, 14 hrs, 0 users, load averages: 1.19, 1.21, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”