Prev: I trod on poo today
Next: Problem with simultaneous equations and unit vectors!
From: david on 13 Apr 2010 00:24
I have been trying to implement GNFS in Mathematica for quite some time but got stuck on finding the square root of a finite field.

The example I have been following is in Section 5 of Matthew Brigg's "An Introduction to the General Number Field Sieve" which can be found at:
http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf

-----
In 5.10, there is a example given where,

p = 9929

f(x) = x^3 + 15x^2 + 29x + 8, where f is irreducible in Z/pZ which is checked by showing gcd(f,x^p - x) = 1

F_{p^3} is a finite field where elements may be represented as theta_p where theta_p is a root of f(x) in the splitting field of f(x) over Z/pZ. also F_{p^3} is denoted by F_p(theta_p)

q = p^3

r = 3

s = 122356359011

q - 1 = 2^r * s
----------

The task is to find a quadratic non-residue in F_p(theta_p) in which Briggs uses a direct search to find that (theta_p + 1) is a non-residue since
(theta_p)^((9929^3 - 1)/2) = -1 mod 9929 from Euler's Criterion.

The problem I am having is visualizing what this theta_p looks like. For this problem does it need to actually be computed to get a specific number? or does it hold a certain property that I am just not getting? I am thinking it's the latter.

Next, he continues with it following that the Sylow 2-subgroup S_8 of F_p(theta_p) can be represented by the set {1, (theta_p + 1)^s, (theta_p + 1)^(2s),..., (theta_p + 1)^(7s)}

Is the "s" in this Sylow 2-subgroup the one defined earlier?

Then he goes on to say
delta_p = 2027*theta_p^2 + 3891*theta_p + 6659
and by direct computation, it is seen that
delta^s = 9928 mod 9929

Again, this goes back to my previous question on what is theta_p and what is s.
From: Tony on 13 Apr 2010 06:49
On Apr 13, 10:24 am, david <da...(a)fabric8d.com> wrote:
> I have been trying to implement GNFS in Mathematica for quite some time but got stuck on finding the square root of a finite field.
>
> The example I have been following is in Section 5 of Matthew Brigg's "An Introduction to the General Number Field Sieve" which can be found at:http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestrict...
>
> -----
> In 5.10, there is a example given where,
>
> p = 9929
>
> f(x) = x^3 + 15x^2 + 29x + 8, where f is irreducible in Z/pZ which is checked by showing gcd(f,x^p - x) = 1
>
> F_{p^3} is a finite field where elements may be represented as theta_p where theta_p is a root of f(x) in the splitting field of f(x) over Z/pZ. also F_{p^3} is denoted by F_p(theta_p)
>
> q = p^3
>
> r = 3
>
> s = 122356359011
>
> q - 1 = 2^r * s
> ----------
>
> The task is to find a quadratic non-residue in F_p(theta_p) in which Briggs uses a direct search to find that (theta_p + 1) is a non-residue since
> (theta_p)^((9929^3 - 1)/2) = -1 mod 9929 from Euler's Criterion.
>
> The problem I am having is visualizing what this theta_p looks like. For this problem does it need to actually be computed to get a specific number? or does it hold a certain property that I am just not getting? I am thinking it's the latter.
>
> Next, he continues with it following that the Sylow 2-subgroup S_8 of F_p(theta_p) can be represented by the set {1, (theta_p + 1)^s, (theta_p + 1)^(2s),..., (theta_p + 1)^(7s)}
>
> Is the "s" in this Sylow 2-subgroup the one defined earlier?
>
> Then he goes on to say
> delta_p = 2027*theta_p^2 + 3891*theta_p + 6659
> and by direct computation, it is seen that
> delta^s = 9928 mod 9929
>
> Again, this goes back to my previous question on what is theta_p and what is s.

The only thing you need to know about theta_p is that it is a root of
f(x). So whenever an arithmetic operation creates an expression which
contains third or higher powers of theta_p, you can use theta_p^3 =
-15*theta_p^2 - 29*theta_p - 8 to cancel them.
It's like complex numbers: the simplest definition of i is that it is
a root of the polynomial x^2 + 1.
From: Chip Eastham on 13 Apr 2010 10:05
On Apr 13, 4:24 am, david <da...(a)fabric8d.com> wrote:
> I have been trying to implement GNFS in Mathematica for quite some time but got stuck on finding the square root of a finite field.
>
> The example I have been following is in Section 5 of Matthew Brigg's "An Introduction to the General Number Field Sieve" which can be found at:http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestrict...
>
> -----
> In 5.10, there is a example given where,
>
> p = 9929
>
> f(x) = x^3 + 15x^2 + 29x + 8, where f is irreducible in Z/pZ which is checked by showing gcd(f,x^p - x) = 1
>
> F_{p^3} is a finite field where elements may be represented as theta_p where theta_p is a root of f(x) in the splitting field of f(x) over Z/pZ. also F_{p^3} is denoted by F_p(theta_p)
>
> q = p^3
>
> r = 3
>
> s = 122356359011
>
> q - 1 = 2^r * s
> ----------
>
> The task is to find a quadratic non-residue in F_p(theta_p) in which Briggs uses a direct search to find that (theta_p + 1) is a non-residue since
> (theta_p)^((9929^3 - 1)/2) = -1 mod 9929 from Euler's Criterion.
>
> The problem I am having is visualizing what this theta_p looks like. For this problem does it need to actually be computed to get a specific number? or does it hold a certain property that I am just not getting? I am thinking it's the latter.
>
> Next, he continues with it following that the Sylow 2-subgroup S_8 of F_p(theta_p) can be represented by the set {1, (theta_p + 1)^s, (theta_p + 1)^(2s),..., (theta_p + 1)^(7s)}
>
> Is the "s" in this Sylow 2-subgroup the one defined earlier?
>
> Then he goes on to say
> delta_p = 2027*theta_p^2 + 3891*theta_p + 6659
> and by direct computation, it is seen that
> delta^s = 9928 mod 9929
>
> Again, this goes back to my previous question on
> what is theta_p and what is s.

I don't know that there's any more concrete way
to think about "what is theta_p" than as an
abstract root of f(x) being adjoined to F_p.
The abstract way of thinking gives rise to a
completely practical way of computing with it.
Essentially F_p(theta) is the polynomial ring
F_p[x] modulo the (maximal) ideal generated by
irreducible polynomial f(x), and theta is the
image of x under this quotient mapping.

As Tony notes, for the most part any computation
to be done with elements of F_p(theta), up to
isomorphism the unique field of prime power order
p^3, can be achieved by using a basis over F_p
involving 1,theta,theta^2 and the irreducible
polynomial f(x) = x^3 + 15x^2 + 29x + 8, given
modulus p = 9929. The basis gives a unique
representation of all the elements of F_p(theta),
addition is component-wise, and multiplication
can be done modulo f(x).

Some background facts: The multiplicative group
of nonzero elements of F_p(theta) is cyclic of
order p^3 - 1, so the "Sylow" theory of this
group is accordingly simplified. In any case 8
is the largest power of 2 that divides p^3 - 1,
so you'd want an element which is an eighth root
of unit in F_p(theta). I haven't looked at the
thesis you linked, but perhaps the connection is
being made between constructing an eighth root of
unity and a quadratic nonresidue (since if such
an eighth root of unity had a square root, that
would have order 16, which would be impossible).

regards, chip
 | 
Pages: 1
Prev: I trod on poo today
Next: Problem with simultaneous equations and unit vectors!