Repository: mhostetter/galois

Issue:
Replace optional return values with raising `ValueError`s
There's no real reason to return `None` upon a function failing to find an answer. Instead, a `ValueError` may be raised. This way the type hints are more consistent.

Currently, a user needs to `if ret is not None:`. With raising an error, the user would need to `try`/`except`. Essentially it's the same thing.

Discussion:

Patch:
diff --git a/galois/_prime.py b/galois/_prime.py
index b713298ec..490cfb652 100644
--- a/galois/_prime.py
+++ b/galois/_prime.py
@@ -791,10 +791,15 @@ def factors(n: int) -> Tuple[List[int], List[int]]:
 
     # Step 4
     while n > 1 and not is_prime(n):
-        f = pollard_rho(n)  # A non-trivial factor
-        while f is None:
-            # Try again with a different random function f(x)
-            f = pollard_rho(n, c=random.randint(2, n // 2))
+        while True:
+            c = 1
+            try:
+                f = pollard_rho(n, c=c)  # A non-trivial factor
+                break  # Found a factor
+            except RuntimeError:
+                # Could not find one -- keep searching
+                c = random.randint(2, n // 2)
+
         if is_prime(f):
             degree = 0
             while n % f == 0:
@@ -975,7 +980,7 @@ def trial_division(n: int, B: Optional[int] = None) -> Tuple[List[int], List[int
 
 
 @set_module("galois")
-def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> Optional[int]:
+def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> int:
     r"""
     Attempts to find a non-trivial factor of :math:`n` if it has a prime factor :math:`p` such that
     :math:`p-1` is :math:`B`-smooth.
@@ -995,6 +1000,11 @@ def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> Optional[int]:
     :
         A non-trivial factor of :math:`n`, if found. `None` if not found.
 
+    Raises
+    ------
+    RuntimeError
+        If a non-trivial factor cannot be found.
+
     Notes
     -----
     For a given odd composite :math:`n` with a prime factor :math:`p`, Pollard's :math:`p-1` algorithm can discover a non-trivial factor
@@ -1022,6 +1032,7 @@ def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> Optional[int]:
     Searching with :math:`B=15` will not recover a prime factor.
 
     .. ipython:: python
+        :okexcept:
 
         galois.pollard_p1(p*q, 15)
 
@@ -1076,7 +1087,7 @@ def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> Optional[int]:
     if d not in [1, n]:
         return d
     if d == n:
-        return None
+        raise RuntimeError(f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm with smoothness bound {B} and secondary bound {B2}.")
 
     # Try to find p such that p - 1 has a single prime factor larger than B
     if B2 is not None:
@@ -1094,11 +1105,11 @@ def pollard_p1(n: int, B: int, B2: Optional[int] = None) -> Optional[int]:
         if d not in [1, n]:
             return d
 
-    return None
+    raise RuntimeError(f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm with smoothness bound {B} and secondary bound {B2}.")
 
 
 # @functools.lru_cache(maxsize=1024)
-def pollard_rho(n: int, c: int = 1) -> Optional[int]:
+def pollard_rho(n: int, c: int = 1) -> int:
     r"""
     Attempts to find a non-trivial factor of :math:`n` using cycle detection.
 
@@ -1115,6 +1126,11 @@ def pollard_rho(n: int, c: int = 1) -> Optional[int]:
     :
         A non-trivial factor :math:`m` of :math:`n`, if found. `None` if not found.
 
+    Raises
+    ------
+    RuntimeError
+        If a non-trivial factor cannot be found.
+
     Notes
     -----
     Pollard's :math:`\rho` algorithm seeks to find a non-trivial factor of :math:`n` by finding a cycle in a sequence
@@ -1162,7 +1178,7 @@ def pollard_rho(n: int, c: int = 1) -> Optional[int]:
         d = math.gcd(a - b, n)
 
     if d == n:
-        return None
+        raise RuntimeError(f"A non-trivial factor of {n} could not be found using the Pollard Rho algorithm with f(x) = x^2 + {c}.")
 
     return d
 


Test patch:
diff --git a/tests/test_factor.py b/tests/test_factor.py
index 9ffc6cb96..cf1d28f22 100644
--- a/tests/test_factor.py
+++ b/tests/test_factor.py
@@ -174,19 +174,23 @@ def test_trial_division():
 def test_pollard_p1():
     p = 1458757  # p - 1 factors: [2, 3, 13, 1039], [2, 3, 1, 1]
     q = 1326001  # q - 1 factors: [2, 3, 5, 13, 17], [4, 1, 3, 1, 1]
-    assert galois.pollard_p1(p*q, 15) is None
+    with pytest.raises(RuntimeError):
+        assert galois.pollard_p1(p*q, 15)
     assert galois.pollard_p1(p*q, 19) == q
     assert galois.pollard_p1(p*q, 15, B2=100) == q
 
     p = 1598442007  # p - 1 factors: [2, 3, 7, 38058143], [1, 1, 1, 1]
     q = 1316659213  # q - 1 factors: [2, 3, 11, 83, 4451], [2, 4, 1, 1, 1]
-    assert galois.pollard_p1(p*q, 31) is None
+    with pytest.raises(RuntimeError):
+        assert galois.pollard_p1(p*q, 31)
     assert galois.pollard_p1(p*q, 31, B2=5000) == q
 
     p = 1636344139  # p - 1 factors: [2, 3, 11, 13, 1381], [1, 1, 1, 1, 2]
     q = 1476638609  # q - 1 factors: [2, 137, 673649], [4, 1, 1]
-    assert galois.pollard_p1(p*q, 100) is None
-    assert galois.pollard_p1(p*q, 100, B2=10_000) is None
+    with pytest.raises(RuntimeError):
+        assert galois.pollard_p1(p*q, 100)
+    with pytest.raises(RuntimeError):
+        assert galois.pollard_p1(p*q, 100, B2=10_000)
 
     n = 2133861346249  # n factors: [37, 41, 5471, 257107], [1, 1, 1, 1]
     assert galois.pollard_p1(n, 10) == 1517