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 » Education » math-teach

Topic: An Interesting Way To Introduce Prime Numbers
Replies: 1   Last Post: Dec 28, 2012 10:14 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
kirby urner

Posts: 1,660
Registered: 11/29/05
Re: An Interesting Way To Introduce Prime Numbers
Posted: Dec 28, 2012 10:14 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Fri, Dec 28, 2012 at 10:35 AM, Ken Abbott <abbottsystems@gmail.com> wrote:
> http://www.math-math.com/2012/12/making-prime-numbers.html

Yes, well described.

In practice it's not always easy to determine which prime factors make
N, so one successively tries those on file.

Like when you asked about 15, 2 doesn't work so we know to try 3, but
sometimes it's not obvious with which odd prime to start, so one plows
through the ones on file in succession, up to sqrt(N), at which point
one should have found one if there is one. If not, add to the stash
and proceed.

Put another way, factoring is a non-trivial problem and once the
integers get big enough, we run out of memory and/or time given
present capacity.

Which is not to denigrate your algorithm. The algorithms giving us
primes of many thousands of digits tend to shoot for "probable primes"
which means very very unlikely to be composite. Composites sneak
through the filters.

Like remember the Carmichael numbers: they pass all the Fermat tests
suggesting they're prime, but they're not:

http://crypto.stanford.edu/pbc/notes/numbertheory/carmichael.xhtml
http://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.xhtml

Your method has often been implemented and is well respected. It
requires a growing stash of primes on file.

Kirby



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.