lagrange module
Pure-Python implementation of Lagrange interpolation over finite fields.
- lagrange.lagrange.interpolate(points, modulus, degree=None)[source]
Determine the value at the origin of the domain (e.g., where x = 0) given a collection of points. The point information can be represented as a collection of two-component coordinates, as a dictionary, or as a sequence of values.
- Parameters
>>> interpolate([(1, 15), (2, 9), (3, 3)], 17) 4 >>> interpolate({1: 15, 2: 9, 3: 3}, 17) 4 >>> interpolate( ... { ... 1: 119182, 2: 11988467, 3: 6052427, 4: 8694701, ... 5: 9050123, 6: 3676518, 7: 558333, 8: 12198248, ... 9: 7344866, 10: 10114014, 11: 2239291, 12: 2515398 ... }, ... 15485867 ... ) 123
If a list of integers is supplied, it is assumed that they are the image of the sequence
[1, 2, 3, ...]
.>>> interpolate([15, 9, 3], 17) 4 >>> interpolate( ... [ ... 119182, 11988467, 6052427, 8694701, 9050123, 3676518, ... 558333, 12198248, 7344866, 10114014, 2239291, 2515398 ... ], ... 15485867 ... ) 123
If the point information is supplied as an
Iterable
of integers, that iterable object must be aSequence
.>>> interpolate({15, 9, 3}, 17) Traceback (most recent call last): ... TypeError: iterable of integers that represents points must be a sequence
Alternatively, a two-coordinate
Sequence
can be used to represent each individual point. In that case, anyIterable
of such individual points is supported.>>> interpolate({(1, 15), (2, 9), (3, 3)}, 17) 4
This function is able to interpolate when supplied more points than necessary (i.e., given the degree).
>>> lagrange({1: 4, 2: 6, 3: 8, 4: 10, 5: 12}, modulus=65537) 2 >>> lagrange({1: 4, 2: 6, 3: 8, 4: 10, 5: 12}, degree=4, modulus=65537) 2 >>> lagrange({1: 4, 2: 6, 3: 8, 4: 10, 5: 12}, degree=5, modulus=65537) Traceback (most recent call last): ... ValueError: not enough points for a unique interpolation >>> lagrange({1: 4, 2: 6, 3: 8, 4: 10, 5: 12}, degree=1, modulus=65537) 2 >>> lagrange({49: 200, 5: 24, 3: 16}, degree=2, modulus=65537) 4 >>> lagrange({49: 200, 5: 24, 3: 16}, degree=1, modulus=65537) 4 >>> lagrange({1: 16, 2: 25, 3: 36}, degree=1, modulus=65537) 7 >>> lagrange({3: 36, 1: 16, 2: 25}, degree=1, modulus=65537) 6 >>> lagrange({1: 16, 2: 25, 3: 36}, degree=2, modulus=65537) 9 >>> lagrange({3: 36, 1: 16, 2: 25}, degree=2, modulus=65537) 9 >>> lagrange({5: 64, 2: 25, 3: 36}, degree=2, modulus=65537) 9
Interpolation in trivial scenarios is supported, as well.
>>> lagrange([12345], degree=0, modulus=65537) 12345
At least one point must be supplied.
>>> interpolate([], 17) Traceback (most recent call last): ... ValueError: at least one point is required
An exception is raised if a supplied argument (or a component thereof) does not have the expected structure or is not of the expected type.
>>> interpolate({1: 15.0, 'a': 9, 'b': 3}, 17) Traceback (most recent call last): ... TypeError: dictionary that represents points must have integer keys and values >>> interpolate({(1, 15, 0), (2, 9, 0), (3, 3, 0)}, 17) Traceback (most recent call last): ... TypeError: iterable that represents points must contain integers or two-element sequences of integers >>> interpolate('abc', 123) Traceback (most recent call last): ... TypeError: iterable that represents points must contain integers or two-element sequences of integers >>> interpolate(1.23, 123) Traceback (most recent call last): ... TypeError: expecting dictionary or iterable that represents points >>> interpolate([15, 9, 3], 'abc') Traceback (most recent call last): ... TypeError: expecting an integer prime modulus >>> interpolate([15, 9, 3], -17) Traceback (most recent call last): ... ValueError: expecting a positive integer prime modulus >>> interpolate([15, 9, 3], 17, 'abc') Traceback (most recent call last): ... TypeError: expecting an integer degree >>> interpolate([15, 9, 3], 17, -3) Traceback (most recent call last): ... ValueError: expecting a nonnegative integer degree
- Return type
- lagrange.lagrange.lagrange(points, modulus, degree=None)
Alias for
interpolate
.- Return type