Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Titanix 2.0.5 Beta

Expand Messages
  • S.Tomabechi
    On Sun, 29 Apr 2001 01:16:13 +0200 ... ... Is it known algorithm ? I want to know the new algorithm. I had implmented Atkin-Morain ECPP. But it is
    Message 1 of 2 , May 1, 2001
    • 0 Attachment
      On Sun, 29 Apr 2001 01:16:13 +0200
      Marcel Martin wrote:

      > Titanix 2.0.5 Beta is available.
      <snip>
      > What's up?
      > ----------
      > * New algorithm to split big polynomials (30% better, on average).

      Is it known algorithm ? I want to know the new algorithm.

      I had implmented Atkin-Morain ECPP. But it is slower than Titanix.
      It takes heavy time to find a root of Hilbert class polynomial or
      Weber polynomial mod N. I implemented factoring algoritm which is
      explained in Cohen's book.

      Satoshi TOMABECHI
    • Satoshi Tomabechi
      On Wed, 02 May 2001 18:01:34 +0200 ... Your explanation is enough to understand almost everything. It is good idea to compute small power insted of large
      Message 2 of 2 , May 3, 2001
      • 0 Attachment
        On Wed, 02 May 2001 18:01:34 +0200
        Marcel Martin wrote:

        > way, i.e., GCD(P(X), (X+k)^((N-1)/2) - 1), it is better to use it this
        > way: GCD(P(X), (X+k)^((N-1)/D) - W^i) where D is a small divisor of
        > N-1 and W is a D-th root of unity successively raised to the powers
        > 0 <= i < D.

        Your explanation is enough to understand almost everything.
        It is good idea to compute small power insted of large power.
        It looks like factoring the polynomial X^n-1 into cyclotomic
        polynomials over Z/NZ.

        I thank you for your help and great soft.

        Satoshi TOMABECHI
      Your message has been successfully submitted and would be delivered to recipients shortly.