Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspxNumber theory
is, roughly speaking, the study of properties of integers. Often a
problem which is easy for real numbers, such as factoring or linear
programming, seems to be considerably more difficult when restricted to
integers (in fact, integeren-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875) Developing for Developers Modular arithmetic and primality testing | unemployment officehttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#9759772Tue, 16 Jun 2009 11:00:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:9759772 Developing for Developers Modular arithmetic and primality testing | unemployment office<p>PingBack from <a rel="nofollow" target="_new" href="http://unemploymentofficeresource.info/story.php?id=8432">http://unemploymentofficeresource.info/story.php?id=8432</a></p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=9759772" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#4844048Sun, 09 Sep 2007 16:42:32 GMT91d46819-8472-40ad-a661-2c78acb4018c:4844048silvia<p>my questions is how determinate the number of Carmichael numbers in numbers de 2^k bits</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=4844048" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#462482Thu, 08 Sep 2005 20:13:53 GMT91d46819-8472-40ad-a661-2c78acb4018c:462482MSDNArchiveThanks 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.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=462482" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#462444Thu, 08 Sep 2005 18:39:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:462444AndyMy 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.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=462444" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#462400Thu, 08 Sep 2005 16:45:42 GMT91d46819-8472-40ad-a661-2c78acb4018c:462400AndyHere is a paper that shows another way of determining primality and shows that primality is in P:
<br><a rel="nofollow" target="_new" href="http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf">http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf</a>
<br>
<br>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.
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=462400" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#462088Wed, 07 Sep 2005 23:03:21 GMT91d46819-8472-40ad-a661-2c78acb4018c:462088MSDNArchiveThanks 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.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=462088" width="1" height="1">re: Modular arithmetic and primality testinghttp://blogs.msdn.com/b/devdev/archive/2005/09/07/462070.aspx#462085Wed, 07 Sep 2005 22:57:51 GMT91d46819-8472-40ad-a661-2c78acb4018c:462085Douglas McCleanIsn'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.
<br>
<br>
<br>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?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=462085" width="1" height="1">