Repository: mhostetter/galois

Issue:
`Poly.Degrees` with duplicate degrees produces incorrect polynomial
An issue was peripherally discovered in #212 where `Poly.Degrees` produces the wrong polynomial if duplicate degrees are provided.

```python
# Wrong answer
In [5]: galois.Poly.Degrees([256, 1, 1, 1, 0])                                                                            
Out[5]: Poly(x^256 + x^2 + x + 1, GF(2))

In [6]: galois.Poly.Degrees([256, 1, 0])                                                                                  
Out[6]: Poly(x^256 + x + 1, GF(2))
```

The solution is to throw a `ValueError` if duplicates are passed in.

Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) Report
> Merging [#219](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) (2042edd) into [master](https://codecov.io/gh/mhostetter/galois/commit/a89fd868478949fe249ff5705d9acf6123441e3c?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) (a89fd86) will **increase** coverage by `0.04%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/mhostetter/galois/pull/219/graphs/tree.svg?width=650&height=150&src=pr&token=3FJML79ZUK&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter)](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter)

```diff
@@            Coverage Diff             @@
##           master     #219      +/-   ##
==========================================
+ Coverage   92.87%   92.92%   +0.04%     
==========================================
  Files          38       38              
  Lines        4366     4367       +1     
==========================================
+ Hits         4055     4058       +3     
+ Misses        311      309       -2     
```


| [Impacted Files](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter) | Coverage Δ | |
|---|---|---|
| [galois/\_polys/\_factor.py](https://codecov.io/gh/mhostetter/galois/pull/219/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-Z2Fsb2lzL19wb2x5cy9fZmFjdG9yLnB5) | `98.33% <100.00%> (ø)` | |
| [galois/\_polys/\_poly.py](https://codecov.io/gh/mhostetter/galois/pull/219/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-Z2Fsb2lzL19wb2x5cy9fcG9seS5weQ==) | `94.14% <100.00%> (+0.01%)` | :arrow_up: |
| [galois/\_fields/\_array.py](https://codecov.io/gh/mhostetter/galois/pull/219/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-Z2Fsb2lzL19maWVsZHMvX2FycmF5LnB5) | `94.79% <0.00%> (+0.34%)` | :arrow_up: |
| [galois/\_fields/\_ufuncs.py](https://codecov.io/gh/mhostetter/galois/pull/219/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter#diff-Z2Fsb2lzL19maWVsZHMvX3VmdW5jcy5weQ==) | `89.24% <0.00%> (+0.63%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter). Last update [a89fd86...2042edd](https://codecov.io/gh/mhostetter/galois/pull/219?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Matt+Hostetter).


Patch:
diff --git a/galois/_polys/_factor.py b/galois/_polys/_factor.py
index 6d25fd82d..693e271ae 100644
--- a/galois/_polys/_factor.py
+++ b/galois/_polys/_factor.py
@@ -129,8 +129,8 @@ def square_free_factorization(poly):
 
     # Step 2: Find all remaining factors (their multiplicities are divisible by p)
     if d != one:
-        degrees = [degree // p for degree in d.degrees]
-        coeffs = d.coeffs ** (field.characteristic**(field.degree - 1))  # The inverse Frobenius automorphism of the coefficients
+        degrees = [degree // p for degree in d.nonzero_degrees]
+        coeffs = d.nonzero_coeffs ** (field.characteristic**(field.degree - 1))  # The inverse Frobenius automorphism of the coefficients
         delta = Poly.Degrees(degrees, coeffs=coeffs, field=field)  # The p-th root of d(x)
         f, m = square_free_factorization(delta)
         factors_.extend(f)
diff --git a/galois/_polys/_poly.py b/galois/_polys/_poly.py
index f0082ba15..55161b5e6 100644
--- a/galois/_polys/_poly.py
+++ b/galois/_polys/_poly.py
@@ -133,12 +133,13 @@ class Poly:
             # Use the field of the coefficients
             field = type(coeffs)
         else:
-            # Convert coefficients to the specified field (or GF2 if unspecified)
+            # Convert coefficients to the specified field (or GF2 if unspecified), taking into
+            # account negative coefficients
             field = GF2 if field is None else field
-            if isinstance(coeffs, np.ndarray):
-                # Ensure coeffs is an iterable
-                coeffs = coeffs.tolist()
-            coeffs = field([int(-field(abs(c))) if c < 0 else c for c in coeffs])
+            coeffs = np.array(coeffs, dtype=field.dtypes[-1])
+            idxs = coeffs < 0
+            coeffs = field(np.abs(coeffs))
+            coeffs[idxs] *= -1
 
         return coeffs, field
 
@@ -451,29 +452,31 @@ class Poly:
             GF = galois.GF(2**8)
             galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF)
         """
-        coeffs = [1,]*len(degrees) if coeffs is None else coeffs
         if not isinstance(degrees, (list, tuple, np.ndarray)):
             raise TypeError(f"Argument `degrees` must array-like, not {type(degrees)}.")
-        if not isinstance(coeffs, (list, tuple, np.ndarray, FieldArray)):
+        if not isinstance(coeffs, (type(None), list, tuple, np.ndarray, FieldArray)):
             raise TypeError(f"Argument `coeffs` must array-like, not {type(coeffs)}.")
         if not isinstance(field, (type(None), FieldClass)):
-            raise TypeError(f"Argument `field` must be a Galois field array class, not {field}.")
-        if isinstance(degrees, (np.ndarray, FieldArray)) and not degrees.ndim <= 1:
+            raise TypeError(f"Argument `field` must be a Galois field array class, not {type(field)}.")
+
+        degrees = np.array(degrees, dtype=np.int64)
+        coeffs = [1,]*len(degrees) if coeffs is None else coeffs
+        coeffs, field = cls._convert_coeffs(coeffs, field)
+
+        if not degrees.ndim <= 1:
             raise ValueError(f"Argument `degrees` can have dimension at most 1, not {degrees.ndim}.")
-        if isinstance(coeffs, (np.ndarray, FieldArray)) and not coeffs.ndim <= 1:
-            raise ValueError(f"Argument `coeffs` can have dimension at most 1, not {coeffs.ndim}.")
-        if not all(degree >= 0 for degree in degrees):
+        if not degrees.size == np.unique(degrees).size:
+            raise ValueError(f"Argument `degrees` must have unique entries, not {degrees}.")
+        if not np.all(degrees >= 0):
             raise ValueError(f"Argument `degrees` must have non-negative values, not {degrees}.")
-        if not len(degrees) == len(coeffs):
-            raise ValueError(f"Arguments `degrees` and `coeffs` must have the same length, not {len(degrees)} and {len(coeffs)}.")
-
+        if not coeffs.ndim <= 1:
+            raise ValueError(f"Argument `coeffs` can have dimension at most 1, not {coeffs.ndim}.")
+        if not degrees.size == coeffs.size:
+            raise ValueError(f"Arguments `degrees` and `coeffs` must have the same length, not {degrees.size} and {coeffs.size}.")
 
+        # No nonzero degrees means it's the zero polynomial
         if len(degrees) == 0:
-            degrees = [0]
-            coeffs = [0]
-        dtype = np.int64 if max(degrees) <= np.iinfo(np.int64).max else np.object_
-        degrees = np.array(degrees, dtype=dtype)
-        coeffs, field = cls._convert_coeffs(coeffs, field)
+            degrees, coeffs = np.array([0]), field([0])
 
         if field is GF2:
             if len(degrees) < SPARSE_VS_BINARY_POLY_FACTOR*max(degrees):


Test patch:
diff --git a/tests/polys/test_constructors.py b/tests/polys/test_constructors.py
index c7146da19..15eaa3a58 100644
--- a/tests/polys/test_constructors.py
+++ b/tests/polys/test_constructors.py
@@ -180,12 +180,14 @@ def test_degrees_exceptions():
 
     with pytest.raises(ValueError):
         galois.Poly.Degrees(np.atleast_2d(degrees), coeffs=coeffs, field=GF)
+    with pytest.raises(ValueError):
+        galois.Poly.Degrees([5, 1, 1, 0], coeffs=[1, 2, 2, 1], field=GF)
+    with pytest.raises(ValueError):
+        galois.Poly.Degrees([5, -3, 0], coeffs=coeffs, field=GF)
     with pytest.raises(ValueError):
         galois.Poly.Degrees(degrees, coeffs=np.atleast_2d(coeffs), field=GF)
     with pytest.raises(ValueError):
         galois.Poly.Degrees([7] + degrees, coeffs=coeffs, field=GF)
-    with pytest.raises(ValueError):
-        galois.Poly.Degrees([5, -3, 0], coeffs=coeffs, field=GF)
 
 
 @pytest.mark.parametrize("field", FIELDS)