Xref: utzoo sci.math:3503 sci.crypt:1040
Path: utzoo!mnetor!uunet!husc6!bbn!rochester!udel!princeton!phoenix!schoen
From: schoen@phoenix.Princeton.EDU (Eric R Schoenberg)
Newsgroups: sci.math,sci.crypt
Subject: Re: New Factorization Records
Message-ID: <2687@phoenix.Princeton.EDU>
Date: 27 Apr 88 06:07:20 GMT
References: <7535@boring.cwi.nl> <2675@phoenix.Princeton.EDU> <7537@boring.cwi.nl>
Reply-To: schoen@phoenix.Princeton.EDU (Eric R Schoenberg)
Organization: Princeton University, NJ
Lines: 54
Keywords: 4,6,8,9,10,12,14,15,16,18,...

In article <7537@boring.cwi.nl> walter@cwi.nl (Walter M. Lioen) writes:
>The method we used is known as the "Multiple Polynomial Quadratic Sieve"
>method (MPQS).
>
Thanks very much for the explanantion.  Is there a good book or article
you could recommend for an introduction to the subject of factorization of
large numbers?  I haven't studied the subject at all, but have always had
a passing interest in it. (I am about to finish my undergraduate degree in
math at Princeton, and have taken two semesters of Algebra -- just so you
can suggest something for my level.)  
   Does your MPQS method have anything to do with something I "discovered"
while doodling in class a few years ago:
  I observed that the two polynomials
	x^2 + x + 1    and    x^2 + x - 1
produce an awful lot of prime numbers, and that for the second one I think,
any non-prime number which is produced by plugging in an integer for x has
a common factor with some other number produced by plugging in a smaller
integer.  It has been a while since I looked into this, so I'm not sure how
far I checked it or if there were any exceptions.  Is there some theory
behind this?

x	x^2 + x - 1

1	1
2	5
3	11
4	19
5	29
6	41
7	55 = 5 * 11
8	71
9	89
10	109
11	131
12	155 = 5 * 31
13	181
14	209 = 11 * 19
...

Not all the numbers have factors which are actually numbers produced by
the polynomial.  For example
43	1891 = 31 * 61
But notice that 31 has already been a factor of one of the numbers (x=12).

I know that it has been proven that x^2 + x + 41 will produce the longest
consecutive string of primes, but is there some general theorem about the
factors of non-primes generated by a polynomial?  My hunch is that there must
be, otherwise you wouldn't be having such success at factoring those large
numbers.  As I said, I am a novice at this and any helpful hints would be
appreciated.

Thanks,

Randy Schoenberg