Repository: more-itertools/more-itertools

Issue:
More rounds for is_prime() ?
The paper [Primality Testing Under Adversarial Conditions](https://eprint.iacr.org/2018/749.pdf) recommends increasing the number of Miller-Rabin rounds to 64.

They note that in non-adversarial conditions, such as generating random large primes, there is no performance degradation because composites are usually weeded-out in the first few rounds. So the extra work is in certifying an actual prime.

```
diff --git a/more_itertools/recipes.py b/more_itertools/recipes.py
index cf61fc6..b1a7e4e 100644
--- a/more_itertools/recipes.py
+++ b/more_itertools/recipes.py
@@ -1134,8 +1134,7 @@ def is_prime(n):
     This function uses the Miller-Rabin primality test, which can return false
     positives for very large inputs. For values of *n* below 10**24
     there are no false positives. For larger values, there is less than
-    a 1 in 2**64 false positive rate. Multiple tests can reduce the chance
-    of a false positive.
+    a 1 in 2**128 false positive rate.
     """
     if n < 17:
         return n in {2, 3, 5, 7, 11, 13}
@@ -1145,7 +1144,7 @@ def is_prime(n):
         if n < limit:
             break
     else:
-        bases = [randrange(2, n - 1) for i in range(32)]
+        bases = [randrange(2, n - 1) for i in range(64)]
     return all(_strong_probable_prime(n, base) for base in bases)

```

Discussion:

Solution patch:
diff --git a/.github/workflows/python-app.yml b/.github/workflows/python-app.yml
index 01935a6..f2d6956 100644
--- a/.github/workflows/python-app.yml
+++ b/.github/workflows/python-app.yml
@@ -8,7 +8,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        python-version: ["3.8", "3.9", "3.10", "3.11", "3.12", "3.13", "pypy-3.10"]
+        python-version: ["3.9", "3.10", "3.11", "3.12", "3.13", "pypy-3.10"]
 
     steps:
     - uses: actions/checkout@v4
@@ -22,16 +22,16 @@ jobs:
     - name: Run tests
       run: make coverage
     - name: Static checks
-      if: "matrix.python-version == '3.8'"
+      if: "matrix.python-version == '3.9'"
       run: make check
     - name: Build docs with sphinx
-      if: "matrix.python-version == '3.8'"
+      if: "matrix.python-version == '3.9'"
       run: make docs
     - name: Build packages
-      if: "matrix.python-version == '3.8'"
+      if: "matrix.python-version == '3.9'"
       run: make package
     - name: Upload packages
-      if: "matrix.python-version == '3.8'"
+      if: "matrix.python-version == '3.9'"
       uses: actions/upload-artifact@v4
       with:
         name: more-itertools-packages
diff --git a/docs/conf.py b/docs/conf.py
index 1e28765..11d08fc 100644
--- a/docs/conf.py
+++ b/docs/conf.py
@@ -10,9 +10,9 @@
 # All configuration values have a default; values that are commented out
 # serve to show the default.
 
-import sys, os
+import sys
+import os
 
-import sphinx_rtd_theme
 
 # If extensions (or modules to document with autodoc) are in another directory,
 # add these directories to sys.path here. If the directory is relative to the
diff --git a/more_itertools/more.py b/more_itertools/more.py
index 0e05986..9cd0140 100755
--- a/more_itertools/more.py
+++ b/more_itertools/more.py
@@ -218,8 +218,8 @@ def first(iterable, default=_marker):
         return item
     if default is _marker:
         raise ValueError(
-            'first() was called on an empty iterable, and no '
-            'default value was provided.'
+            'first() was called on an empty iterable, '
+            'and no default value was provided.'
         )
     return default
 
@@ -240,15 +240,14 @@ def last(iterable, default=_marker):
         if isinstance(iterable, Sequence):
             return iterable[-1]
         # Work around https://bugs.python.org/issue38525
-        elif hasattr(iterable, '__reversed__') and (hexversion != 0x030800F0):
+        if hasattr(iterable, '__reversed__'):
             return next(reversed(iterable))
-        else:
-            return deque(iterable, maxlen=1)[-1]
+        return deque(iterable, maxlen=1)[-1]
     except (IndexError, TypeError, StopIteration):
         if default is _marker:
             raise ValueError(
-                'last() was called on an empty iterable, and no default was '
-                'provided.'
+                'last() was called on an empty iterable, '
+                'and no default value was provided.'
             )
         return default
 
diff --git a/more_itertools/more.pyi b/more_itertools/more.pyi
index f8543b4..b33dcff 100644
--- a/more_itertools/more.pyi
+++ b/more_itertools/more.pyi
@@ -12,7 +12,6 @@ from typing import (
     ContextManager,
     Generic,
     Hashable,
-    Mapping,
     Iterable,
     Iterator,
     Mapping,
diff --git a/more_itertools/recipes.py b/more_itertools/recipes.py
index cf61fc6..e5d032e 100644
--- a/more_itertools/recipes.py
+++ b/more_itertools/recipes.py
@@ -1009,12 +1009,8 @@ def matmul(m1, m2):
     return batched(starmap(_sumprod, product(m1, transpose(m2))), n)
 
 
-def factor(n):
-    """Yield the prime factors of n.
-
-    >>> list(factor(360))
-    [2, 2, 2, 3, 3, 5]
-    """
+def _factor_trial(n):
+    # Factor using trial division, used for small inputs
     for prime in sieve(math.isqrt(n) + 1):
         while not n % prime:
             yield prime
@@ -1025,6 +1021,44 @@ def factor(n):
         yield n
 
 
+def _factor_pollard(n):
+    # Return a factor of n using Pollard's rho algorithm
+    for b in range(1, n - 2):
+        x = y = 2
+        d = 1
+        while d == 1:
+            x = (x * x + b) % n
+            y = (y * y + b) % n
+            y = (y * y + b) % n
+            d = math.gcd(x - y, n)
+        if d != n:
+            return d
+    raise ValueError('prime or under 5')
+
+
+def factor(n):
+    """Yield the prime factors of n.
+
+    >>> list(factor(360))
+    [2, 2, 2, 3, 3, 5]
+
+    This function uses trial division for when *n* is less than 1000 and
+    Pollard's rho algorithm for larger inputs.
+    """
+    todo = [n] if n > 1 else []
+    factors = []
+    while todo:
+        n = todo.pop()
+        if is_prime(n):
+            factors += [n]
+        elif n < 1000:
+            factors += _factor_trial(n)
+        else:
+            fact = _factor_pollard(n)
+            todo += (n // fact, fact)
+    return iter(sorted(factors))
+
+
 def polynomial_eval(coefficients, x):
     """Evaluate a polynomial at a specific value.
 
@@ -1134,8 +1168,8 @@ def is_prime(n):
     This function uses the Miller-Rabin primality test, which can return false
     positives for very large inputs. For values of *n* below 10**24
     there are no false positives. For larger values, there is less than
-    a 1 in 2**64 false positive rate. Multiple tests can reduce the chance
-    of a false positive.
+    a 1 in 2**128 false positive rate. Multiple tests can further reduce the
+    chance of a false positive.
     """
     if n < 17:
         return n in {2, 3, 5, 7, 11, 13}
@@ -1145,7 +1179,7 @@ def is_prime(n):
         if n < limit:
             break
     else:
-        bases = [randrange(2, n - 1) for i in range(32)]
+        bases = [randrange(2, n - 1) for i in range(64)]
     return all(_strong_probable_prime(n, base) for base in bases)
 
 
diff --git a/more_itertools/recipes.pyi b/more_itertools/recipes.pyi
index 1f73af9..63f641a 100644
--- a/more_itertools/recipes.pyi
+++ b/more_itertools/recipes.pyi
@@ -129,6 +129,8 @@ def reshape(
     matrix: Iterable[Iterable[_T]], cols: int
 ) -> Iterator[tuple[_T, ...]]: ...
 def matmul(m1: Sequence[_T], m2: Sequence[_T]) -> Iterator[tuple[_T]]: ...
+def _factor_trial(n: int) -> Iterator[int]: ...
+def _factor_pollard(n: int) -> int: ...
 def factor(n: int) -> Iterator[int]: ...
 def polynomial_eval(coefficients: Sequence[_T], x: _U) -> _U: ...
 def sum_of_squares(it: Iterable[_T]) -> _T: ...
diff --git a/pyproject.toml b/pyproject.toml
index 682f20e..b6a9be4 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -6,7 +6,7 @@ build-backend = "flit_core.buildapi"
 name = "more-itertools"
 authors = [{name = "Erik Rose", email = "erikrose@grinchcentral.com"}]
 readme = "README.rst"
-requires-python = ">=3.8"
+requires-python = ">=3.9"
 license = {file = "LICENSE"}
 keywords = [
     "itertools",
@@ -24,7 +24,6 @@ classifiers = [
     "Natural Language :: English",
     "License :: OSI Approved :: MIT License",
     "Programming Language :: Python :: 3",
-    "Programming Language :: Python :: 3.8",
     "Programming Language :: Python :: 3.9",
     "Programming Language :: Python :: 3.10",
     "Programming Language :: Python :: 3.11",
@@ -39,11 +38,12 @@ dynamic = ["version", "description"]
 
 [project.urls]
 Homepage = "https://github.com/more-itertools/more-itertools"
+Documentation = "https://more-itertools.readthedocs.io/en/stable/"
 
 [tool.flit.module]
 name = "more_itertools"
 
 [tool.black]
 line-length = 79
-target-version = ['py38']
+target-version = ["py39"]
 skip-string-normalization = true
diff --git a/requirements/development.txt b/requirements/development.txt
index a879a9e..03c2f8f 100644
--- a/requirements/development.txt
+++ b/requirements/development.txt
@@ -2,7 +2,7 @@ black
 coverage
 flake8
 flit
-mypy
+mypy==1.13
 setuptools
 sphinx
 sphinx_rtd_theme


Test patch:
diff --git a/tests/test_recipes.py b/tests/test_recipes.py
index 6f8bfaf..c31d2b1 100644
--- a/tests/test_recipes.py
+++ b/tests/test_recipes.py
@@ -1153,8 +1153,12 @@ class FactorTests(TestCase):
             (6, [2, 3]),
             (360, [2, 2, 2, 3, 3, 5]),
             (128_884_753_939, [128_884_753_939]),
-            (999953 * 999983, [999953, 999983]),
-            (909_909_090_909, [3, 3, 7, 13, 13, 751, 113797]),
+            (999_953 * 999_983, [999_953, 999_983]),
+            (909_909_090_909, [3, 3, 7, 13, 13, 751, 1_137_97]),
+            (
+                1_647_403_876_764_101_672_307_088,
+                [2, 2, 2, 2, 19, 23, 109471, 13571009, 158594251],
+            ),
         ):
             with self.subTest(n=n):
                 actual = list(mi.factor(n))