（基础数学专业论文）rs码的表单解码与多元插值分解算法.pdf

中山大学硕士毕业论文 r s 码的表单解码与多元插值分解算法 【中文摘要】 本文在m c e l i e c e 等人工作的基础上，将r s 码表单解码的g s 算法推广到多元情形，多元g s 算法 由多元插值定理与多元分解定理构成 【关键词】 表单解码，r s 码，多元插值算法，多元分解算法 r s 码表单解码与多冗插值分解算法 l i s td e c o d i n go fr e e d s o l o m o nc o d e sa n dm u l t i v a r i a t e i n t e r p o l a t i o n f a c t o r i z a t i o na l g o r i t h m s a b s t r l 虻t i nt h i sa r t i c l e ，t h eg u r u s w a m i s u d a na l g o r i t h mf o rl i s td e c o d i n go fr e e d - s o l o m o nc o d e s i se x t e n d e dt om u l t i v a r i a t ec a s e ，w h i c hc o n s i s t so fm u l t i v a r i a t ei n t e r p o l a t i o na l g o r i t h ma n dm u l 。 t i v a r i a t ef a c t o r i z a t i o na l g o r i t h m k e y w o r d s l i s td e c o d i n g ，r e e d s o l o m o nc o d e s ，m u l t i v a r i a t ei n t e r p o l a t i o na l g o r i t h m ，m u l t i v a r i a t e f a c t o r i z a t i o na l g o r i t h m 中山大学硕士毕业论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的 个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结 果由本人承担。 学位论文作者签名：日期：年月 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有 权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系 资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用 复印、缩印或其他方法保存学位论文。 学位论文作者签名：导师签名：日期：年月 日 第一章预备知识弟一早以亩划识 纠错码【1 1 】：一个f 上的h ，k ，明码就是f n 的一个七维线性子空间，其中瓣为距离，扎称 为码长。给定一个i n ，k ，d 】码够。若7 满足 2 7 - + 1 d 那么够是一个r - - 幺q 错码，即对够中的任一码字，距离该码字的距离为7 的码字至多存在一 个，满足2 丁+ 1 d 的最大的7 - 被称为码够的纠错界，。 冗s 码 1 l 】：r s 码是一种特殊的b c h 码。众所周知，r s 码也是最大距离分离码( m d s 码) ， 即n 一南= d l ，其中d 为兄s 码的距离。若够是如上的一个h ，k ，明r s 码，u 是f 中的某个 本原元，那么 够= ( u ) ，p ( u 2 ) ，p ( wj f 卜1 ) ) ：p 日i x ，d e g p d ) 符号说明： n - 非负整数集 ：集合x 的势 f ：域，一般指有限域 f i x l ：域f 上的多项式环 d e g f ( x ) ：，( z ) 的次数 r ：f i x 上次数不超过u 的多项式集合 f i x ，引：f 上的二元多项式环 m i x ，y 】= y ：i 0 ，歹o ：系数为1 的二元单项式集合 如乳， q ( x ，y ) ：q ( z ，秒) 的u ，v ) ) j h 权次数 d e g u ，t ，q ( z ，可) 全( m 州a x 仳i + 力) ) ， 其中，是指标集。 f i x ，y ，z 】：域f 上的三元多项式环 m i x ，y ，z l = c z 七：i o ，j 0 ，k o ：系数为l 的三元单项式集合 d e g , , 舢埘q ( x ，y ，z ) ：q ( x ，y ，z ) 的( 钆，u ，伽) 加权次数 d e 乳鸬加q ( z ，可，z ) 全( 囊m 七a ) x ， 【 饿+ 巧+ 叫七) ) ， 其中，是指标集。 d e g z q ( x ，y ，z ) ，d e g u q ( x ，z ) ，d e g 。q ( z ，y ，z ) ：多项式q ( x ，y ，z ) 的z ，可，z 的次数 d e g x q ( x ，y ，z ) 全d e 9 1 ，o ，o q ( x ，y ，z ) = m a x ， ) 【l j ，k ) e l 如如q ( z ，y ，z ) 垒d e g o ，1 ，o q ( x ，y ，z ) = m a x ， 歹) l j ，七j 6 1 d e g x q ( x ，y ，名) 全d e g o ，o 1 q ( z ，y ，z ) = ，m a x ， 七) i l j ，膏) 6 1 e l k ，引：f i x ，y 】中y 的次数不超过l 的多项式组成的集合 e l i x ，y ，z 】：f z ，y ，z 中z 的次数不超过己的多项式组成的集合 第二章表单解码已有的重要理论与算法 2 1s u d a n 算法 经典的解码方法“最大似然解码”：给定一个向量s f n ，找一个码字c 够，使c 到8 的 汉明距离不超过7 - ，如果够是7 纠错码，这样的码字存在的话，肯定是唯一的。这种解码方 法固然非常有效，但也有缺点，那就是在有些情况下不能解码，如最小距离为2 时，而且 解码受纠错界限制，对于超出纠错界的情形无法纠错。 在1 9 9 7 年，m a d h u s u d a n 在前人工作的基础上发现了一种能够解决超过经典纠错界 的r s 解码算法( 见【1 0 】) ，两年后，g u r u s w a m i 与s u d a n 又对s u d a n 的算法做出了重大改 进，使得这种解码方法几乎能适应于所有的r s 码。这种解码方法就是表单解码，下面我 们详细阐述s u d a n 算法中所提及的构造和分解问题。 问题1 ： 输入：一个有限域f ；礼组不同的数组 ( 甄，玑) ) 饕l f f ；整数卿。 输出：- ；歹a j 函数，：f f 满足： ( 1 ) ，( z ) 的次数不超过d 。 ( 2 ) m ：f ( x i ) = 玑) l 。 算法1 ： 卓输入：n ，d ，； ( z 1 ，y 1 ) ，( z 。，鼽) ) ， 1 ，木参数f ，m 随后确定宰， 2 找到任意函数q ：f 2 一f 满足： d e g l ，d q ( x ，y ) m + l d v i n 】，q ( 戤，鼽) = 0 ， q o 3 将q 分解成不可约因子的乘积。 4 输出所以满足下面条件的多项式，： ( y f ( x ) ) l q ( x ，鲈) ， m ：，) = 玑 l t 自然地，我们希望把这个问题推广到多元的情形。 问题2 ： 输入：一个有限域f ，hcf ，一个函数，：日k _ f ，整数与d 。 输出：一列函数，：f o f 满足： ( 1 ) ，( 盒) 的次数不超过d 。 ( 2 ) ，i 盒h ：f ( x ) = ，( 圣) ) i 之t 。 算法2 ： ，幸输入：d ，t ，七；hcf ； ，( 圣) ) 量h 术 ，产参数2 ，m 随后确定$ ， ，查找任意q ：f 1 叶f 满足： d e g l ，1 ，d q ( 圣，y ) m + l d 4 r s 码表单解码与多元插值分解算法 v 宕日七，q ( 岔，7 ( 2 ) = 0 q 0 ，把q 分解成不可约因子的乘积。 ，输出所有满足下列条件的多项式，： ( y 一，( 圣) ) i q ， m ：f ( x i ) = f 。( 窑) ) i t 对于前一个问题已经有很多人做了很多工作。下面我们主要介绍对于前一个问题的 许多重要算法。 2 2 表单解码的g s 算法 距1 9 9 7 年，s u d a n 发表的有关表单解码的开创性论文两年后，g u r u s w a m i 与s u d a n 共同 对s u d a n 原始算法进行了重大改进，使得新的算法几乎能够适应于任意纠错界下的r s 码， 新的算法被成为g s 算法( 见 4 】) 。 下面我们介绍g s 的主要内容。在定义了加权次数的情况下有： 输入：礼，k ，t ， ( 毛，玑) s t e p0 ：计算参数nf 如下： r t 1 礼嚷。 掣 特别地，设 r 全l + k n + x 纠k 2 【n 2 一+ 尤4 n ( j t 2 - k n ) j z 全r t 一1 s t e pl ：构造一个多项式q ( x ，可) 满足： d e g l ，t ，( z ，y ) l 即要求出q ( z ，! ，) 的系数 【，j 2 ) j 1 j 2 2 0j l + v j 2 l 所以它满足如下条件： 1 ) ，至少有一个吗。，j 。不为0 。 2 ) ，对m ，若q ( ) = q ( x i ，玑) ，那么q ( ) 的所有次数不超过r 的单项式的系数为o ，即 当l n j ，坳l ，j 2 0 ，s tj l + j 2 r 时，有 a ( o 血全c j l c i j 2 _ 彳，五巧嘶谚嘞= o 中山大学硕士毕业论文 5 s t e p2 ：输出满足下列条件的多项式p r m ： ( y p ( x ) ) l q ( x ，可) ， d e g p ( x ) k ， m ：p ( x i ) = 计i t 2 3 m c e l i e c e 的工作 2 0 0 3 年，m e e l i e c 在k & t e r 与r o t h r u c k e n s t e i n 等人工作的基础上，对g s 算法进行了重 新阐述，并改进了分解算法计算终止的条件。 下面我们重点介绍插值定理的k 6 t t e r 算法( 见【8 】) ，分解定理会在第五章提及，故在此 不详细叙述。 首先，定义一种二元单项式全序关系，那么按任意确定的单项式序关系 咖o ( z ，y ) l ( z ，y ) 通过计算x k 与y l 的指数，确定，l m 等参数。此时任意二元多项式q ( x ，y ) 可写成 其中o ，不为0 ，c j ( x ，y ) 是q ( x ，秒) 的首项，记为l m ( q ) 。如果q 与尸的首项相同，日p l m ( q ) l m ( p ) ，那么记q o 其中a i e 如是单项式。为了做到这点，我们需要在下面的集合中定义一种线性序 m i x ，y ，z 】= z 。矿扩：i ，j ，k o ) 在这一节中，我们将介绍一种通常的单项式序关系。 在【l 】中提至w l m z ，y 上的一种二元单项式序关系” ”有如下性质： 1 ) ，若a l b l ，a 2 6 2 ，则( n l ，a 2 ) ( b l ，6 2 ) 。 2 1 ，关系” ”是一种全序，即如果a 和b 是不同单项式，则要么a b ，要么b a 。 3 ) ，若a b r c n 2 ，则a + c b + c 。 我们希望在m z ，y ，z 1 中定义具有类似性质的序关系。事实上，存在多种单项式序关 系，但对我们来说最重要的一类就是单项式加权次数序关系。 定义3 1 1 对于权数u = ( u ，u ，w ) n 3 ，单项式a i , j ，七y j z 的u 加权次数为i u + j v + k w 。而多项式q ( z ，y ，z ) = 协，七a i , j ，y j z 七的u 一次数定义为其有限个单项的u 一次数的 最大者，记为d e g u q ( x ，y ，z ) ，简称为u 一次数。 若我们通过加权次数来给m i x ，y ，z 】赋序，如果d e 钆砂( z ，y ，z ) d e g 。咖7 ( z ，y ，z ) ，则 称咖( z ，y ，z ) ( z ，y ，z ) 。通过这种方式，我们定义了一种多项式偏序，但由于不具有可 比性，所以不是全序。下面我们来定义单项式全序关系。 定义3 1 2 u = ( “，v ，伽) 字典序定义如下： z 1 矿l z 七1 x i 2 矿2 z k 2 如果满足下列任一条件： 1 ，u i x + v j l + w k l u i 2 十嘞+ w k 2 2 ，u i l + 巧1 + w k l = u i 2 + 巧2 + w k 2 ，且u i l + 力l u i 2 + 叨2 3 ，u i l4 - 巧l + w k l = u i 2 - 4 - v j 2 + w k 2 ，u i l4 - 巧1 = u i z + 巧2 ，且i l i 2 。 类似地，只要将加权字典序定义中的不等号反转，就定义了加权逆字典序。以后我们分别 称加权字典序，加权逆字典序为u 一字典序，u 一逆字典序。 7 8 r s 码表单解码与多元插值分解算法 例3 1 对于任意的一种单项式字典序，我们有：x y z x 2 y z 。对于( 1 ，1 ，2 ) 逆字典 序，z 4 x 3 y x y z 。 按u 一字典序，m i x ，y ，z 】中的单项式可以按顺序排列起来： 1 = o ( z ，y ，z ) 咖1 ( z ，y ，z ) 2 ( z ，y ，z ) 对应于这种序关系，f i x ，y ，z 】中的任意非零多项式都可以唯一地表达成 ， q ( x ，y ，z ) = 芝：咖x ，y ，z ) j = o 其中印f ，a j 0 。正整数，称为q ( x ，y ，z ) 的秩，对应的单项式加( z ，y ，z ) 称为q ( z ，y ，z ) 的 首项。我们将它们分别记为r ( q ) = j ，l m ( q ) = c j ( x ，y ) 。在f i x ，y ，z 】中，关系l m ( p ) = l m ( q ) 是一种等价关系，我们将其记为p 三q 。那么我们可以称尸 q 时，意思就 是l m ( p ) l m ( q ) 。通过这种方式，我们把单项式集中的全序 转变成f i x ，y ，z 】中的偏 序。通过上述等价关系作用于f i x ，y ，z 上，我们得到一个由等价类组成的集合，关系” ”此时就变成该集合中的全序。 在加权序关系的情形下，首项咖的加权次数被称为q ( x ，y ，z ) 的加权次数，记为d e g 。q 。 从而， d e g u q ( x ，y ，名) = m a x d e g u 西( x ，y ，z ) ：a j o 那么u 一次数函数有如下基本性质： d e g u o = 一o o d e g , , ( p q l = d e g u p + d e g u q d e g , 。( p + q ) m a x ( d e g , p ，d e a 。q ) 如钆( p4 - q ) = m a x ( d e g 。p ，如鼬q ) ，l m p l m q 如果咖( z ，y ，z ) 矽1x ，y ，z ) 是一个确定的单项式序关系，那么任意= k m i x ，y ，z 】( 对某个k ) ，我们称k 为的指数，记为i n d ( ) = k 。 我们将看到在( 1 ，1 ，v ) - 逆字典序中，i n d ( y 耳) 与i n d ( z l ) 非常重要，所以我们引进新 的记号 a ( k ，u ) 垒i n d ( y k ) b ( l ，u ) 垒i n d ( z l ) 在本文以后章节中，若无特别说明，a ( k ，u ) ，b ( l ，可) 都是指在( 1 ，l ， ) 一逆字典序下的取得 的。如果我们把z ，y ，z 分别看作是在三维笛卡儿垂直坐标系各坐标轴上，那么数字a ( k ，u ) 在 出现在y 一轴上，即t = 0 ，k = o ；同理，b ( l ，u ) 出现在z 一轴上，即i = o ，j = 0 。注意 到可k 是所有( 1 ，1 ，v ) - 力h 权次数等于k 的项中的第k + 1 项，z l 是所有( 1 ，1 ，t ，) 一加权次数等 于l u 的项中的最后一项。所以 a ( k ，u ) = i ( i ，歹，) ：i + 歹+ v k k ) l - 4 - k b ( l ，口) = i ( i ，j ，k ) ：iq - j - + - v k n v j - 1 中山大学硕士毕业论文 9 定理3 1 1 对f 0 ，令r = k ( m o d v ) ，则 、 ( k 一1 ) ( 1 + u ) r + 4 r + 4 七a ( k，u ) = 竖型尘掣竺竺 b ( l ，u ) ：型盐绰塑型 证明 f l j b ( l ， ) = i ( i ，j ，k ) ：i + j + v k l v i lo - f f f 得 b ( l ，u ) = ( 1 ( i ，j ，k ) ：i + j + v k ( l 一1 ) u ) i 一1 ) + i ( i ，j ，k ) ：( l 一1 ) u + 1 i + j + v k l v ：b ( l 一1 ，u ) + 竺丝芸型l + 1 又由于 故有 = b ( 。，u ) + 丛竺手型( l + ( l 一1 ) + + 1 ) + l l ( v ( 1 + u ) ( 1 + ) + 4 ) 4 b ( l ，v ) = i ( ，j ，k ) ：i + j + v k l v l 一1 = ( i ( i ，j ，k ) ：i + j + v k l v + 1 ) i + l v + 1 ) 一l u 一2 = a ( l v + 1 ， ) 一l 秽一2 令l v + 1 = k 得 证毕。 a ( l v + 1 ，口) = b ( l ，u ) + l v + 2 = 塑生掣仙+ 2 a ( k m = 坠业竽? 坐 3 2 三元多项式的零点与多重零点 口 上一节里，我们讨论了多项式的加权次数与序关系，在本节中，我们将继续讨论多项 式的性质，而重点在于多项式的零点和多重零点。 若q ( z ，y ，z ) f x ，y ，名】，且q ( q ，7 ) = 0 ，那么我们就称q 在( q ，p ，y ) 处有零点。 定义3 2 1 我们称q ( x ，y ，z ) = 谢，知a i ，j ，k x 矿f i x ，可，z 】在( o ，o ，o ) 处有m 重零点， 并记为o r d ( q ：0 ，0 ，0 ) = m ，如果当i + j + k m 时，a i j ，七= 0 ，即在q ( z ，y ，z ) 中没有次数小 于m 的项。类似地，我们称q ( z ，y ，z ) 在( o l ，p ，7 ) 处有m 重零点，并记为卯d ( q ：o t ，p ，y ) = m ， 如果q ( x + a ，耖+ p ，z + 7 ) 在( o ，0 ，o ) 处有m 重零点。 例3 2 令q ( z ，y ，z ) = z 2 y 2 z + x 2 y z + x y 3 2 2 ，那么q 在( o ，0 ，o ) 有三重零点。类似 地，q ( x ，y ，z ) = ( z a ) 2 ( 一p ) 2z - 7 ) + ( z q ) 2 ( y p ) ( z 一，y ) + ( z 一口) ( y p ) 3 ( z 一7 ) 2 在( o r ，p ，y ) 处有三重零点。 1 0 r s 码表单解码与多元插值分解算法 为了计算o r d ( q ：o l ，p ，y ) ，我们需要将q ( x + q ，y + 卢，z + ，y ) 写成如下形式： a i 囊k x 矿， i , j 七 根据哈塞( h h a s s e ) 8 的结论，我们有如下定理。 定理3 2 1 如果q ( z ) = t a i x f m ，那么对任意q f ，我们有 q ( x + a ) = q ，( 口) 这里g ( z ) g ( z ) = c t a t x 卜 它被称为q ( z ) 的r 次哈塞导数。注意到 g ( 口) = c o e f a r q ( x + 口) = c $ 。a i a 扛r 当f 的特征为。时，q ，( q ) 就是q ( z ) 的泰勒展式矿的系数，即 训牡寺刍) 推论3 2 1 q ( z ) = q r ( q ) 一口) r 0 定理3 2 2 令q ( z ，y ，z ) = i d , ka i d ，七矿f i x ，y ，z 】。那么对任意( a ，p ，7 ) f 3 我们有 q ( z + 口，y + p ，z + 7 ) = q r t ( 口，7 ) z r y 8 名。， r ，s ，t 其中 q 拍t ( z ，y ，z ) = q r u 歹s u 七t 锄础z 扣r 矿一5 ， i , j 称为q ( z ，y ，z ) 的( r ，s ，亡) 哈塞导数。注意到当f 的特征为。时，q ( x + q ，y + p ，z + 7 ) = tq 柏t ( 口，p ，7 ) 矿y 8 z 。就是q 的泰勒展开式，因为当f 的特征为。时： t ( 删，z ) 2 赢赫d r t q ( 舢，z ) 1+ 8 + 证明应用二项式定理，将q ( x + q ，y + p ，z + ，y ) 展开得 q ( x + q ，y + z ，z + 7 ) = o “七( z + q ) ( 可+ p ) j ( z + ，y ) 七 i ，j ，后 = a i , m ( q 矿吖) ( q 旷叫) ( 嚷z 。7 。) = ( q v r 叶v $ u 肚t 私叶伊一3 ，y ) 口 中山大学硕士毕业论文 推论3 2 2 q ( z ，y ，z ) = 钆，tx - 口) 7 ( y 一) 5 ( z 一7 ) r ，s ，t 推论3 2 3 多项式q ( z ，y ，z ) 在( q ，p ，7 ) 处有m 重零点的充分必要条件是当o r + s + t m 时 q ， t ( 口，7 ) = 0 证明 由定义，o r d ( q ：口，p ，y ) m 当且仅当心 4 - 口，y + p ，z + ，y ) 】在( o ，0 ，o ) 处 有m 重零点。但由定理3 2 2 ，q ( x + 口，y + p ，z + 7 ) 在( o ，0 ，o ) 处有m 重零点等价于：当o 3 3 插值定理与分解定理 在这一节里，我们陈述和证明两个g s 算法中的插值定理与分解定理。 3 3 1 插值定理 假设对任一口f ，对应一个非负整数m ( q ) ，我们要求构造一个次数尽可能低的多 项式，( z ) 使其在任意q f 处有m ( q ) 重零点。显而易见，满足上述条件的解是 m ) = ( z a ) 吣) ， q f d e g f ( x ) = m ( a ) q f 我们关心的问题是：v ( 口，成，y ) f 3 ，对应某个正整数m ( 口，p ，7 ) ，构造一个次数尽可 能低的多项式q ( x ，y ，z ) 满足 o r d ( q ：a ，p ，7 ) = m ( n ，p ，7 ) 下面我们证明满足条件的非零多项式是存在的，并给出该多项式次数的上界。 定理3 3 1 ( 插值定理) 令【m ( q ，p ，7 ) ：( q ，p ，y ) f 3 ) 是给定的重数函数，加 砂l 是任一单项式序关系。那么存在一个如下形式的非零多项式q ( z ，! ，z ) c q ( z ，y ，z ) = a i 砂i ( x ，y ，z ) i = 0 满足o r d ( q ：q ，7 ) = m ( 口，p ，y ) 其中 c ：f ! 竺( 竺! 壁：1 2 ! ! ( 竺! 竺! 壁! ! ! 1 2 竺! 竺：垒：1 2 ，6 o 口1 。 口 n = 、，7 矽 n ，rl t 南nq 时m + s + r r s 码表单解码与多元插值分解算法 证明我们已知，o r j ( q ：o l ，p ，7 ) = 仇( q ，p ，7 ) 的充分必要条件是 q ，s ，( 口，p ，y ) = 0 ，0 r + s + t m ( a ，p ，一y ) 当7 = o 时，( s ，) 共有嚷( a ，芦，7 ) + 1 种选择： 当_ r = 1 时，( s ，) 共有嚷( 口，口，7 ) 种选择； 当r = m ( 口，p ，7 ) 一1 时，( s ，) 共有喏种选择。那么可知满足条件o r + s + t c ( n ，m ) ) l m ( n ，尼) 全m a x l ：b ( l ，u ) c ( n ，m ) ) b ，g s 算法：构造一个三元多项式如下 其中 咖l 是( 1 ，1 ，u ) 一逆字典序，q 满足：o r d ( q ：o l i ，屈，m ) = m i 。输出： ( x ，矽) f i x ，胡：( z f ( x ，u ) ) l q ( x ，y ，z ) ) 在给出关于输出列的精确结论前，我们先介绍一些必要的知识。 若 j q ( x ，舭) = a i 咖t ( z ，y ，z ) i = 0 那么由u 次数的性质，有 d e g u q m a x d e g u i ：i = 0 ，1 ，) 引入记号： d ( “，口，w ，j ) = m a x d e g 。i ：i = 0 ，1 ，j ) 那么 d e g u ，州q d ( u ，v ，w ，j ) 若 a = 妣：k = 0 ，1 ，) 其中。南n ，a 知 a k + 1 ，k = 0 ，1 ，。那么对任意z n ，存在k 使 a k z a k + l 数k 被称为x 在a 中的秩，记为r a ( x ) 。则 r a ( x ) = m a x k ：a k z ) 定理3 4 1 记r a ( c ) = l ，输出列中包含满足下列条件的多项式f ( z ，可) ： 1 ) ， d e 9 1 ，i ( f ) u z 咖叼 嘶触 l | zq 中山大学硕士毕业论文 2 ) ， k ( f ，y ) k m ，c 【a l + l ，a l + 1 ) 或 k ( s ，7 ) k k + l ，c a l ，a l + l ) 丽且输出多项式的数目不超过m 。 为了证明这个定理，我们需要两个引理。若 那么由“次数的性质，有 d e g 埘q m a x 如吼咖：i = 0 ，1 ，j ) 荨| 入记号： d ( u ，u ，w ，j ) 一m a x d e g 叫i ：t = 0 ，1 ，j ) 那么 d e q _ l t 双仰q d ( u ，移，w ，j ) 若 a = 钕：k 一0 ，l ， 其e e a k 毯n ，a k r a ( c ) 且 d e g l ，x ( y ) 钉 则它必是q ( x ，y ，z ) 的z 一根。也就是说，若 k ( y ，y ) 1 + 【r a ( c ) m j j 再由上述条件2 ) 与引理4 4 2 ，n f ( x ，可) 在输出列中。 因为q 的z 一根的数目不超过d e g 。q ( z ，y ，z ) ，而咖：q ( z ，y ，z ) l m ，故输出多项式的 数目不超过己m 。 口 3 5 插值定t 剿j k s t t e r 算法 在本节里，我们将以三元多项式为例详细叙述多元情况下插值问题的k o t t e r 算法，二 元的情况见 9 1 ，【1 2 。 通常而言，插值问题就是构造一个具有极小( 1 ，1 ，u ) 次数三元多项式q ( z ，y ，z ) 满足一 系列限制条件 q 即，t ( q ，p ，7 ) = 0 其中( r ，s ，t ) n 3 a ( a ，p ，1 ) f 3 。那么它就变成一个映射 q ( z ，y ，z ) hq r 禹( a ，p ，7 ) 它是一个从f k ，y ，z n f 上的线性函数。所以为了解决上述的插值定理，我们可以考虑更 一般情况下的插值问题：一个三元多项式q ( z ，y ，彳) 具有极小的加权次数并且满足下列约 束条件 o , o ( x ，y ，名) = 0i = 1 ，2 ， 其中每个现是一个线性函数。 3 5 1f x ，y ，名】上的线性函数 一个映射d ：尸k ，y ，z 】hf 被称为一个线性函数如果 d ( a p + z o ) = a d ( p ) + f l d ( q ) 对所有只q f x ，y ，z 】以及任意口，p ，7 f 。对我们来说，重要的例子就是求哈塞导数的 值： q ( x ，y ，z ) hq 即，t ( 口，p ，y ) 其中( n8 ，t ) n 3 和( 口，7 ) f 3 是固定的。 给定一个单项式序关系： 如( z ，y ，z ) q ，由表达形式【p ，q d = d ( q ) p d ( p ) q 可 得l m ( 只q 】d ) = l m ( p ) ，从而r ( 【尸：q o ) = r ( p ) 。 口 3 5 2 插值问题 令兄ky ，z l 表示f p ，y ，z 】中z 的次数不超过l 的多项式组成的集合，即集合中元素有 如下形式 q ( x ，y ，z ) = q k ( x ，) k = 0 其q b q k ( x ，y ) f i x ，y 】。黼u r l z ，y ，z 】是一个f i x ，胡一模，后面我们会看到这在k 6 t t e r 算 法中是必要的。 令d l ，d c 是c 个定义在见【z ，y ，z 】上的线性函数，厩，是其对应的核，即 k = q ( z ，y ，z ) e lx ，y ，z 】：d i ( q ) = o 为了讨论的方便，我们引进累积核的概念。累积核丽，瓦定义如下： 蔚= 兄p ，z 】 瓦= i i - x i l k l c 孑 耖 z 咖吁 j 芦 l l z y z q 如 j 汹 i i q d r s 码表单解码与多元插值一分解算法 丽= k 1 n n o d l , o d 1 , 1 - ) 中山大学硕士毕业论文 其中肌，七是瓦n 鼠的极小元素。) 那么k 6 t t e r 算法的输出多项式 q o ( x ，y ，z ) 2 。m ，且r ( g i + l , k ) = r ( ( z + y ) g i ，七) ，所以矶+ 1 ，k 鼠，从而仇+ 1 ，k 瓦石n & 接下来证明仇+ 1 知是t i i + xn 鼠的极小元。如果它不是极小的，那么存在h k i + l ( 1 瓯且h g i + 1 加那么h 凰n 瓯，h 。由于r ( g i + 1 ，k ) = r ( ( z + ) ，) = r ( x f ) = r ( y f ) ，故h 三，。 通过乘以某一常数，我们总可以使h 和，的首项系数相等。下面考虑多项式f 7 = h 一，明 显，尬，且， h 三，由于d 件1 ( ) = 0 ，d 件l ( ，) 0 ，那么d 件1 ( 1 ) 0 。 总之，如果仇+ 1 彪不是瓦i n 瓯中极小元，我们可以构造一个非零多项式，7 满足 f 、k t k 件1 ，。 ， 但是这与，是瓦一瓦石中极小元矛盾，故g i + l , ，知是必是瓦石n 瓯的极小元。 口 3 5 4伪代码与例子 三元情形下k t i t t e r 算法的伪代码 b e g i n ( 给定l ，( n ) 星1 ) f o r j = 0 t ol g ：= z j f o ri = 1t 0c f o rj = 0t old o j ：一- - - d t ( g j ) j ：= d ：j o j g 歹。：= a r g m i n g j ：岛o ) ，：= 所；：= j f o 即jd o 0 j + ) 9 1 ：= g j 一 e l s e ( 歹= j ) 彩：= 【( z + y ) 门一d i ( x + y ) ，】， q o ( z ，y ，z ) ：= 1 1 1 i n 冬o 毋( z ，z ) ， e | n d 一生坐盔学硕士毕业论文 2 1 例3 3 令f = g f ( 8 ) ，其本原元，y 满足：7 3 = ，y + 1 。下面我们用k 6 t t e r 算法构造 一个在( 1 ，1 ，3 ) 一逆字典序中极小的三元多项式q ( z ，y ，z ) 且满足：o r d ( q ：1 ，1 ，- y ) 1 ， 和o r d ( q ：1 ，7 ，y 6 ) 2 。那么q 有五个线性约束条件： d l 旧) = q o ，0 ，o ( 1 ，1 ，7 ) = 0 d 2 ( q ) = q o ，0 ，o ( 1 ，7 ，7 6 ) = 0 d a ( q ) = q 1 ，0 ，o ( 1 ，y ，矿) = 0 d 4 ( q ) = q o ，1 ，o ( 1 ，y ，7 6 ) = 0 d s ( q ) = q o ，0 ，1 ( 1 ，y ，7 6 ) = 0 按k t i t t e r 算法求解： ( 1 ) ，初始化，踟= o n l ， g o ：= z o = 1 ，9 1 ：= z 1 = z ( 2 ) ，对i = 1 至i j 5 循环， ，i = i ，a o ：= d l ( g o ) = 1 ，a 1 ：= d l ( 9 1 ) = ，y ， ，= o ，1 ) ，歹+ ：= 0 ，：= g o = l ，：= o = l j = 1 歹+ g l ：= a g l 一1 ，= z 一，y j = 0 = j 。 g o ：= ( + 可) ，) 一d l ( ( z + y ) f ) f = z4 - y ，i = 2 ，a o ：= d 2 ( g o ) 7 3 0 ，a l ：= ，y 6 一一y = 0 ， j = o 】- ，j + ：= 0 ，：= g o = z + y ，a ：= o = 1 3 j = 0 = j g o ：= ( ( z + ) 厂) 一d 2 ( ( x + ) 厂) 厂= 一7 3 ( z - i - y ) ( z + y 一7 3 ) ，i = 3 ，a o ：= d 3 ( g o ) = ，y 6 0 ，1 ：= d 3 ( 9 1 ) = 0 ， j = o ) ，j ：= 0 ，：= ，y 3 ( z + y ) ( z + y 一，y 3 ) ，：= 7 6 j = 0 = j + g o ：= , 7 2 ( z + y ) ( z + y 一，y 3 ) 2 ，i = 4 ，a o ：= d 4 ( g o ) = 0 ，a 1 ：= d 4 ( 夕1 ) = 0 ， ，i = 5 ，a o ：= d s ( g o ) = 0 ，a 1 ：= d 5 ( 9 1 ) = 1 0 ， j = 1