mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-08-10, 07:29   #1
Joppe_Bos
 
Apr 2007

448 Posts
Smile The factorization of primorials +/- 1

Hi all,

As a hobby project I extended the tables for the primorials +/- 1 from the World Integer Factorization Center. Right now I have the tables with n <= 160.

I did quite some amount of ECM work on the extensions as well as one the original tables (and managed to find quite some prime factors). I have mailed Hisanori Mishima but not all my new factors for the original list are on the WIFC website yet.

If anyone is interested in helping out please report ECM work done or factors found in this thread. I made a very basic website showing how many curves I have done on these numbers together with the tables at primorial.unit82.com.

Furthermore I am quite interested in any theory about the factorization of these numbers. When searching for some articles I managed to find only a few about the primorial primes, so if anyone knows some good resources please let me know!

Thanks,

Joppe
Joppe_Bos is offline   Reply With Quote
Old 2007-08-11, 02:14   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

I'm reserving 76#+1 here (Edit: and 82#+1), since I figure this is the most obvious place. If someone wants to give me editing privileges, I'll restrict myself to this thread and only handle the tracking.(I would suck as a mod, but I'm sure people already know that)

Last fiddled with by jasong on 2007-08-11 at 02:25
jasong is offline   Reply With Quote
Old 2007-08-11, 02:32   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

If I may ask a stupid question. How do you put comments in an ecm input file?
jasong is offline   Reply With Quote
Old 2007-08-11, 02:42   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

30458 Posts
Default

I have always wondered about this, but never had the time to implement this...

If we take P#+1 or P#-1 and do a P-1/P+1 test using B1=P, how many factors would be end up finding? What would be the distribution of such factors? Are any such factors known for large P?
Citrix is offline   Reply With Quote
Old 2007-08-11, 04:35   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default

The only solution I know of is 2#+1 is divisible by 3. Are there any more?
Citrix is offline   Reply With Quote
Old 2007-08-11, 10:15   #6
Joppe_Bos
 
Apr 2007

448 Posts
Default

Quote:
Originally Posted by jasong View Post
I'm reserving 76#+1 here (Edit: and 82#+1), since I figure this is the most obvious place. If someone wants to give me editing privileges, I'll restrict myself to this thread and only handle the tracking.(I would suck as a mod, but I'm sure people already know that)
Thanks for the help jasong! You probably want to reserve E_76 = 383# + 1 and E_82 = 421# + 1. Just report the amount of ECM curves here so I can update the stats on the website. My first goal is to ECM all the numbers up to 40 digits and then 45 (and at the same time focus on the smaller n in #p_n +/- 1 (where p_n is the nth prime).

Quote:
Originally Posted by jasong View Post
If I may ask a stupid question. How do you put comments in an ecm input file?
Lines beginning with a "#" are comments as far as I know.

Last fiddled with by Joppe_Bos on 2007-08-11 at 10:17 Reason: Typo
Joppe_Bos is offline   Reply With Quote
Old 2007-08-11, 11:14   #7
Joppe_Bos
 
Apr 2007

22·32 Posts
Default

Quote:
Originally Posted by Citrix View Post
I have always wondered about this, but never had the time to implement this...

If we take P#+1 or P#-1 and do a P-1/P+1 test using B1=P, how many factors would be end up finding? What would be the distribution of such factors? Are any such factors known for large P?
Quote:
Originally Posted by Citrix View Post
The only solution I know of is 2#+1 is divisible by 3. Are there any more?
Maybe I don't understand your question right but aren't all primorials +/- 1 a solution? For example take a number p_n# + 1 (the nth prime) than factoring with Pollard p-1 algorithm with a bound p_n will always give the trivial factor p_n# + 1 itself (the same holds for p_n# - 1 and using Williams p + 1 algorithm with bound p_n).

About the non-trivial factors I have no idea about the distribution (interesting question!), the first non-trivial factor which can be found with Pollard p-1 with pound p_n is when n = 7 so p_7# + 1 = 17# + 1 = 510511 which has a factor 2 * 3^2 + 1.
Joppe_Bos is offline   Reply With Quote
Old 2007-08-11, 12:15   #8
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·2,963 Posts
Default

Set up an ECMNet server and you will probably have many more helpers.
rogue is online now   Reply With Quote
Old 2007-08-11, 18:55   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default

Quote:
Originally Posted by Joppe_Bos View Post
Maybe I don't understand your question right but aren't all primorials +/- 1 a solution? For example take a number p_n# + 1 (the nth prime) than factoring with Pollard p-1 algorithm with a bound p_n will always give the trivial factor p_n# + 1 itself (the same holds for p_n# - 1 and using Williams p + 1 algorithm with bound p_n).
only if P#+1 is prime. Hence I was asking for the distribution of these factors.

In short find n such that P#+1== 0 (mod n) and the largest prime divisor of n-1 is smaller or equal to P. I tested all n up to 100K, but did not not find a solution except n=3.

Similarly, find x such that P#-1==0 (mod x) and the largest prime divisor of x+1 is smaller or equal to P. No solutions for this.
Citrix is offline   Reply With Quote
Old 2007-08-11, 20:18   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default

Quote:
Originally Posted by Citrix View Post

In short find n such that P#+1== 0 (mod n) and the largest prime divisor of n-1 is smaller or equal to P. I tested all n up to 100K, but did not not find a solution except n=3.

Similarly, find x such that P#-1==0 (mod x) and the largest prime divisor of x+1 is smaller or equal to P. No solutions for this.
Never mind this, a bug in my code, found several solutions for this.
Citrix is offline   Reply With Quote
Old 2007-08-11, 23:17   #11
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by rogue View Post
Set up an ECMNet server and you will probably have many more helpers.
Um, because of my impulsiveness and the difficulty of compiling ecm on my quad-core, I'd like to unreserve my numbers.
jasong is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primorials squared primes? siegert81 Math 6 2010-12-28 15:17
Factorization of 7,254+ dleclair NFSNET Discussion 1 2006-03-21 05:11
Factorization of 11,212+ Wacky NFSNET Discussion 1 2006-03-20 23:43
Factorization of 5,307- Jeff Gilchrist NFSNET Discussion 7 2005-02-23 19:46
Factors of primorials grandpascorpion Math 9 2005-02-10 07:13

All times are UTC. The time now is 23:07.

Thu Oct 1 23:07:22 UTC 2020 up 21 days, 20:18, 0 users, load averages: 1.75, 1.87, 1.82

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.