Thread: prime problem
View Single Post
Old 2004-05-05, 12:05   #10
wblipp's Avatar
May 2003
New Haven

22×32×5×13 Posts

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."

Originally Posted by Agrajag
hmm someone else in the class is already winning with a 5473 bit answer:

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


"#" 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.

wblipp is offline   Reply With Quote