# Compute properties of mathematical "fields" formed by taking
# Z/n (the whole numbers modulo some whole number n) and an
# irreducible polynomial (i.e., a polynomial with only complex zeros),
# e.g., Z/5 and X**2 + 2.
# The field is formed by taking all possible linear combinations of
# a set of d base vectors (where d is the degree of the polynomial).
# Note that this procedure doesn't yield a field for all combinations
# of n and p: it may well be that some numbers have more than one
# inverse and others have none. This is what we check.
# Remember that a field is a ring where each element has an inverse.
# A ring has commutative addition and multiplication, a zero and a one:
# 0*x = x*0 = 0, 0+x = x+0 = x, 1*x = x*1 = x. Also, the distributive
# property holds: a*(b+c) = a*b + b*c.
# (XXX I forget if this is an axiom or follows from the rules.)
# Example N and polynomial
P
= poly
.plus(poly
.one(0, 2), poly
.one(2, 1)) # 2 + x**2
# Return x modulo y. Returns >= 0 even if x < 0.
# Normalize a polynomial modulo n and modulo p.
for i
in range(len(a
)): a
[i
] = mod(a
[i
], n
)
# Make a list of all n^d elements of the proposed field.
if d
== 0: return [poly
.one(0, 0)]
sub
= make_elements(n
, d
-1)
all
.append(poly
.plus(a
, poly
.one(d
-1, i
)))
inv
.append(norm(poly
.times(a
, x
), n
, p
))
all
= make_elements(n
, len(p
)-1)
inv
= make_inv(all
, n
, p
)
if all1
== inv1
: print 'BINGO!'
if type(s
) is not type(''): s
= `s`
return ' '*(width
- n
) + s
if type(s
) is not type(''): s
= `s`
return s
+ ' '*(width
- n
)