prime problem

Agrajag · 2004-05-04, 06:50

Hey all, I've been part of gimps for some time now, and in a network security course I'm doing at uni we've been given the following problem:
--------------------------------------------------------------
The project involves finding what Prof. Rivest calles "oreo cookies". These are consecutive integers (p, p+1, p+2) where p and p+2 are both prime, and the complete prime factorisation of p+1 is given. An example is (5, 2.3, 7), where "2.3" represents "two times three" (= 6). Your task is to find the largest oreo cookie you can, and send us the factorisation of p+1.

The catch is that Prof. Rivest is currently only interested in oreo cookies where p+1 is divisible by 1997.

Please note that the factorisation must be given as the product of powers of primes. For example, the factorisation of 96130371093750 should be given as:

2.3^2.5^17.7

which means 96130371093750 = 2*3(power of 2)*5(power of 17)*7.

----------------------------------------------------------------

was wondering if anyone could give me some tips on how to go about this problem?

Uncwilly · 2004-05-04, 12:28

You are looking for "twin primes". Normally they are refered to by the number in the middle (n+1,n-1). One of the math wizards here can tell you more.

jinydu · 2004-05-04, 12:38

The largest known twin prime is (33218925*(2^169690))-1.

http://primes.utm.edu/top20/page.php?id=1

I think (but I'm not sure) that the other twin is (33218925*(2^169690))+1. The website didn't make that very clear.

However, a quick check on a calculator reveals that none of the 20 twin primes have a middle number divisible by 1997.

EDIT: http://perso.wanadoo.fr/yves.gallot/...rcds.html#twin makes it clear that (33218925*(2^169690))+1 is indeed the other twin.

jinydu · 2004-05-04, 13:11

So you're looking for values of n such that 1997n-1 and 1997n+1 are prime.

The smallest such value of n is 54.

Hint: n must be divisible by 6.

wblipp · 2004-05-04, 14:07

There are some interesting tradeoffs in the difficulty of finding and proving large primes and the difficulty of factoring large numbers. The range of approaches also depends on how much time and computing power is available - a class collaboration for a semester could go much further than an individual for a night.

As jinydu pointed out, the middle number must be of the form 6x - otherwise at least one of the other numbers is divisible by 2 or 3. A little more work will also show that to eliminate 5 as a possible factor, the middle number must be either 30x or 30x+12. I'll stick with the 30x+12 case.

You also require the middle number to be a multiple of 1997. So you need integer solutions to 30x+12=1997y

Using Dario Alpern's Quadratic Integer Solver, you can quickly find that solutions are of the form y= 6 + 30t

Now you know the middle number is of the form 1997*(6+30*t). There are two general strategies from here. You can pick a range where you are sure you can factor 6+30t and look for the primes, or you can limit yourself to special values of 6+30t that are already factored. If you pick the second strategy, you may want to go back up a few paragraphs and pick the 30x route instead of the 30x+12 route.

To find the primes, you'll want to use one of the sieving programs. I've never done such a search, but I think PFGW's "abc" format would work.

To factor the middle number (if not forced to be pre-factored), you might be able to use Dario Alpern's Factoring Applet. For larger number you will need to use other methods.

wblipp · 2004-05-04, 15:08

Searching in the 65 digit range, PFGW and Alpertron took only a few minutes to find the Oreo
2 ^ 2 x 3 ^ 2 x 1997 x 1339115036882491896284968410284302168768502494818994029419041

And less than five more minutes around 96 digits to find

2 ^ 2 x 3 x 7 x 13 x 71 x 1997 x 184607 x 1116853 x 91621069741259657 x 41725296244311767159315973024836146511068406178172970363089

wblipp · 2004-05-04, 20:52

As you simply get larger, you run into the problem that you cannot factor the creme (middle of the oreo cookie). You can force the factorization to smaller numbers by proper selection of the form. For example, by choosing your (6+30t) to be 6*(1+5x)⁵, you can reduce the size of the remaining composite by a factor of 5. If you figure that you can probably factor 100 digit numbers, you can look for 500 digit oreos of the form 1997*6*(1+5t)⁵, where (1+5t) is 100 digits. It took a few hours to find a 505 digit oreo of this form:

2 x 3 x 7⁵ x 601⁵ x 1697⁵ x 1997 x 2221331321127842521176503⁵ x 170419913749602947794168163⁵ x 4046509251675607979406939228671806723909451⁵

Going much larger than this, your problem will be finding candidates. You will probably need a better search method.

William

Agrajag · 2004-05-04, 22:40

thanks a lot for your help, i'll probably have some more questions later but i'll see where this gets me :)

