wheel_tuner.py

I really hesitated to include any printed output that wasn't a warning for an invalid setting. However, maybe even more valuable than the ultimate factorization output, with FACTOR_FINDER method, is the running list of smooth numbers successfully identified in the sieve. Based on empirical tests (or theory that isn't yet apparent to me), the script wheel_tuner.py in the project root can be used with this intermediate output, of a list of smooth number, to better tune the application of wheel factorization.

Full Changelog: v6.6.0...v6.7.0

sha1sum results:
c8fcbc1c2d0c3cf011961a2383b1d03ce2f74a8b FindAFactor-6.7.0-cp310-cp310-manylinux_2_35_x86_64.whl
f960cb97c6bdd3da066f87251986a2fbfed895d5 FindAFactor-6.7.0-cp312-cp312-manylinux_2_39_x86_64.whl
cb6d29e7ec2495f860fc0ceda65fc688ca15ce47 FindAFactor-6.7.0-cp312-cp312-win_amd64.whl
80072f46be02a1a32192d455dc35d0be01b3f876 FindAFactor-6.7.0-cp313-cp313-macosx_14_0_arm64.whl
1bbc58a9d9f2b8cce344793a8f15e4fbc967415d FindAFactor-6.7.0-cp313-cp313-macosx_15_0_arm64.whl
017942d818f58ab56331e17764ae5eb34d4683a6 FindAFactor-6.7.0-cp38-cp38-manylinux_2_31_x86_64.whl
4c4d85167e4d8ed1299135948808162c4f155035 findafactor-6.7.0.tar.gz

wheel_primes_excluded argument

This release adds a wheel_primes_excluded list argument (and environment variable) that allows users to selectively exclude specific prime numbers from wheel factorization when using FACTOR_FINDER method. (All primes up to wheel_factorization_level or gear_factorization_level will be applied during wheel factorization except for those in the exclusionary list argument.)

The reason FindAFactor previously applied wheel factorization to all primes up to the specified level not in the factor base is that other popular reference implementations of GitHub never produced such smooth numbers: it turns out, this is because the top hits on Google for "github quadratic sieve" are almost all copied from the same reference implementation that is almost totally wrong, but there's a "cargo cult" that's grown up around this implementation because it happens to provide one example of a number being factored below the scale that even motivates quadratic sieve in a manner that's essentially a bad version of the original qimcifa, because "garbage-in, garbage-out" manages to correctly guess the number. (You have been warned.)

Full Changelog: v6.5.4...v6.6.0

sha1sum results:
102cc5a1040649aa13bda024dc8009df9a136579 FindAFactor-6.6.0-cp310-cp310-manylinux_2_35_x86_64.whl
1b7ecfd3a16f179535706e50b87d36043fa888aa FindAFactor-6.6.0-cp312-cp312-manylinux_2_39_x86_64.whl
5d35d911d6acb71387742ea308acec51c70566e0 FindAFactor-6.6.0-cp312-cp312-win_amd64.whl
bc6998d3a9e52e8313b9af873b132c96599e1338 FindAFactor-6.6.0-cp313-cp313-macosx_14_0_arm64.whl
6958ae3d4acbab440831176deb11b847c5f0ac49 FindAFactor-6.6.0-cp313-cp313-macosx_15_0_arm64.whl
21559f7337d11abd4da60a36f49a99cda84a4075 FindAFactor-6.6.0-cp38-cp38-manylinux_2_31_x86_64.whl
c9207a7e2eba3968971e90551d91b29758184080 findafactor-6.6.0.tar.gz

Nitpick

An exception message that should never occur has had its message amended. (If you ever encounter "Quadratic Sieve math is not self-consistent!" then our implementation of the math is wrong.) Also, range checks have been replaced with inequality checks in cases where, semantically, it should make no difference except in performance (and no difference is actually observed in tests).

Full Changelog: v6.5.3...v6.5.4

