| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 546.1 | | ENGINE::ROTH | | Wed Jul 30 1986 09:24 | 8 |
| A recent book published by Birkhauser by Hans Riesel on prime numbers
may be what you are looking for. I don't have a copy in my office, but
you could call Birkhauser in Boston about the book; it includes many
routines in PASCAL.
Of course, Knuth has lots of info too.
- Jim
|
| 546.2 | 'Scientific Pascal' | EAGLE7::BEST | R. D. Best, 32 bit sys. arch. & A.D., VAXBI | Wed Aug 06 1986 18:32 | 24 |
| < Note 546.0 by SHEILA::PUCKETT "Very Asian Gold Box" >
-< ?? Division/factoring algorithms ?? >-
Has anyone got network-readable descriptions, or book references,
to algorithms for:
1) fast multiprecision integer operations (esp. division)
2) factoring (pollard rho, quadratic sieve etc.)
Any light shed on these would be appreciated.
- Giles
> A book reference with Pascal sources:
> ( but I can't say how fast they are )
> re: multiprecision integer ops (I'm not sure about division)
> 'Scientific Pascal' by Harley Flanders, Reston Publishing Co.
> Available in the DEC library.
> /R Best
|
| 546.3 | Maybe it can be dug out of the library | MODEL::YARBROUGH | | Tue Sep 30 1986 15:50 | 3 |
| The Pollard Rho algorithm is used in MAPLE for factoring large integers.
The MAPLE manual only describes it by name, though. A simpler algorithm
(which fails for large factors) is also available.
|
| 546.4 | Pollard | TAV02::NITSAN | Nitsan Duvdevani, Digital Israel | Thu Oct 09 1986 10:01 | 13 |
| -- About the Pollard algorithm, if I remember correctly, it goes
something like this:
Statisticly, when you have a set of k items, it takes about sqrt(k) random
choices to repeat the same choice with high probability. Assuming you have
a number n = p*q, then it takes about sqrt(p) random choices to get two
values with the same residue mod p. So choose random pairs and test the
gcd between their difference and n.
This is just the basic idea. The algorithm itself has more points of
optimization etc.
Nitsan
|