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 n1 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