Theory and Application of Algebraic Feedback Shift Registers

代数反馈移位寄存器的理论与应用首席研究员：Andrew Klapper，University of Buckingham伪随机序列是数字通信和信息技术的基础。 它们用于流密码密码系统;蜂窝电话、GPS系统和卫星通信中的扩频系统;以及作为数字通信的纠错码中的码字。 大量的伪随机序列用于大型模拟，例如天气预测，反应堆设计，油井勘探，放射性癌症治疗，交通流量和金融工具定价。 在每种情况下，都需要具有特定性质的序列。 然而，用于有效生成伪随机序列的一般方法很少是已知的。 这项研究涉及大量伪随机序列的开发和分析，这些序列可用于密码学、编码理论和模拟等领域的各种应用。Klapper和M. Goresky提出了“带进位反馈移位寄存器”（FCSR），这是一类易于实现的伪随机发生器，它可以快速生成具有许多理想特性的伪随机序列。 这些后来被推广到代数反馈移位寄存器（AFSR）。 已经确定了FCSR和AFSR的许多基本性质。 本计画主要研究有关FCSR与AFSR序列的问题，包括：（1）设计合成器、前馈函数与时钟控制电路以产生密码安全序列;（2）设计快速且具良好统计特性的FCSR序列以应用于准蒙地卡罗（QMC）;（3）分析与设计几种新的AFSR序列产生器，并应用于串流密码与准蒙地卡罗（QMC）;（4）解决AFSR的寄存器综合问题;（5）开发基于AFSR序列的新的纠错分组码和卷积码族。

Theory and Application of Algebraic Feedback Shift RegistersPrincipal Investigator: Andrew Klapper, University of KentuckyPseudorandom sequences essential for digital communications and information technology. They are used in stream cipher cryptosystems; in spread spectrum systems in cellular telephones, GPS systems, and satellitecommunications; and as codewords in error-correcting codes for digital communication. Pseudorandom sequences of large numbers are used in large simulations for such applications as weather prediction, reactor design, oil well exploration, radiation cancer therapy, traffic flow, and pricing of financial instruments. In each case sequences with particular properties are needed. Yet few general methods for efficient generation of pseudorandom sequences are known. This research involves the development and analysis of a large supply of pseudorandom sequences for a variety of applications in cryptography, coding theory, and simulations.In 1994 A. Klapper and M. Goresky proposed "feedback-with-carry shift registers" (FCSRs), a class of pseudorandom generators which are easily implemented and which rapidly generate pseudorandom sequences with many desirable properties. These were later generalized to algebraic feedback shift registers (AFSRs). Many basic properties of FCSRs and AFSRs have been determined. This project addresses issues concerning FCSR and AFSR sequences including (1) design of "combiners", "feedforward functions", and clock-controlled circuits for the generation of cryptographically secure sequences, (2) design of fast and efficient FCSRs with good statistical properties for use in quasi-Monte Carlo (QMC), (3) analysis and design of several new AFSR generators with applications to stream ciphers and QMC, (4) solution of the register synthesis problem for AFSRs, and (5) development of new families of error correcting block and convolutional codes based onAFSR sequences.