Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Phil Carmody

Posts: 2,219
Registered: 12/7/04
Re: Combining Primes
Posted: Aug 19, 2013 1:07 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read Combining Primes
jim
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
Sandy
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
Sandy
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
Sandy
8/10/13
Read Re: Combining Primes
Bart Goddard
8/10/13
Read Re: Combining Primes
Peter Percival
8/10/13
Read Re: Combining Primes
Bart Goddard
8/11/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Bart Goddard
8/11/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
fom
8/10/13
Read Re: Combining Primes
antani
8/10/13
Read Re: Combining Primes
Bart Goddard
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
Bart Goddard
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
Bart Goddard
8/10/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Peter Percival
8/10/13
Read Re: Combining Primes
Virgil
8/10/13
Read Re: Combining Primes
Peter Percival
8/10/13
Read Re: Combining Primes
rossum
8/10/13
Read Re: Combining Primes
John
8/10/13
Read Re: Combining Primes
Helmut Richter
8/10/13
Read Re: Combining Primes
Helmut Richter
8/19/13
Read Re: Combining Primes
Phil Carmody
8/10/13
Read Re: Combining Primes
antani
8/11/13
Read Re: Combining Primes
Helmut Richter
8/10/13
Read Re: Combining Primes
Sandy
8/10/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/10/13
Read Re: Combining Primes
William Elliot
8/10/13
Read Re: Combining Primes
namducnguyen
8/10/13
Read Re: Combining Primes
William Elliot
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
William Elliot
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
William Elliot
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/12/13
Read Re: Combining Primes
Sandy
8/12/13
Read Re: Combining Primes
Bart Goddard
8/13/13
Read Re: Combining Primes
Shmuel (Seymour J.) Metz
8/11/13
Read Re: Combining Primes
Sandy
8/19/13
Read Re: Combining Primes
Phil Carmody
8/11/13
Read Re: Combining Primes
Sandy
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
Sandy
8/13/13
Read Re: Combining Primes
Shmuel (Seymour J.) Metz
8/11/13
Read Re: Combining Primes
Pubkeybreaker
8/11/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
fom
8/11/13
Read Re: Combining Primes
Brian Q. Hutchings
8/12/13
Read Re: Combining Primes
namducnguyen
8/12/13
Read Re: Combining Primes
namducnguyen
8/12/13
Read Re: Combining Primes
Peter Percival
8/13/13
Read Re: Combining Primes
Shmuel (Seymour J.) Metz
8/12/13
Read Re: Combining Primes
Peter Percival
8/11/13
Read Re: Combining Primes
namducnguyen
8/11/13
Read Re: Combining Primes
namducnguyen
8/12/13
Read Re: Combining Primes
namducnguyen
8/12/13
Read Re: Combining Primes
Peter Percival
8/19/13
Read Re: Combining Primes
Phil Carmody

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.