sha1sum results:
230c429935a2eac562128c534e6f9729152101e7 FindAFactor-6.5.4-cp310-cp310-manylinux_2_35_x86_64.whl
0393ced465194e7686d0834b787531d8f0cfa6aa FindAFactor-6.5.4-cp312-cp312-manylinux_2_39_x86_64.whl
8f9efbf15072d038d4945bf0f8ff1d74abe0a6a6 FindAFactor-6.5.4-cp312-cp312-win_amd64.whl
023075488f47a98f6f754e336598832fa1f3fe80 FindAFactor-6.5.4-cp313-cp313-macosx_14_0_arm64.whl
5a9a08d092c4fcf5eb1dd06a977acd9976ac439f FindAFactor-6.5.4-cp313-cp313-macosx_15_0_arm64.whl
d9dbd384f6ab2a8929f57f5406909af6862ef46d FindAFactor-6.5.4-cp38-cp38-manylinux_2_31_x86_64.whl
ae1e9980abd0f995a8c4fd41b9740e1a94558bf3 findafactor-6.5.4.tar.gz

v6.5.3

This release (only) optimizes trial division on polynomial residues. As for packaging, Mac 13 wheel builds broke today, as support ends for Mac 13 and homebrew within it as an environment. (It's been months, since Mac 13 was deprecated. The Qrack team always tries to support deprecated systems as long as we can hold out; in February, 2025, there's little point in trying to go back.)

Full Changelog: v6.5.2...v6.5.3

sha1sum results:
724120778b4c3f1bbcca5e3dc5634bc39b6ee293 FindAFactor-6.5.3-cp310-cp310-manylinux_2_35_x86_64.whl
9a9eff8b2685c848c7f5d0a01ff058752669ae3b FindAFactor-6.5.3-cp312-cp312-manylinux_2_39_x86_64.whl
380ce5b892b7c2939f0c69ab506c322b03b9fa41 FindAFactor-6.5.3-cp312-cp312-win_amd64.whl
b3c014b19ef78d95c4547ccde1d50d89453de256 FindAFactor-6.5.3-cp313-cp313-macosx_15_0_arm64.whl
3824eab33eb5b3e4daef5b2ace6018136a8368fa FindAFactor-6.5.3-cp38-cp38-manylinux_2_31_x86_64.whl
c38a2a4579eadd4c5a58af164157fdf033347ca7 findafactor-6.5.3.tar.gz

Optimize FACTOR_FINDER trial division

The release (only) makes an improvement in FACTOR_FINDER trial division efficiency for sieving smooth residues.

Full Changelog: v6.5.1...v6.5.2

sha1sum results:
2f7c6017c3c0f78059a06316a17ce42522e80967 FindAFactor-6.5.2-cp310-cp310-manylinux_2_35_x86_64.whl
51ebe8c222c683f720964e3212b44057433794b1 FindAFactor-6.5.2-cp312-cp312-manylinux_2_39_x86_64.whl
64cc36e4bb62a2381446b71dab513b2265d30b2b FindAFactor-6.5.2-cp312-cp312-win_amd64.whl
04cd03274c809d983f2dca026e34e304ba39dd67 FindAFactor-6.5.2-cp313-cp313-macosx_13_0_x86_64.whl
8b7aa39bb3f9618dbb4277f95bdda777c5b09e2e FindAFactor-6.5.2-cp313-cp313-macosx_14_0_arm64.whl
62dc3c0c59c66ae607fb703911a0811fb2352651 FindAFactor-6.5.2-cp313-cp313-macosx_15_0_arm64.whl
52f7b14350a43f2be26576cfcb3fafea46be7402 FindAFactor-6.5.2-cp38-cp38-manylinux_2_31_x86_64.whl
d604cbd49eb1520a242ded8fe94109ccbc937843 findafactor-6.5.2.tar.gz

Fix defaults and README

