| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
While they last, grab a copy of AURORA::FACTOR.EXE. The program is an implementation of the "Continued Fraction" algorithm described in Knuth section 4.5.4. It is rather straightforward to use -- you type in a number, it tells you the factors. There is, however, the following caveat: It is possible (though extremely rare) that the program will output some number "N" as a factor, but N will be composite. In all cases, the listed factors will of course multiply out to the input number, but don't bet the mortgage that they're all prime. If you type in "N" and the program spits "N" back, that means that the program thinks N is prime. Again, this is usually (but not always) true.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 73.1 | CASTOR::[RABAHY] | Thu May 31 1984 17:12 | 2 | ||
An example of a composite number which is itself returned by the program is 524287 = 2**20-1. Have I reached some boundary condition? | |||||
| 73.2 | AURORA::HALLYB | Sat Jun 02 1984 23:12 | 13 | ||
First, the number 524287 is not 2^20 - 1; it's 2^19 - 1, and IS prime (according to Mersenne...) However, there are cases where composite numbers (especially Carmichael numbers) are returned as unfactorable. The problem is that this algorithm fails for pseudoprimes. It's not so much a boundary case as the nature of the beast. About all I can do is guarantee some limit (currently 292,682) below which all numbers are indeed prime. If this is not satisfactory then you're out of luck. I'm satisfied with the algorithm because I have a specific need, and don't mind an occasional pseudoprime. John | |||||