2012-09-09  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (prime_p): Compute redcify from multiples of `one' instead
	of directly.
	(mod2): Fix typo.

	* Makefile (primes.h): Up primes limit to 5000.

	* make-prime-list.c (output_primes): Put diff8 entries into P macro.
	* factor.c: Corresponding changes.

	* factor.c (factor): Remove `alg' argument.  Callers changed.
	(add_ssaaaa): Provide default.
	(factor_clz_tab): When asked for, provide table for longlong.h.
	(flag_prove_primality): Set by `-w' (for `weak' prime testing).
	(prime_p, prime2_p, mp_prime_p): Honour flag_prove_primality.

2012-09-08  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (powm2, mulredc2): Return low result word.  Callers changed.
	(read_item): Rewrite to use dynamic allocation.
	(main): Make basic allocation for read_item.

2012-09-07  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c: Merge GMP factoring code (gmp/demos/factorize.c).
	(div_smallq): New name for div1.

2012-09-06  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c: Remove debug inside #if 0 ... #endif.

2012-09-06  Jim Meyering  <jim@meyering.net>

	* ourseq.c (incr): Don't omit trailing NUL when incrementing.

2012-09-06  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c: Clean up many things, remove unused code, add comments.
	(prime_p): Remove non-Lucas code.

2012-09-06  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (factor_using_pollard_rho2): Handle unlikely case of
	pollard rho finding a large factor, exceeding one word.

2012-09-06  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (factor_using_pollard_rho2): New function, still rudimentary.
	(submod2): New macro.
	(mod2): New function.
	(gcd2_odd): Slightly change interface, also support even arguments.
	(factor_using_division): Rewrite 1-word code.
	(make-prime-list): Emit 8-step diff list using P8 macro.
	(factor_using_pollard_rho): Minor clean up.

2012-09-05  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (factor_using_squfof): Use factor_using_pollard_rho for
	one-word composites.
	(print_uintmaxes): Rewrite using printf.
	(strto2uintmax): Use UNLIKELY for several conditions.
	(primes_ptab, primes_dtab): Make const.
	(gcd2_odd): New function (untested).

2012-09-02  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (millerrabin2): Fix typo.
	(mulredc2): Fix typos.

2012-09-02  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (MAX_NFACTS): Increase to 26 (for 128 bits).
	(addmod2): Typo fix.
	(mulredc2): More typos.
	(prime2_p): Lucas test: special case for dividing by the (p-1)
	factor 2. Take into account any two-limb factor of (p-1).

2012-09-02  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (powm2): Copy result value to intended place (code
	might still be non-functional).
	(lsh2): Make it actually work.
	(div21): New macro.
	(prime2_p): Use div21, not divexact_21 since the latter is undefined
	for even divisors.

	* ourseq.c: Rewrite to avoid strlen exercise.

	* factor.c (mod): Remove.
	(redcify): Use udiv_qrnnd instead of removed mod.
	(LIKELY): New macro.
	(factor_using_division): Use LIKELY.
	(prime2_p): Fix some typos (code still non-functional).

	* Makefile (check): Add tests for numbers >= 2^64.

2012-09-02  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (struct factors): Hold a one two-word factor.
	(lsh2): New macro.
	(count_trailing_zeros): New macro.
	(addmod2): New macro.
	(divexact_21): New macro.
	(redcify2): New macro.
	(factor_insert_large): New function.
	(factor_using_division): Handle double-word inputs.
	(mulredc2): New function.
	(powm2): New function.
	(millerrabin2): New function.
	(prime2_p): New function.
	(factor_using_squfof): Handle double-word inputs. Also added
	quotient statistics.
	(factor): Handle double-word inputs.
	(factor_one): Handle double-word inputs. Output double-word prime
	factor, if any.
	(main): Output squfof statistics (if enabled).

2012-08-31  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (primes_ptab): Delete sentinel.
	(factor_using_division): Arrange loop to read primes_ptab at start
	of each iteration.
	(div1): New macro, extracted from factor_using_squfof.
	(factor_using_squfof): Use it.
	Fix trivial-factor bug, affecting n = 36914291 and multiplier 21.
	Stricter limit for multiplier size, affecting n = 37243139 and
	multiplier 105.

2012-08-31  Torbjorn Granlund  <tege@gmplib.org>

	* Makefile (primes.h): Up primes limit to 4000.

