БЫСТРЫЙ АЛГОРИТМ ПРОВЕРКИ ВЫРОЖДЕННОСТИ ГАНКЕЛЕВЫХ МАТРИЦ

  • Published on
    04-Apr-2017

  • View
    215

  • Download
    2

Embed Size (px)

Transcript

  • 12 2 (2011)

    VIII : ,

    190- 120-

    510.52

    .., .. (. ) ykuz@niisi.ras.ru,petrunin@niisi.ras.ru

    2009-2010 .. (

    - ..) , -

    -

    . -

    O(n log2 n), -

    468.

    - -. [1]-[3] 2009-2010 .. ( - ..) - - , . , ( ) .

    .

    -

    , 09-01-00287- 11-01-12002---2011

  • ... 61

    C R - . - : . [4].

    - ( O(n log2 n)), - , - [6].

    C O(n log2 n). -. C 468. , (. [8]).

    -.

    . a b, deg a > deg b.

    u0 = a, u1 = b,

    v0 = 0, v1 = 1,

    w0 = 1, w1 = 0,

    ui+1 = ui1 qiui,vi+1 = vi1 qivi,

    wi+1 = wi1 qiwi,

    qi , ui1 ui, ui+1 .

    , i 0

    wiu0 + viu1 = ui,

    (vi, wi) = 1,

    i = k, uk+1 = 0, ..uk uk1. uk (a, b), wk vk , wku0 + vku1 = (a, b).

    2 ui ui+1 {uj}, ui+1, ui+2 (

    ui+1ui+2

    )=

    (0 11 qi+1

    )(uiui+1

    )

  • 62 . . , . .

    (uiui+1

    )=

    (qi+1 11 0

    )(ui+1ui+2

    )

    (q 11 0

    ), deg q > 0 , -

    . ,

    (ab

    )= Q

    (uiui+1

    ), i, Q

    Q1 =

    (wi viwi+1 vi+1

    ).

    , , ,

    (ab

    )=

    Q

    (a

    b

    ), Q deg(a) > deg(b), a b

    , .. i a = ui b = ui+1 [7]. - [5]. -

    a b, deg(a) > deg(b), Q

    ,

    (ab

    )= Q

    (uiui+1

    ), deg(ui+1) < deg(a)2 deg(ui).

    - - , - .

    - - , , . 1973 . , - , - . - , [5] 8- , , , . 1980- , [6], , - , . , , . - . [5] . , 10 - . . . [7], , . -, .

    - [7], HGCD. , EMGCD [6]

  • ... 63

    . HGCD, ui, ui+1, .

    HGCD

    : a, b, deg b < deg a = n.: Q , deg(c) n/2 > deg(d), (

    c

    d

    )= Q1

    (ab

    ).

    HGCD(a, b):

    1. m := deg a2

    ; deg(b) < m, E;

    2. a0 := a div xm; b0 := b div xm;

    R := HGCD(a0, b0);(a

    b

    ):= R1

    (ab

    );

    3. deg(b) < m, R;

    4. q := a div b;

    (cd

    ):=

    (b

    amodb

    );

    5. l := deg(c); k := 2m l;6. c0 := c div xk; d0 := d div xk;

    S := HGCD(c0, d0);

    7. Q := R (q 11 0

    )S;

    Q.

    , -- O(n log2 n). - .

    1. - HGCD -

    n 117n log22(n) + O(n log(n)) n = 2k 234n log22(n) +O(n log(n)) n.

    . T (n) HGCD - a, b, , n = deg a > deg b, M(n) n.

    n = 2k.

  • 64 . . , . .

    T (n) HGCD. 2 a0 b0, , -

    . a0, b0 T (n

    2), .. deg(b0) < deg(a0) = nm = n2 .

    , R , -, Q, . 7 :

    Q := S (0 11 q

    )R.

    , R. , R ( ), R1. 1 [7]. -, R deg(a0) n2 .

    , 2 4M(n) +O(n).

    4 a div b amodb. D(n) f -

    g, deg(g) = n deg f 2n1. , m deg(b) < deg(a) deg(uj).

    , .

    1. - n n 234n log22(n) + O(n log2(n)) n = 2k 468n log22(n) +O(n log2(n))

    . a b, HGCD - n- uj . , , HGCD - 2n+1 468n log22(n)+O(n log2(n)). n = 2k 1 234n log22(n) +O(n log2(n)).

    [1] . . , . . -, S- - , . ., 200, 11, 2009, 15-44

    [2] . . , , , 430, 3, 2010, 318-320

    [3] . . , . . -, - - , ,433, 2, 2010, 154-157

    [4] Tyrtyshnikov E.E. Fast algorithms for toeplitz and quasi-toeplitz systems. J.Numer. Anal. Math. Modelling, 4, 5, 1989, 419-430.

    [5] Aho A. V., Hopcroft J. E., Ullman J. D., The design and analysis of computeralgorithms. Addison-Wesley, Reading, Mass., 1976.

    [6] Richard P. Brent, Fred G. Gustavson, David Y. Y. Yun, Fast solutionof Toeplitz systems of equations and computation of Pade approximants,Journal of Algorithms 1, 1980, 259-295. ISSN 0196-6774. MR 82d:65033. URL:http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub059.html.

    [7] K. Thull and C. Yap. A unied approach to HGCD algorithms for po-lynomials and integers. Manuscript, 1990, http://cs.nyu.edu/cs/faculty/yap/allpapers.html/.

  • ... 67

    [8] . . , - , , 22, 1, 2010, 17-49

    [9] .., , -, , 2008, 277-289, http://parallel.ru/info/VVV/18.pdf

    [10] Bernstein D. J., Fast multiplication and its applications. In: AlgorithmicNumber Theory. Lattices, Number Fields, Curves and Cryptography (Mathe-matical Sciences Research Institute Publications), 44 (Buhler J. P. et al., eds.).Cambridge, 2008, pp. 325-384.

    17.10.2011