483Re: A Record Prime Factor by Pollard's "p-1" method
- Mar 5, 2001
On Sun, 04 March 2001, Andy Steward wrote:
[On the NMBRTHRY mailing list]
> Early on 3rd March 2001, my own Ubasic "p-1" code found the following
> factor of 922^47-1:
> I therefore claim the world record factor found by this method (unless
> any of you know better).
Well done, Andy.
Is UBasic as fast for this kind of job as C would be with one of the standard bignum packages. Or a dedicated number-theoretic package, such as pari or LiDIA?
I was looking on the prime pages, for some info on the p-1 factoring method, and I noticed that there is no "Factoring into primes" section on the prime pages. My favourite search engine quickly pointed me in the direction of Wolfram/Eric Weisstein's Mathworld, several dead links, and some source code in an unknown language... So perhaps we could put our heads together to create the kernel of a new prime pages page of factoring methods? As far as my memory serves me (traditionally very poorly), it would be nice to get information on the following.
- Trial division
- Pollard p-1
- Pollard p+1
- Continued Fractions
- Pollard Rho
Note - I haven't got a clue what any of the above are (apart from one), I'm just parroting.
I do have Knuth, so I am prepared to put my reading spec's on to learn a few of the above, but that still leaves half of them for others.
Mathematics should not have to involve martyrdom;
Support Eric Weisstein, see http://mathworld.wolfram.com
Find the best deals on the web at AltaVista Shopping!