Agrajag · 2004-05-04, 23:06

hmm someone else in the class is already winning with a 5473 bit answer:

2^1307.3^2614.11.13.19.1997

damn! :P

wblipp · 2004-05-05, 12:05

Quote:

Originally Posted by Agrajag

in a network security course I'm doing at uni we've been given the following problem:

This is a good exercise. It lets you experience several key things:
1. Factoring is harder than primality proving.
2. Difficulty of increases rapidly with number size.
3. Better Algorithms are more important than faster hardware.
4. Competitive impulses can inspire communities to ever higher responses to security "puzzles."

Quote:

Originally Posted by Agrajag

hmm someone else in the class is already winning with a 5473 bit answer:

2^1307.3^2614.11.13.19.1997

I left some of the algorithmic improvements for you to discover yourself. Instead you found #4. Trying for a grand slam beat the pants off response is risky because of #2. A slightly better answer is

15737*4013#

"#" is the "primorial" symbol - it works like factorial except that only primes are included - so 4013# is the product of all prime numbers from 2 through 4013. It's an effective search idea because it guarantees that n-1 and n+1 do not have small prime factors, increasing the probability they are prime. I picked 4013# to be a little larger than the outstanding record, then used PFGW's ABC2 file format to search for a prime pair (a*4013#-1) and (a*4013#+1). It found 55 values of a where (a*4013#-1) is prime but (a*4013#+1) is composite before finding this pair. Use Dario Alpern's applet if you need an expansion or a list of the primes.

If you win the class competition, I'd like of week of your wasted idle computer cycles on the ElevenSmooth factoring project.
http://ElevenSmooth.com

William

Agrajag · 2004-05-06, 09:33

Thanks a lot for your help william! I think i'll try for an even higher one - if i get it i'll give you more than a weeks cpu cycles! (not too many though, gotta keep going with gimps :P). I found out today that apparently last years record was a 44k bit number!

question though - in "(a*4013#-1) and (a*4013#+1)." - did you only use prime numbers for 'a'? Does that increase the probability of those expressions being prime too?

2004-05-04, 06:50	#1
Agrajag May 2004 3² Posts	prime problem Hey all, I've been part of gimps for some time now, and in a network security course I'm doing at uni we've been given the following problem: -------------------------------------------------------------- The project involves finding what Prof. Rivest calles "oreo cookies". These are consecutive integers (p, p+1, p+2) where p and p+2 are both prime, and the complete prime factorisation of p+1 is given. An example is (5, 2.3, 7), where "2.3" represents "two times three" (= 6). Your task is to find the largest oreo cookie you can, and send us the factorisation of p+1. The catch is that Prof. Rivest is currently only interested in oreo cookies where p+1 is divisible by 1997. Please note that the factorisation must be given as the product of powers of primes. For example, the factorisation of 96130371093750 should be given as: 2.3^2.5^17.7 which means 96130371093750 = 23(power of 2)5(power of 17)7. ---------------------------------------------------------------- was wondering if anyone could give me some tips on how to go about this problem? Last fiddled with by Agrajag on 2004-05-04 at 06:53*

2004-05-04, 12:38	#3
jinydu Dec 2003 Hopefully Near M48 2·3·293 Posts	The largest known twin prime is (33218925(2^169690))-1. http://primes.utm.edu/top20/page.php?id=1 I think (but I'm not sure) that the other twin is (33218925(2^169690))+1. The website didn't make that very clear. However, a quick check on a calculator reveals that none of the 20 twin primes have a middle number divisible by 1997. EDIT: http://perso.wanadoo.fr/yves.gallot/...rcds.html#twin makes it clear that (33218925(2^169690))+1 is indeed the other twin. Last fiddled with by jinydu on 2004-05-04 at 12:47*

