- View SourceHistory: In the olden days, factorization of large integers

required critical judgement. One had to decide when to give

up on an elliptic-curve method (ECM) in favour of a self-

initializing quadratic sieve (SIQS) or a number-field sieve

that might be special (SNFS) or general (GNFS).

Automated choice: Then a benign and skilful programmer, Ben

Buhrow, automated much of this process, for the benefit of

users who care more about results than methods. With

unwonted modesty, Ben called his package "yet another

factoring utility" (YAFU). He did such a good job that

nowadays many users may avoid learning both the principles

behind the methods of factorization and also the criteria

for choosing between those methods.

Caveat: There remain two areas where critical thought is

advisable: algebraic factorization and polynomial selection.

Practice: Here are some exercises where wetware helps. I

have tried to grade them, starting with easy pencil-and-

paper mathematics and ending with something approaching

state-of-the-art factorization.

Definition: Let F(n) = ((5^n-9)/4)^2-5 for integer n > 0.

Exercise 1: For even n > 2, prove that F(n) is composite.

Exercise 2: For odd n > 1, prove that F(n)/4 is composite.

Exercise 3: For k > 1, prove that F(3*k) has at least 4 odd

prime divisors.

Exercise 4: Factorize F(6) = 15241211 completely, by hand.

Exercise 5: Find the complete factorization of F(n) for at

least one odd integer n > 250.

Exercise 6: Find the complete factorization of F(n) for at

least one even integer n > 600.

Exercise 7: Factorize F(263) completely.

Exercise 9: Factorize F(265) completely.

Comments: Exercises 1 to 4 require only pencil and paper.

Exercises 5 and 6 may be solved quickly, using OpenPFGW.

Exercise 7 and 8 are more demanding and involve informed

choices between ECM, SNFS and GNFS.

David - View Source
---In primenumbers@yahoogroups.com, <thefatphil@...> wrote:

> You only chose that target after

> the arrow had landed, I'm sure.It happened thus:

1) I determined to factorize F(n)=((n^2-9)/4)^2-5 for

n <= 300, completely. As later shown in "factordb", I succeeded.2) Meanwhile I ran OpenPFGW on n in [301,600], hoping for a

quick outlier and found none.3) I estimated the probability of an easily discoverable

completely factorization for n>600 and found it to be small.4) Recalling how I had once been caught out before by

a "probably no more" heuristic, I set a lone process running on

n in [601, 10000] so as not to be caught out again by Jens.5) When I later looked and pfgw.log, it had found a hit at

n=608.So yes, Phil, you are quite correct that the puzzle was set

after this finding. However the heuristic that I gave was

made prior to my discovery, else I would not have said that

I was surprised.The point that you are making (I think) is that I do such

expsriments often and only notice when the result is unexpected.

I don't tell folk about all the boring times when a negative

heuristic is borne out by a null result. That is the selectioneffect.

David

`(guilty of not boring folk with what is routine)`