Modular arithmetic and primality testing

Developing for Developers Modular arithmetic and primality testing | unemployment office

Tue, 16 Jun 2009 11:00:04 GMT

PingBack from http://unemploymentofficeresource.info/story.php?id=8432

re: Modular arithmetic and primality testing

silvia — Sun, 09 Sep 2007 16:42:32 GMT

my questions is how determinate the number of Carmichael numbers in numbers de 2^k bits

re: Modular arithmetic and primality testing

MSDNArchive — Thu, 08 Sep 2005 20:13:53 GMT

Thanks for the link, Andy. I tried to stay away from the PRIMES in P result, because it requires quite a bit more explanation and background, and because the probabilistic algorithms are more practical and are the ones actually used in practice. It is a very important theoretical result though and I apologise for neglecting to mention it. If there were a result showing that factoring is in P, or even in BPP, I'm sure it would get a lot of attention, regardless of how practical it actually is.

re: Modular arithmetic and primality testing

Andy — Thu, 08 Sep 2005 18:39:17 GMT

My bad. The paper I linked above for proving primality can be determined in P was what he was talking about and not factoring primes. I keep hoping for the prime factoring thing though because so many people I know have been working on it in their spare time.

re: Modular arithmetic and primality testing

Andy — Thu, 08 Sep 2005 16:45:42 GMT

Here is a paper that shows another way of determining primality and shows that primality is in P:
http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf

I think a while back I saw that some researchers were going to publish a paper showing that factoring of primes was in P as well. I could be wrong on that though but I did contact the Proff. that I heard it from and I asked him for a link to the paper or a source if it is indeed true. I post the link in a comment here if he comes through with it.

re: Modular arithmetic and primality testing

MSDNArchive — Wed, 07 Sep 2005 23:03:21 GMT

Thanks for the comments and the correction, Douglas. The main part of this algorithm is used to test a number for primality, rather than to choose one. The candidate primes are chosen at random, and so are entirely unpredictable (except for their number of bits). In practice, however, most systems can't afford to generate enough truly random bits, and so they'll use some random seed bits in combination with a pseudorandom number generator. Also, just as passwords are often validated with automatic password crackers, many candidate semiprimes are rejected because they happen to be of a special form that can be easily factored by known algorithms. This somewhat affects the final choice of prime factors.

re: Modular arithmetic and primality testing

Douglas McClean — Wed, 07 Sep 2005 22:57:51 GMT

Isn't the chance of erroneously claiming that p is prime (1/4)^T? I ask because 1 - (1/4)^T quickly approaches 1 as T increases.

Another question is this: how are the primes generated by this algorithm distributed over the primes in general? Is it thought that factoring large semi-primes might be simplified by the knowledge that the prime factors were generated by this or a similar algorithm?