Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Combining Primes
Replies: 81   Last Post: Aug 19, 2013 1:12 PM

 Messages: [ Previous | Next ]
 Phil Carmody Posts: 2,219 Registered: 12/7/04
Re: Combining Primes
Posted: Aug 19, 2013 1:07 PM

Note:I just removed sci.crypt.random-numbers, as I deem it irrelevant

Helmut Richter <hhr-m@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 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.

Date Subject Author
8/10/13 jim
8/10/13 namducnguyen
8/10/13 namducnguyen
8/10/13 Sandy
8/10/13 namducnguyen
8/10/13 Sandy
8/10/13 namducnguyen
8/10/13 Sandy
8/10/13 Bart Goddard
8/10/13 Peter Percival
8/10/13 Bart Goddard
8/11/13 Peter Percival
8/11/13 namducnguyen
8/11/13 Bart Goddard
8/11/13 Peter Percival
8/11/13 fom
8/10/13 antani
8/10/13 Bart Goddard
8/10/13 namducnguyen
8/10/13 Bart Goddard
8/10/13 namducnguyen
8/10/13 Bart Goddard
8/10/13 namducnguyen
8/11/13 Peter Percival
8/11/13 namducnguyen
8/10/13 namducnguyen
8/11/13 Peter Percival
8/11/13 namducnguyen
8/11/13 Peter Percival
8/10/13 Virgil
8/10/13 Peter Percival
8/10/13 rossum
8/10/13 John
8/10/13 Helmut Richter
8/10/13 Helmut Richter
8/19/13 Phil Carmody
8/10/13 antani
8/11/13 Helmut Richter
8/10/13 Sandy
8/10/13 namducnguyen
8/11/13 Sandy
8/11/13 namducnguyen
8/11/13 Sandy
8/10/13 William Elliot
8/10/13 namducnguyen
8/10/13 William Elliot
8/11/13 namducnguyen
8/11/13 William Elliot
8/11/13 namducnguyen
8/11/13 William Elliot
8/11/13 namducnguyen
8/11/13 Sandy
8/11/13 namducnguyen
8/11/13 Sandy
8/11/13 namducnguyen
8/11/13 Sandy
8/11/13 namducnguyen
8/11/13 Sandy
8/11/13 namducnguyen
8/12/13 Sandy
8/12/13 Bart Goddard
8/13/13 Shmuel (Seymour J.) Metz
8/11/13 Sandy
8/19/13 Phil Carmody
8/11/13 Sandy
8/11/13 namducnguyen
8/11/13 Sandy
8/13/13 Shmuel (Seymour J.) Metz
8/11/13 Pubkeybreaker
8/11/13 Peter Percival
8/11/13 fom
8/11/13 Brian Q. Hutchings
8/12/13 namducnguyen
8/12/13 namducnguyen
8/12/13 Peter Percival
8/13/13 Shmuel (Seymour J.) Metz
8/12/13 Peter Percival
8/11/13 namducnguyen
8/11/13 namducnguyen
8/12/13 namducnguyen
8/12/13 Peter Percival
8/19/13 Phil Carmody