2004-05-04, 15:08	#6
wblipp "William" May 2003 New Haven 2360₁₀ Posts	Searching in the 65 digit range, PFGW and Alpertron took only a few minutes to find the Oreo 2 ^ 2 x 3 ^ 2 x 1997 x 1339115036882491896284968410284302168768502494818994029419041 And less than five more minutes around 96 digits to find 2 ^ 2 x 3 x 7 x 13 x 71 x 1997 x 184607 x 1116853 x 91621069741259657 x 41725296244311767159315973024836146511068406178172970363089 Last fiddled with by wblipp on 2004-05-04 at 15:15

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semiprime and n-almost prime candidate for the k's with algebra for the Sierpinski/Riesel problem	sweety439	sweety439	11	2020-09-23 01:42
Problem with prime 95 in worker #8	artesina	Information & Answers	5	2018-02-27 20:51
disk died, prime work lost forever? where to put prime? on SSD or HDD?	emily	PrimeNet	3	2013-03-01 05:49
Cullen prime problem	Citrix	Prime Cullen Prime	22	2007-02-23 10:46
Problem running prime-net on debian (woody) dual processor	thedagit	Software	3	2002-10-19 05:57

2004-05-04, 12:28	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 21770₈ Posts	You are looking for "twin primes". Normally they are refered to by the number in the middle (n+1,n-1). One of the math wizards here can tell you more.

2004-05-04, 13:11	#4
jinydu Dec 2003 Hopefully Near M48 1758₁₀ Posts	So you're looking for values of n such that 1997n-1 and 1997n+1 are prime. The smallest such value of n is 54. Hint: n must be divisible by 6.

2004-05-04, 14:07	#5
wblipp "William" May 2003 New Haven 2³×5×59 Posts	There are some interesting tradeoffs in the difficulty of finding and proving large primes and the difficulty of factoring large numbers. The range of approaches also depends on how much time and computing power is available - a class collaboration for a semester could go much further than an individual for a night. As jinydu pointed out, the middle number must be of the form 6x - otherwise at least one of the other numbers is divisible by 2 or 3. A little more work will also show that to eliminate 5 as a possible factor, the middle number must be either 30x or 30x+12. I'll stick with the 30x+12 case. You also require the middle number to be a multiple of 1997. So you need integer solutions to 30x+12=1997y Using Dario Alpern's Quadratic Integer Solver, you can quickly find that solutions are of the form y= 6 + 30t Now you know the middle number is of the form 1997(6+30t). There are two general strategies from here. You can pick a range where you are sure you can factor 6+30t and look for the primes, or you can limit yourself to special values of 6+30t that are already factored. If you pick the second strategy, you may want to go back up a few paragraphs and pick the 30x route instead of the 30x+12 route. To find the primes, you'll want to use one of the sieving programs. I've never done such a search, but I think PFGW's "abc" format would work. To factor the middle number (if not forced to be pre-factored), you might be able to use Dario Alpern's Factoring Applet. For larger number you will need to use other methods.

2004-05-04, 20:52	#7
wblipp "William" May 2003 New Haven 2³×5×59 Posts	As you simply get larger, you run into the problem that you cannot factor the creme (middle of the oreo cookie). You can force the factorization to smaller numbers by proper selection of the form. For example, by choosing your (6+30t) to be 6(1+5x)⁵, you can reduce the size of the remaining composite by a factor of 5. If you figure that you can probably factor 100 digit numbers, you can look for 500 digit oreos of the form 19976*(1+5t)⁵, where (1+5t) is 100 digits. It took a few hours to find a 505 digit oreo of this form: 2 x 3 x 7⁵ x 601⁵ x 1697⁵ x 1997 x 2221331321127842521176503⁵ x 170419913749602947794168163⁵ x 4046509251675607979406939228671806723909451⁵ Going much larger than this, your problem will be finding candidates. You will probably need a better search method. William

2004-05-04, 22:40	#8
Agrajag May 2004 3² Posts	thanks a lot for your help, i'll probably have some more questions later but i'll see where this gets me :)

2004-05-04, 23:06	#9
Agrajag May 2004 3² Posts	hmm someone else in the class is already winning with a 5473 bit answer: 2^1307.3^2614.11.13.19.1997 damn! :P

2004-05-06, 09:33	#11
Agrajag May 2004 3² Posts	Thanks a lot for your help william! I think i'll try for an even higher one - if i get it i'll give you more than a weeks cpu cycles! (not too many though, gotta keep going with gimps :P). I found out today that apparently last years record was a 44k bit number! question though - in "(a4013#-1) and (a4013#+1)." - did you only use prime numbers for 'a'? Does that increase the probability of those expressions being prime too?