资源描述：
《给定模最大周期乘同余序列的乘子确定》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1986年6月数值计算与计算机应用第2期*给定模最大周期乘同余序列的乘子确定李凤林(中国科学院计算中心)DETERMINATIONOFTHEMULTIPLIERSAOFMCSMPFORFIXEDMODULEM一LiFenglin“ti刀9Center,Acade滋ias动(CO附Pica)Abstraet,In5paPerwe,ystematieallyexplainhowtodeteinethemultiplier,aofa伽助multiPlieativeeongruentialsequeneeformaximumPeriod(粥【CSMP)forthofixed,,,moeal
2、aeoneeo,weeersaodulMP心兜rlyb鸽d止mthdin[13]fin61aJthmultiPlifoeexe.MCSMPfr恤fixedeomPldulMmo引言.a在给乘同余和混合同余序列的质量好坏与方法中参数(乘子)的选择有密切关系...,a的选择标准是:1;2使序列具有好的统计性质定模M下使序列达到最大周期关,当模M为素数幂时,a.当模M为复合模时,对混合于前者两种方法中的都较容易确定,习,。,同余序列根据其达最大周期M的充要条件定理[1,就可容易地定出全部乘子但对乘同余序列x。ax:o,伦,,三卜(mdM)~12⋯(1)“的确定却较复杂.〔1,31基于M的
3、各素因子之元根(对因子2‘为本原元)提供了求找部a的方法,。.1,3]的方法进一步推广,解决了确定全部分但仍不能确定出全部本文将【a.至于如何快速地求找。,,.的问题这是个算法问题我们准备在另文中讨论二、几个定义和预备定理为了本文的需要引人如下几个定义和定理,它们均可在有关数论书中见到..,定义。1,0<‘a,(M)~称满足4、M)~(M)为模M的最大周.当战,。价(M),a.期M)~称为模M之元根a,l,,a.定理L若(材)~则占(M)}币。f)(A旧表示A整除B)2.2,4,P’,2尸,p为.定理模M(>l)存在元根的充要条件是M一奇素数户,,。,1,,。,定理3.设为素数(P)~钾则‘‘·,,士l+户e,。pl+产e+,r,,1,()~(户)~P~2,8),‘1;p,,,1,土1其中当时2)当为奇素数时O妻1)这时括号中的由1代替.a,,定理4.若(M)~l则‘,一‘,,,!,l中(P)一(P一1)P当M~P》l5一‘,J。,。占(M)一<2当M~Z>2‘,J,,,.【2一当M~Z~l2,··、定理
5、a1,l‘m。:,mZ,,m,,。‘lil,2,,5.设(M)~M~{⋯}>(~⋯友),:,Z,,,a,,,a,,,a,序列(1)对模Mmm⋯。*的周期分别为占(M)占(。)⋯占(拼,)则··.占叼,al‘。占。:,a,,占m*,a()~{()⋯()}、‘,‘三M=2p(p为奇素数),根据定理1一4并注意到当!)2时有,,,,+‘,,,占(22一l)一吞(22一l)~2.a由如下定理6则确定.:。,21,t。Zq+l,定理6令()~即~则‘,a‘一,,‘一,a,当占(2)一2时有2个。士1+22t。土1+222宁+1,孕0,l,,2,一,~~()~⋯一l;,,a,一3,‘一3a,当
6、占(2)一2时有2个。,z。,,,,,,‘一‘~士1+2~士1+2(Zq+1)q~012⋯2一1;‘,。‘一e,‘一口。,当占(2)~2时有2个。~士1+Zet。士1+Ze2宁+l,宁~o,l,2,,2‘一口一,~()⋯一l;,,a,当占(2)~2时有,一,,了一{士1+22一1当‘>2,J,Z一1了一2;‘,a,4,,。.当占(2)~l时~1;当~o规定~0定理7.如果ap,。户-l一1,a,,>是奇素数之元根并且尸冬()则为P’的元根这里1,.冬表示不整除数值计算与计算机应用1986年8.。p,q,。+p一‘l,,1,定理为的元根如能找到一个使护冬((Pq)一)则对任何>a+P
7、q为尸之元根...a户,一‘定理9Pt之元根一定为之元根且尸本(砂一1)a,,ap一‘o,a户一‘,证明由定理条件知(户)一l故二l(md户)若户1(一l)不失一般,。p一,,z。,。,.性可设~l+P(zP)一1根据定理3有a‘p一‘,p‘一,,,。p‘一’‘,:,‘,,,~(1+户)~1+户(p:)~1。‘p一1)p,一,o·‘一,,一,,,ap一,.即二l(md户)、(户一1)户l((户一l》)矛盾故p冬(一l)下面证,a.。户,,as‘p,1+Pt,占,a,必