2012-08-29  Torbjorn Granlund  <tege@gmplib.org>

	* Makefile (check): Depend on ourseq.  Add many more tests, and use the
	widely available shasum instead of md5.
	* tests: New directory with new shasum files.

	* ourseq.c: New program for running tests.

	* factor.c (factor_using_division): Get rid of "non-hairy" variant.

	* longlong.h: Import from GMP.
	* factor.c: Pull in longlong.h by default.

2012-08-29  Niels Mller  <nisse@lysator.liu.se>

	* Makefile (check): Pass numbers to factor on stdin.

2012-08-28  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (factor): Clear nfactors field earlier, to make it always
	initialised.
	(strto2uintmax): New function.
	(print_uintmaxes): New function.
	(factor_one): Use new functions, but abort when high word != 0 since
	factoring functions are not yet ready.

2012-08-28  Niels Mller  <nisse@lysator.liu.se>

	* Makefile (check): New target.
	(test-1.md5, test-2.md5): MD5 sums of expected output.

	* factor.c (factor_one): New function, extracted from main.
	Process one argument.
	(read_item): New function.
	(main): Use factor_one. If there are no command line arguments,
	read numbers to factor from stdin.

2012-08-28  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (factor_insert_multiplicity): Avoid out-of-bounds indexing.
	(factor_using_squfof): Handle small quotients in continued fractions
	divisions using division-free code.

2012-08-26  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c: Improve file comment.
	(redc, cmp_uintmax): Remove unused functions.

2012-08-22  Torbjorn Granlund  <tege@gmplib.org>

	* Makefile: Handle make-prime-list, generate primes.h.

	* make-prime-list.c (output_primes): Make output proper C.
	Fix typo in last change.

	* factor.c (prime_p): Make Lucas test work again by comparing powm
	return value to redcified `one', not plain 1.
	(prime_diff): Remove.  Use primes_ptab everywhere.
	(alg): New global variable.
	(prime_p): Use 'alg' for factoring of n-1.
	(factor_using_pollard_rho): Remove a redundant gcd call.
	(prime_p): Add a cast to allow hug primes list.

2012-08-21  Niels Mller  <nisse@lysator.liu.se>

	* make-prime-list.c: New program to generate prime tables.

	* factor.c (factor_insert_multiplicity): Generalize factor_insert
	to take multiplicity argument.
	(factor_insert): New macro, passing multiplicity = 1.
	(factor_using_squfof): Adapted the square case to new work with
	factor_insert.

2012-08-20  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (prime_p): Use prime bases for the benefit of both Lucas and
	Miller-Rabin.  Avoid re-running powm for repeated factors.
	(factor_insert): New function.  Use it everywhere.

2012-08-19  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (prime_p): Implement variant with Lucas prime test.

2012-08-19  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (factor_using_squfof): Complete factorization, in the
	case that the input is a square.
	(factor_using_squfof): Support for extra multipliers.

2012-08-19  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (struct factors): New type.
	(factor, factor_using_*): Accept factors parameter.
	(main): Print factors here, not in factors.

	* factor.c (prime_p): New name for probab_prime_p, now supposedly
	deterministic for numbers < 2^64.  Callers changed.

2012-08-18  Niels Mller  <nisse@lysator.liu.se>

	* factor.c (probab_prime_p): 1 is not a prime.
	(factor_using_pollard_rho): Assert that a < n. Deleted workaround
	for probab_prime_p (1) bug. Applies to both redc and non-redc
	versions.
	(factor_using_squfof): New function, partly working.
	(main): Added -s option, selecting the squfof algorithm.

	(factor_using_squfof): Generate full factorization. Attempt at fix
	for case n = 1 (mod 4).
	(is_square): Use test suggested by Cohen. For square inputs,
	return the square root.
	(factor_using_squfof): Use is_square for the square test in the
	loop.

	(factor_using_squfof): Fixed handling of the queue.

2012-08-18  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c (factor_using_pollard_rho): Move inverse computation
	inside outer loop, to make ni and n match.

	* factor.c (factor_using_pollard_rho): Supply redc variant.

2012-08-17  Torbjorn Granlund  <tege@gmplib.org>

	* factor.c: New file, by Niels Mller and Torbjorn Granlund, with code
	also from GNU MP by the same authors.