This was meant to go into v6.5.0: default arguments and the README have been correctly updated. (Default gear/wheel levels are 23/13.)

Full Changelog: v6.5.0...v6.5.1

sha1sum results:
886caee012391d4f1db69516c675b15bfdac3ad0 FindAFactor-6.5.1-cp310-cp310-manylinux_2_35_x86_64.whl
966b8048e86c1782f1929dd556b175ad83364653 FindAFactor-6.5.1-cp312-cp312-manylinux_2_39_x86_64.whl
3c7ab38e241a875d79c35ffaafeb14ef39de9e5f FindAFactor-6.5.1-cp312-cp312-win_amd64.whl
8f6462a80eb6a5b49d007b441bed0d71679c25b7 FindAFactor-6.5.1-cp313-cp313-macosx_13_0_x86_64.whl
b5b3077aa17f011a4506e3eed36f65e514dc8e9d FindAFactor-6.5.1-cp313-cp313-macosx_14_0_arm64.whl
d6c54e5f27ce909807123dc9eb690099d34f32dc FindAFactor-6.5.1-cp313-cp313-macosx_15_0_arm64.whl
fc37aa0dd73dd30187e6fb3694ac06d85a82c0d1 FindAFactor-6.5.1-cp38-cp38-manylinux_2_31_x86_64.whl
463aa361720e93afd9b4fa2cf8eb23578b9c4a52 findafactor-6.5.1.tar.gz

Wheel factorization to 17

Benchmarks reveal that 13 might no longer be a ceiling for the point of additional practical advantage with wheel factorization. Hence, we add wheels up to 17. (We might go another increment or two higher, ultimately, but the difference in overhead with each additional step is huge, probably tending somewhat like factorial, so we want to have support for just the highest case where we ever see practical advantage, or just one higher than that for completeness.)

Full Changelog: v6.4.3...v6.5.0

sha1sum results:
0c57078510ccbefbd2fcf0dfa1f4c8b41890e27d FindAFactor-6.5.0-cp310-cp310-manylinux_2_35_x86_64.whl
c3ca1a39b393c7462c6a0f7befe79c4e583dfa9e FindAFactor-6.5.0-cp312-cp312-manylinux_2_39_x86_64.whl
8203978c5492737e8bfaac96fee39ce09e819beb FindAFactor-6.5.0-cp312-cp312-win_amd64.whl
8652e19e73b455ff93f1a2101cc75bcb8f8975fe FindAFactor-6.5.0-cp313-cp313-macosx_13_0_x86_64.whl
ea9ea5af736d6fa2a075ee3cb682123d89156cc7 FindAFactor-6.5.0-cp313-cp313-macosx_14_0_arm64.whl
017d4760e912c1a0efabaccc8bf5470414969759 FindAFactor-6.5.0-cp313-cp313-macosx_15_0_arm64.whl
54ed2b316ca69e6a9841ab741f338ea9a2fec144 FindAFactor-6.5.0-cp38-cp38-manylinux_2_31_x86_64.whl
1b8cdbc2e6e4ad547faf85b87fb3d28b28f943f9 findafactor-6.5.0.tar.gz

Finishing touches

This release contains minor finishing touches (including minor bug fixes).

Full Changelog: v6.4.2...v6.4.3

sha1ums results:
883c01f4b0f46f26476327b3a33ddabb2dc958ce FindAFactor-6.4.3-cp310-cp310-manylinux_2_35_x86_64.whl
3797863860dc3b7482cbe79bde6a0c8567fe1a8a FindAFactor-6.4.3-cp312-cp312-manylinux_2_39_x86_64.whl
ff2864331ba71d14f5549571c9556c52692a177b FindAFactor-6.4.3-cp312-cp312-win_amd64.whl
03f200fc343189aeadbad67a8a6ffc33784c77e4 FindAFactor-6.4.3-cp313-cp313-macosx_13_0_x86_64.whl
6fa1ad69b96bf1021cce51ff76b67e81d01fd6cf FindAFactor-6.4.3-cp313-cp313-macosx_14_0_arm64.whl
7ec1d3bf6446b6b89d7eb7c920c48bbc6185d462 FindAFactor-6.4.3-cp313-cp313-macosx_15_0_arm64.whl
a8244110d089eeebe314c1b93f87e5ea7445695e FindAFactor-6.4.3-cp38-cp38-manylinux_2_31_x86_64.whl
19edddedd3dfceded7126fac73cd1eec0a51937a findafactor-6.4.3.tar.gz

