- 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.

______________________________ Reply Separator _________________________________

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/ > 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- On Mon, 05 March 2001, Paul Leyland wrote:
> > In terms of the list of methods below, you;ve missed out the Quadratic

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

> Sieve,

> > which was the mainstay for a long time before NFS came along and is still

> used

> Another good algorithm for factoring small integers, up to 25 digits say, is

In the words of my Finnish teacher "you can't even pronounce it".

> SQFOF. Such a tool comes in handy at times.

(actually it sounds like an insult!)

I've never heard of it, care to elaborate?

> > - Continued Fractions

My source is Knuth, ACP vol 2 - SNA, alone. Knuth waxes lyrical about it. He makes it sound of great historical importance.

>

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

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 > Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I'd

Implementing NFS from scratch is somewhat non-trivial. I'd estimate about a

> counciously forgotten about NFS.

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.

Perhaps you've never heard of it, at least in part, because I didn't spell

>

> 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?

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

It is indeed of great historical importance, as is Fermat's method.

> >

> > 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.

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 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