Note:I just removed sci.crypt.random-numbers, as I deem it irrelevant
Helmut Richter <firstname.lastname@example.org> writes: > On Sat, 10 Aug 2013, Helmut Richter wrote: > > On Sat, 10 Aug 2013, jim wrote: > > > > > Is there any way to combine 2 primes to get a larger prime, either > > > guarantying the primality of the result or with a quick test for the > > > primality? > > > > Yes and No. > > > > Yes: if you have two primes p and q, then pq+1 can be prime with good > > luck, and testing it for primality is much simpler than testing an > > arbitrary number N where the prime decomposition of N-1 is not known. > > This fulfils your condition "primality of the result or with a quick test > > for the primality". > > > > No: The chance that pq+1 is prime is in general very low, and if it isn't, > > you get exactly nothing. > > I forgot: you can enhance it to something useful by searching k so that > kpq+1 *could* be prime. With many k you get many candidates for primes, > and each of them is easy to test, as long as the prime decomposition of k > is known. This is indeed a viable method for constructing large primes.
You don't need to know the prime decomposition of k as long as k<(pq)^2. (Or with some tweaks like KP, you can push that exponent towards 7/3, and even further towards 3 using CHG.)
Phil -- If "law-abiding citizens have nothing to fear" from privacy-invading technologies and policies, then law-abiding governments should have nothing to fear from whistleblowers.