计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2005年
4期
690-696
,共7页
有限自动机%弱可逆%延迟%分解%输出权
有限自動機%弱可逆%延遲%分解%輸齣權
유한자동궤%약가역%연지%분해%수출권
研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径.从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题,首先证明了其可分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为1.其次,在获得一类不可分解出延迟元的弱可逆有限自动机的基础上,构造出一个反例,否定回答了鲍丰在1993年提出的一个公开问题.同时给出了二元严格延迟τ步强连通弱可逆有限自动机可分解为一个严格延迟τ-1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自动机的一个充分条件.
研究弱可逆有限自動機的分解可以為分析有限自動機公開鑰密碼體製的安全性提供一種重要途徑.從輸齣權的角度研究瞭n元延遲τ步弱可逆有限自動機M的分解問題,首先證明瞭其可分解為一箇延遲0步弱可逆有限自動機和一箇τ階延遲元噹且僅噹M的所有狀態的長τ輸齣權為1.其次,在穫得一類不可分解齣延遲元的弱可逆有限自動機的基礎上,構造齣一箇反例,否定迴答瞭鮑豐在1993年提齣的一箇公開問題.同時給齣瞭二元嚴格延遲τ步彊連通弱可逆有限自動機可分解為一箇嚴格延遲τ-1步弱可逆有限自動機和一箇嚴格延遲1步弱可逆有限自動機的一箇充分條件.
연구약가역유한자동궤적분해가이위분석유한자동궤공개약밀마체제적안전성제공일충중요도경.종수출권적각도연구료n원연지τ보약가역유한자동궤M적분해문제,수선증명료기가분해위일개연지0보약가역유한자동궤화일개τ계연지원당차부당M적소유상태적장τ수출권위1.기차,재획득일류불가분해출연지원적약가역유한자동궤적기출상,구조출일개반례,부정회답료포봉재1993년제출적일개공개문제.동시급출료이원엄격연지τ보강련통약가역유한자동궤가분해위일개엄격연지τ-1보약가역유한자동궤화일개엄격연지1보약가역유한자동궤적일개충분조건.
