The Math Forum

Search All of the Math Forum:

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

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

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

Topic: Largest primeproduct with 2 as factor?
Replies: 19   Last Post: Aug 16, 2007 1:06 PM

Advanced Search

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

Posts: 1,683
Registered: 2/12/07
Re: Largest primeproduct with 2 as factor?
Posted: Aug 16, 2007 11:48 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply wrote:

> Is the computional effort for primality test for x bigger or less than
> checking that a composit only have two factors x*2?

I do not understand what you are asking. Please clairify.
Modern algorithms check for primaility by first:

(1) Checking for small prime factors
(2) Performing a probable prime test of some kind
(3) Then proceeds to a full primality proof.

The AKS prime proving algorithms runs in time no worse than a
constant multiple of (log N)^6 where N is the number you are
The multiple is machine and implementation dependent.

There is a random version that runs in time O( (log N)^4)

The cyclotomy primality test runs in time O( (log N)^ logloglog N)

May I suggest that you read a book on this subject? I can recommend a
of good ones.

You might start with:

H. Riesel Prime Numbers and Computer Methods for Factorization

The math in this book is well within the understanding of a good high

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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.