Cryptanalysis of Linear Feedback Shift Registers: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


No parameters found.
$n$: size of input stream


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 16: Line 16:
|-
|-


| [[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]
| [[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]
|-
|-
|}
|}

Revision as of 08:22, 10 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

Space Complexity Graph

Cryptanalysis of Linear Feedback Shift Registers - Space.png

Time-Space Tradeoff

Cryptanalysis of Linear Feedback Shift Registers - Pareto Frontier.png

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