## Re: [PrimeNumbers] Re: A Record Prime Factor by Pollard's "p

Expand Messages
• RE : Factoring. Two of the sites of most use for this sort of stuff are ; Will Edgington s page : http://www.garlic.com/~wedgingt/mersenne.html and Paul
Message 1 of 5 , Mar 5, 2001
RE : Factoring.

Two of the sites of most use for this sort of stuff are ;

Will Edgington's page : http://www.garlic.com/~wedgingt/mersenne.html

and

Paul Zimmerman's page : http://www.loria.fr/~zimmerma/records/ecmnet.html

In terms of the list of methods below, you;ve missed out the Quadratic Sieve,
which was the mainstay for a long time before NFS came along and is still used
in various forms. I've implemented at various times everything except NFS and
ECM (the maths is too difficult for me). I'm amazed that UBASIC provided such a
result - it can't possibly be as fast as specifically designed code. However, by
it's nature, there is always a chance at finding reaonably big factors.

With finding factors of Fermat numbers, there are even more methods available,
since the form of divisors is so restrictive : Leonid Durman and Tony Forbes
both have freely available software that hunts specifically for Fermat factors.

Joe McLean.

Subject: [PrimeNumbers] Re: A Record Prime Factor by Pollard's "p-1"
Author: Phil Carmody <fatphil@...> at Internet
Date: 05/03/01 01:45

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:
>
> p39=188879386195169498836498369376071664143
> p-1=2.3.13.47.101.813613.1174951.1766201.3026227.99836987
>
> 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
- NFS
- ECM
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.

Any takers?

Phil

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!
http://www.shopping.altavista.com

Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
The Prime Pages : http://www.primepages.org

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
• ... Sieve, ... used Indeed, it s still doing sterling service and is probably the method of choice for general integers in the range 50-110 digits. I have
Message 2 of 5 , Mar 5, 2001
> In terms of the list of methods below, you;ve missed out the Quadratic
Sieve,
> which was the mainstay for a long time before NFS came along and is still
used

Indeed, it's still doing sterling service and is probably the method of
choice for general integers in the range 50-110 digits. I have several QS
jobs running right now.

At the moment, GNFS takes over for about 100-160 digits whereas SNFS will
handle special integers up to around 240 digits.

Finding small factors (8 - 30 digits say) of large integers is best done
with ECM; smaller factors are best found by trial division (<5 digits or so)
and Pollard rho for the intervening range.

Another good algorithm for factoring small integers, up to 25 digits say, is
SQFOF. Such a tool comes in handy at times.

> - Continued Fractions

Personally, I'd drop this one. It has long been superseded by QS.

Paul
• ... Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I d counciously forgotten about NFS. ... In the words of my Finnish teacher you can t even pronounce
Message 3 of 5 , Mar 5, 2001
On Mon, 05 March 2001, Paul Leyland wrote:
> > In terms of the list of methods below, you;ve missed out the Quadratic
> Sieve,
> > which was the mainstay for a long time before NFS came along and is still
> used

Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I'd counciously forgotten about NFS.

> Another good algorithm for factoring small integers, up to 25 digits say, is
> SQFOF. Such a tool comes in handy at times.

In the words of my Finnish teacher "you can't even pronounce it".
(actually it sounds like an insult!)
I've never heard of it, care to elaborate?

> > - Continued Fractions
>
> Personally, I'd drop this one. It has long been superseded by QS.

My source is Knuth, ACP vol 2 - SNA, alone. Knuth waxes lyrical about it. He makes it sound of great historical importance.
I'm not qualified to even sneeze in the presence of QS. Do I see a volunteer? (quick - everyone else step back 1 pace :-) )

Does anyone have _any_ information on "Valles two-thirds algorithm"? I know it _was_ on mathworld, but that was when mathworld was still available.

Phil

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!
http://www.shopping.altavista.com
• ... Implementing NFS from scratch is somewhat non-trivial. I d estimate about a year s work to get something worthwhile. QS, on the other hand, is rather
Message 4 of 5 , Mar 5, 2001
> Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I'd

Implementing NFS from scratch is somewhat non-trivial. I'd estimate about a
year's work to get something worthwhile. QS, on the other hand, is rather
easier --- especially as several implementations are available as source
code.

> > Another good algorithm for factoring small integers, up to 25 digits
say, is
> > SQFOF. Such a tool comes in handy at times.
>
> In the words of my Finnish teacher "you can't even pronounce it".
> (actually it sounds like an insult!)
> I've never heard of it, care to elaborate?

Perhaps you've never heard of it, at least in part, because I didn't spell
it properly! Try SQUFOF, aka
Daniel Shanks' "Square Forms Factorization" algorithm. It finds factors of N
in about (logN)^0.25 and so is much faster than trial division which is
(logN)^0.5. Like CFRAC, it calculates the continued fraction expansion of
sqrt(N), but doesn't use a factor base but, rather looks for a square
directly. It's this last difference than makes SQUFOF an exponential
algorithm and CFRAC subexponential. OTOH, it's very fast for relatively
small integers.

If memory serves, and I haven't looked for a *long* time, there's an
implementation of SQUFOF in the good old RSA-129 version of the MPQS siever
still to be found at ftp://ftp.ox.ac.uk/pub/math/ The double large prime
version of MPQS requires the factorization of large numbers of relatively
small integers and SQUFOF ruled supreme in this role for several years.
These days, we tend to use ECM with small parameters but SQUFOF is still
competitive.

> > > - Continued Fractions
> >
> > Personally, I'd drop this one. It has long been superseded by QS.
>
> My source is Knuth, ACP vol 2 - SNA, alone. Knuth waxes
> lyrical about it. He makes it sound of great historical importance.

It is indeed of great historical importance, as is Fermat's method.
Nonetheless, both are quite outdated now. Certainly implement it if you
want to do so, but don't expect it to be competitive.

Paul
• This has turned into a quite fun day (sad sad man that I am - sue me!) http://www.math.niu.edu/~rusin/known-math/index/11Y05.html Seems to be a fairly good
Message 5 of 5 , Mar 5, 2001
This has turned into a quite fun day (sad sad man that I am - sue me!)

http://www.math.niu.edu/~rusin/known-math/index/11Y05.html

Seems to be a fairly good resource after the non-existant one.

(Hmmm, does anyone have a copy of Weisstein? I'm thinking nefarious thougts here...)

About 6 months ago I found some ultra-lucid p-1, p+1, and rho source code on the internet, I even mailed the author a few hints on how he could optimise a couple of them. So - can I find that link again? Not for the life of me.

Phil

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!
http://www.shopping.altavista.com
Your message has been successfully submitted and would be delivered to recipients shortly.