Cryptanalysis of Linear Feedback Shift Registers: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== Problem Description== == Bounds Chart == 350px == Step Chart == 350px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/Factorial | | |- | rowspan="...")
 
No edit summary
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Cryptanalysis of Linear Feedback Shift Registers (Cryptanalysis of Linear Feedback Shift Registers)}}
== Description ==  


Find the shortest linear feedback shift register that can generate a given finite sequence of digits.


== Bounds Chart ==
== Parameters ==  
[[File:Cryptanalysis_of_Linear_Feedback_Shift_RegistersBoundsChart.png|350px]]


== Step Chart ==
$n$: size of input stream
[[File:Cryptanalysis_of_Linear_Feedback_Shift_RegistersStepChart.png|350px]]
 
== Table of Algorithms ==  
 
{| class="wikitable sortable"  style="text-align:center;" width="100%"
 
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference


== Improvement Table ==
{| class="wikitable" style="text-align:center;" width="100%"
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
|-
| rowspan="1" | Exp/Factorial
|
|
|-
|-
| rowspan="1" | Polynomial > 3
 
|
| [[Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers)|Berlekamp–Massey algorithm]] || 1969 || $O(n^{2})$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1054260 Time]
|
|-
|-
| rowspan="1" | Cubic
|}
|
 
|
== Time Complexity Graph ==  
|-
 
| rowspan="1" | Quadratic
[[File:Cryptanalysis of Linear Feedback Shift Registers - Time.png|1000px]]
|
|
|-
| rowspan="1" | nlogn
|
|
|-
| rowspan="1" | Linear
|
|
|-
| rowspan="1" | logn
|
|
|-|}

Latest revision as of 09:10, 28 April 2023

Description

Find the shortest linear feedback shift register that can generate a given finite sequence of digits.

Parameters

$n$: size of input stream

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Berlekamp–Massey algorithm 1969 $O(n^{2})$ $O(n)$? Exact Deterministic Time

Time Complexity Graph

Cryptanalysis of Linear Feedback Shift Registers - Time.png

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Cryptanalysis_of_Linear_Feedback_Shift_Registers&oldid=47738"