Feedback with Carry Shift Registers

Pseudorandom number generators | Stream ciphers | Cryptographic algorithms

In sequence design, a Feedback with Carry Shift Register (or FCSR) is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in . FCSRs have been used in the design of stream ciphers (such as the F-FCSR generator), in the cryptanalysis of the summation combiner stream cipher (the reason Goresky and Klapper invented them), and in generating pseudorandom numbers for quasi-Monte Carlo (under the name Multiply With Carry (MWC) generator - invented by Couture and L'Ecuyer,) generalizing work of Marsaglia and Zaman. FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer . Associated with the output sequence is the N-adic number The fundamental theorem of FCSRs says that there is an integer so that , a rational number. The output sequence is strictly periodic if and only if is between and . It is possible to express u as a simple quadratic polynomial involving the initial state and the qi. There is also an exponential representation of FCSRs: if is the inverse of , and the output sequence is strictly periodic, then , where is an integer. It follows that the period is at most the order of N in the multiplicative group of units modulo q. This is maximized when q is prime and N is a primitive element modulo q. In this case, the period is . In this case the output sequence is called an l-sequence (for "long sequence"). l-sequences have many excellent statistical properties that make them candidates for use in applications, including near uniform distribution of sub-blocks, ideal arithmetic autocorrelations, and the arithmetic shift and add property. They are the with-carry analog of m-sequences or maximum length sequences. There are efficient algorithms for FCSR synthesis. This is the problem: given a prefix of a sequence, construct a minimal length FCSR that outputs the sequence. This can be solved with a variant of Mahler and De Weger's lattice based analysis of N-adic numbers when ; by a variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm. If L is the size of the smallest FCSR that outputs the sequence (called the N-adic complexity of the sequence), then all these algorithms require a prefix of length about to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose N-adic complexity is low should not be used for cryptography. FCSRs and LFSRs are special cases of a very general algebraic construction of sequence generators called Algebraic Feedback Shift Registers (AFSRs) in which the integers are replaced by an arbitrary ring R and N is replaced by an arbitrary non-unit in R. A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book. (Wikipedia).

Application: Linear Feedback Shift Registers! C Tutorial 9.2

An application of bitwise operators

From playlist C Tutorial

What Is Feedforward Control? | Control Systems in Practice

A control system has two main goals: get the system to track a setpoint, and reject disturbances. Feedback control is pretty powerful for this, but this video shows how feedforward control can make achieving those goals easier. Temperature Control in a Heat Exchange Example: http://bit.ly

From playlist Control Systems in Practice

Fuzzy control of inverted pendulum

Fuzzy control of inverted pendulum, State-feedback controller is designed based on T-S fuzzy model with the consideration of system stability and performance.

From playlist Demonstrations

Feedforward control Lecture 2019-03-19

From playlist Lectures

Stream Ciphers (Contd...2)

Cryptography and Network Security by Prof. D. Mukhopadhyay, Department of Computer Science and Engineering, IIT Kharagpur. For more details on NPTEL visit http://nptel.iitm.ac.in

From playlist Computer - Cryptography and Network Security

Lecture 3D - Lifting with a Pulley

Here is what pulleys are good for. They can apply the tension force multiple times for a "mechanical advantage". In this problem we go through the tensions and weights, and think about the effect on motion.

From playlist PHYS 125 | Forces

Stream Ciphers

Cryptography and Network Security by Prof. D. Mukhopadhyay, Department of Computer Science and Engineering, IIT Kharagpur. For more details on NPTEL visit http://nptel.iitm.ac.in

From playlist Computer - Cryptography and Network Security

Sensors: Direct Sensing - A Level Physics Part 2

Part 2 of 2: What a direct sensor is, how to incorporate it in a circuit such that it can cause action to happen when external circumstances (light levels, temperature, pressure) change.

From playlist A Level Physics Revision

Feedback to Empower Students

Feedback is critical for learning, but not all feedback is created equal. Consider evaluative feedback, in which a student is told they are right or wrong. This can be easiest to give but frustrating or unhelpful to receive. In this session, we’ll consider alternatives, especially ones tha

From playlist Webinars While We're Away

History of Science and Technology Q&A (February 8, 2023)

Stephen Wolfram hosts a live and unscripted Ask Me Anything about the history of science and technology for all ages. Find the playlist of Q&A's here: https://wolfr.am/youtube-sw-qa Originally livestreamed at: https://twitch.tv/stephen_wolfram If you missed the original livestream of

From playlist Stephen Wolfram Ask Me Anything About Science & Technology

25c3: An introduction to new stream cipher designs

Speaker: Tor E. Bjørstad Turning data into line noise and back Even with "nothing to hide", we want to protect the privacy of our bits and bytes. Encryption is an important tool for this, and stream ciphers are a major class of symmetric-key encryption schemes. Algorithms such as RC4 (us

From playlist 25C3: Nothing to hide

The role of controller gain

From playlist CPB Theme 2

19. Phase-locked Loops

MIT Electronic Feedback Systems (1985) View the complete course: http://ocw.mit.edu/RES6-010S13 Instructor: James K. Roberge License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT Electronic Feedback Systems (1985)

ELEC2141 Digital Circuit Design - Lecture 26

ELEC2141 Week 10 Lecture 1: Computer Design Fundamentals

From playlist ELEC2141 Digital Circuit Design

Lec 13 | MIT RES.6-008 Digital Signal Processing, 1975

Lecture 13: Network structures for finite impulse response (FIR) systems and parameter quantization effects in digital filter structures Instructor: Alan V. Oppenheim View the complete course: http://ocw.mit.edu/RES6-008S11 License: Creative Commons BY-NC-SA More information at h

From playlist MIT RES.6-008 Digital Signal Processing, 1975

CPU flags register

Share your requests for future video topics here: https://www.reddit.com/r/beneater/comments/88m9jy/ben_eater_video_suggestions/ Intel x86 developers guide (4800 pages!): https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf#page=80 More 8-bit compu

From playlist Building an 8-bit breadboard computer!

Stanford Lecture: Donald Knuth - "MMIX: A RISC Computer for the New Millennium" (February 9, 1999)

February 9, 1999 Professor Knuth is the Professor Emeritus at Stanford University. Dr. Knuth's classic programming texts include his seminal work The Art of Computer Programming, Volumes 1-3, widely considered to be among the best scientific writings of the century.

From playlist Donald Knuth Lectures

Black Hat USA 2010: Attacking Phone Privacy 2/5

Speaker: Karsten Nohl Our most popular phone technologies use decade-old proprietary cryptography. GSM's 64bit A5/1 cipher, for instance, is vulnerable to time memory trade-offs but commercial cracking hardware costs hundreds of thousands of dollars. We discuss how cryptographic improveme

From playlist BH USA 2010 - PRIVACY

Posture-based game controller

I quickly built a game controller to test the idea of generated game inputs from the player's posture (shift in center-of-gravity). This controller is built from a digital bathroom scale and an XBox 360 controller. I used an opamp to convert the bathroom scale's sensor input to a thumbstic

From playlist Electronics

Apple 1 Replica - Retro Computer Festival 2017 - Part 1

David Williams shows us his Apple 1 Reproduction. Filmed at Retro Computer Festival 2017 at the Centre for Computing History.

From playlist Retro Computer Festival 2017

Feedback with Carry Shift Registers

Related pages