
Re: Combining Primes
Posted:
Aug 19, 2013 1:07 PM


Note:I just removed sci.crypt.randomnumbers, as I deem it irrelevant
Helmut Richter <hhrm@web.de> 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 N1 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 "lawabiding citizens have nothing to fear" from privacyinvading technologies and policies, then lawabiding governments should have nothing to fear from whistleblowers.

