Free Republic
Browse · Search
News/Activism
Topics · Post Article

To: Virginia-American

I based my statement on this article.

http://www.finextra.com/fullstory.asp?id=12452


170 posted on 04/12/2006 9:00:39 PM PDT by Boiler Plate (Mom always said why be difficult, when with just a little more effort you can be impossible.)
[ Post Reply | Private Reply | To 166 | View Replies ]


To: Boiler Plate

The article presumes
that the extra knowledge
that would enable us to prove the R.H.
also would enable us to factor composite numbers.

Not unreasonable, but not established.


171 posted on 04/12/2006 9:15:53 PM PDT by Allan (*-O)):~{>)
[ Post Reply | Private Reply | To 170 | View Replies ]

To: Boiler Plate

Take it with a grain of salt. I think the authors are confusing factorizing with primality testing and proving.

Search the web for Miller-Rabin test (there are a number of good references)

Roughly speaking, there is an algorithm for testing for compositeness. Given N, and another number a, it can return either "N is composite", or "can't say whether N is prime or composite."

It can be proved that if N is in fact composite, then the odds are 3/4 that the algorithm will return "N is composite". So if we run the algorithm x times with x different values of a, and it reurns "can't say" each time, the odds that N is not prime are (1/4)^x; if x is large enough, people will call N a "probable prime".

The trick is actually proving that N is prime using this test. It can be proved that if every value of a less that the square root of N is tried, and the algorithm never says "N is composite", then N is in fact prime. But this is impractical for N's with hundreds of digits.

If the extended RH is true, then you only need to use values of a less than 2(ln N)^2, which is much more practical.

What this means is that if you can find a number that is composite, but passes the Miller-Rabin test for all values of a less than 2(ln N)^2, then you have disproved the ERH.

If the test comes back and says N is composite, this is true but it gives no hint as to what its prime factors are


172 posted on 04/12/2006 9:41:54 PM PDT by Virginia-American
[ Post Reply | Private Reply | To 170 | View Replies ]

Free Republic
Browse · Search
News/Activism
Topics · Post Article


FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson