Let L be a primitive root of unity, L^n=1. Let ca=a0*L^0+a1*L^1+...+a(n-1)*L^(n-1) be an element in the cyclotomic field generated by L. (The coefficients a0...a(n-1) are typically rational numbers in the context of the mathematical objects called Number Fields, from whence "Number Field Sieve".) Similarly another element cb with coefficients b0...b(n-1). We wish to divide them, to compute cb/ca.
That is, we wish to find cx such that ca*cx = cb. Let cx have coefficients x0...x(n-1). Expand ca*cx by the distributive law and collect by like powers of L. For powers of L that are greater than or equal to n, reduce the power according to the rule L^n=1, that is, compute the exponent mod n. Collect by like reduced powers.
Match up the like powers of (collected) ca*cx with like powers of cb and set them equal to each other. This results in a system of n linear equations in the n unknown coefficients of cx. Write the system of linear equations in matrix form Ax=b then solve for x as usual. You probably want some matrix library that can work with exact rational numbers in order for the output coefficients of cx to be rational numbers.
The matrix A is highly structured, containing lots of cyclic permutations of the coefficients a0...a(n-1). It might be possible to exploit this structure to compute things faster, but I don't know how.
Recall we are computing cb/ca. If we have a constant ca but lots of different cb, then we can precompute the reciprocal of ca once (that is, divide 1/ca by the above method), then all the divisions become multiplications by the reciprocal. However, conversely, if we have constant cb but lots of different ca, is there a way to precompute something to make it go faster? Although the matrix A will differ each time, the pattern of the permuted coefficients remains the same, so it suggests it might be possible to precompute something.
This method can be generalized beyond cyclotomic fields. The exponents were reduced by the rule L^n=1, so L is the generator of a cyclic group. We can generalize to a different group structure using different reduction rules for a different group's generators. (Groups that are not cyclic groups must have more than 1 generator.) Note that many finite groups are very large, so we would therefore need to do very large NxN linear algebra where N is the order of the group. We also have to be careful with collecting like powers if the group does not commute.
Pari/GP has some nice built-in functionality for computing division and reciprocal in cyclotomic fields. We compute an example in the 7th cyclotomic field, with the 7th root of unity, the root of L^7-1=0. Let's compute a reciprocal of (3,1,4,1,5,9,2):
? 1/Mod(3 + 1*L + 4*L^2 + 1*L^3 + 5*L^4 + 9*L^5 + 2*L^6,L^7-1)
Mod(-145932/4200025*L^6 + 97168/4200025*L^5 - 189607/4200025*L^4 + 106793/4200025*L^3 + 430943/4200025*L^2 - 128532/4200025*L - 2832/4200025, L^7 - 1)
Aside: Pari/GP can seemingly handle modulus being an arbitrary polynomial, not just L^n-1, so there is something slightly fancier going on. Probably put the highest order term on one side: a(n)*L^n = -a(n-1)*L^(n-1) - a(n-2)*L^(n-2) - ... - a0*L^0, then define a reduction rule L^n = ... by dividing through by a(n). Actually, just use polynomial division and remainder to reduce.
We can compute the reciprocal of (3,1,4,1,5,9,2) using the linear algebra process described above. The coefficients come out in the reverse order as above.
? A=[3, 2, 9, 5, 1, 4, 1; 1, 3, 2, 9, 5, 1, 4; 4, 1, 3, 2, 9, 5, 1; 1, 4, 1, 3, 2, 9, 5; 5, 1, 4, 1, 3, 2, 9; 9, 5, 1, 4, 1, 3, 2; 2, 9, 5, 1, 4, 1, 3];
? (1/A)*[1;0;0;0;0;0;0]
[-2832/4200025]
[-128532/4200025]
[430943/4200025]
[106793/4200025]
[-189607/4200025]
[97168/4200025]
[-145932/4200025]
As with quadratic fields, we could also ask that if a programming library provides arithmetic on complex numbers, it could more generally provide arithmetic on arbitrary polynomial field extensions of the reals (complex numbers extend with L^2+1). Linear algebra, solving Ax=b, is considerably hairier than complex number arithmetic, though.
Because a field extension creates a field from another field, the process can be iterated. We can invent incredibly complicated objects which obey field axioms.
No comments:
Post a Comment