Correctly scale batches for FACTOR_FINDER mode

This release calculates the first valid sieving element after wheel factorization in FACTOR_FINDER Quadratic Sieve mode, takes this as overall additive offset on all other work items, and multiplies just the batch number by the batch size. (Getting the order of operations right on wheel factorization interval scaling has always been the trickiest part, since the original development of PRIME_PROVER mode, as well.)

Full Changelog: v6.4.1...v6.4.2

sha1sum results:
44bffee0e3e215d686c4af364c254c824583d4ed FindAFactor-6.4.2-cp310-cp310-manylinux_2_35_x86_64.whl
f8387986c0ffd0fb0421acbf28de2e725a9a37c9 FindAFactor-6.4.2-cp312-cp312-manylinux_2_39_x86_64.whl
9ade956cd0188882baabe6581bf92fe49066e28a FindAFactor-6.4.2-cp312-cp312-win_amd64.whl
1e82aa0faa5ec15b10b7ace130d84dc11a2acf8e FindAFactor-6.4.2-cp313-cp313-macosx_13_0_x86_64.whl
561b683ea0581198bce23ec4fd44a09fcbb89f0e FindAFactor-6.4.2-cp313-cp313-macosx_14_0_arm64.whl
b1e20d6e1c1b4d0f3e6eff223242a0aa9a81e29b FindAFactor-6.4.2-cp313-cp313-macosx_15_0_arm64.whl
c50ec2804e9750eec7c12e4760194e6c0d0f1520 FindAFactor-6.4.2-cp38-cp38-manylinux_2_31_x86_64.whl
a164535c1caa53842b34cac68cb7a1f838503289 findafactor-6.4.2.tar.gz

Cut unused variables and fix off-by-one

This release cuts unused variables. It also fixes an off-by-one condition, for counting batch numbers from the high end of sieving intervals. (This is more important to PRIME_PROVER mode than to FACTOR_FINDER, as PRIME_PROVER might actually sieve the entire range, whereas FACTOR_FINDER will reasonably never be expected to do so.)

Full Changelog: v6.4.0...v6.4.1

sha1sum results:
a823e69db4042141f7b480dd5045fb19f9d6d479 FindAFactor-6.4.1-cp310-cp310-manylinux_2_35_x86_64.whl
ac591e9c5d7bf2778c7176141f45e2b9f4a8f591 FindAFactor-6.4.1-cp312-cp312-manylinux_2_39_x86_64.whl
289471ad86a31e3641fceff1009ce9b67f04b273 FindAFactor-6.4.1-cp312-cp312-win_amd64.whl
2d29bf06fc8cf22a72d3c44377e51c5493618cb2 FindAFactor-6.4.1-cp313-cp313-macosx_13_0_x86_64.whl
cda978e5f5b440a762d679bacd38c9968baf3b28 FindAFactor-6.4.1-cp313-cp313-macosx_14_0_arm64.whl
a71ccc428af5a3b04dbfb3110b6167b7fded2925 FindAFactor-6.4.1-cp313-cp313-macosx_15_0_arm64.whl
fde7ada73f168fa7f82506fdfb436cf4b86de9c9 FindAFactor-6.4.1-cp38-cp38-manylinux_2_31_x86_64.whl
887cd49c7e4b83c1979fa1497eef982e75d466c7 findafactor-6.4.1.tar.gz