StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here are some steps toward an answer. First, consider the ring <code>Z/nZ</code> which is a field if <code>n</code> is prime. We can give a simple routine to compute the multiplicative inverse of an element <code>a</code></p> <pre><code>-- | Compute the inverse of a in the field Z/nZ. inverse' a n = let (s, t) = xgcd n a r = s * n + t * a in if r > 1 then Nothing else Just (if t < 0 then t + n else t) </code></pre> <p>Its type is <code>inverse :: Integral a => a -> a -> Maybe a</code> because it allows for non-prime <code>n</code>, when the multiplicative inverse does not exist.</p> <p>If a field is not a prime field, then it is a field extension of a prime field <code>K = Z/nZ</code> for some prime <code>n</code>, and is isomorphic to <code>K[x]/p</code> for some polynomial <code>p</code>. In particular, we require that there is a function</p> <pre><code>degree :: Polynomial -> Integer </code></pre> <p>that tells us the degree of a polynomial, and a partial function</p> <pre><code>project :: Integral a => Polynomial -> Maybe a </code></pre> <p>that projects a polynomial of degree 0 down to its underlying field in the obvious way. So if you know <code>n</code> and <code>p</code>, then</p> <pre><code>-- |Compute the inverse of a in the finite field K[x]/p with K=Z/nZ inverse a (n, p) = let (s, t) = xgcd p a r = s * p + t * a in if degree r > 0 then Nothing else let Just r' = inverse' (project r) n in Just $ r' * t </code></pre> <hr> <p>As an aside, if I were doing this, I would probably build on the definition of the <code>Integral</code> class in Haskell, and define a new class</p> <pre><code>class Integral a => FiniteField a where degree :: a -> Integer xgcd :: a -> a -> (a, a) inverse :: a -> a </code></pre> <p>which would have some simple instances (prime fields, which can be represented with a data type like)</p> <pre><code>data PrimeField = PF { size :: Integer, element :: Integer } </code></pre> <p>and more complicated instances for non-prime finite fields, whose elements are polynomials, probably represented with a <code>Map</code> -</p> <pre><code>data NonPrimeField = NPF { prime :: Integer , maxDegree :: Integer , element :: Map Integer Integer } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload