Browse Groups

• ## Re: About polynomial factorization using Galois group

(5)
• NextPrevious
• Thanks for the background, Marcel. In such a situation an author might perhaps have written: I thank X for demonstrating that some of my earlier ideas were
Message 1 of 5 , Dec 2 8:57 AM
View Source
Thanks for the background, Marcel.

In such a situation an author might perhaps have written:
"I thank X for demonstrating that some of my earlier
ideas were more useful than I had supposed."

please, keep path-only. Then I can use 1.1.0 for path-only,
with advanced-setup backtrack, and still benefit from
even better factorization of polys in 1.2.

Else, you would divide your talents into incompatible packages,
which would be unfortunate for folk like Hans, Bouk and me.

Thanks, as ever, for everything that you do...

David
• ... Thank you for telling us very interesting paper. Since I m now developing the computation of the maximal order, I could not read the paper in detail. I
Message 1 of 5 , Dec 3 7:26 PM
View Source
Marcel Martin wrote:

> I just saw that F. Morain (with G. Hanrot) published the following
> paper
>
> This is a description of the method I am using to split the Hilbert
> polynomials with their Galois groups.

Thank you for telling us very interesting paper.
Since I'm now developing the computation of the maximal order,
I could not read the paper in detail.

I guessed that your polynomial factorization used subfields of
the Hilbert class fields. But I was not able to think a concrete way.
I would like to learn the method developed by you.

Thank you, Marcel

Satoshi Tomabechi
• Marcel Martin conjectured that ... The conjecture is hereby validated. Thanks, Marcel! David
Message 1 of 5 , Dec 4 11:34 AM
View Source
Marcel Martin conjectured that
> among the 300 subscribers of this list, Satoshi
> is not the only one interested in ECPP or in the
> factorization of class polynomials over Z/P.
The conjecture is hereby validated.
Thanks, Marcel!
David
• ... What I understand slightly is as follows. Class field theory tells that CL(D) = Gal(K(D)/Q), where K(D) is the Hilbert class field. We suppose that there
Message 1 of 5 , Dec 5 2:38 AM
View Source
Marcel Martin taught:
> Here, we see the advantage of the method. Instead of factoring a
> degree-15 polynomial, we only have to factor a degree-3 and a
> degree-5 polynomials.

What I understand slightly is as follows.

Class field theory tells that CL(D) = Gal(K(D)/Q),
where K(D) is the Hilbert class field.
We suppose that there is a sequence of groups
CL(G) = G1 > G2> ... > {e}.
( G>H denotes that H is a subgrouop of G)
Corresponding to the sequence we get a sequence of fields
Q =K(D)^G1 < K(D)^G2 < ... < K(D)^{e}=K(D),
where K(D)^Gi is the field which consists of elements
fixed by Gi. Also we get the polynomials Fi(X) with
coefficients in K(D)^G{i-1} which define the field
extension K(D)^Gi/K(D)^G{i-1}. By finding roots of Fi(X)
successively we get a root of the Hilbert polynomial H(D)(X).
By reduction modulo P similar procedure works over Z/P
as well as over Q.

Indeed CL(-971) is not cyclic, but there is a sequence of
groups:
CL(-971) = G1 =Z_5*Z_3 > G2=Z_5 > {e}
K(D)^G2/Q is an extension of degree 3.
K(D)/K(D)^G2 is an extension of degree 5.
Therefore we should factor a degree-3 and a degree-5
polynomials instead of factoring a degree-15 polynomial.

I look forward to your next post, however I could not understand
as you expect.
Thank you for an exciting explanation.

Satoshi Tomabechi
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.