Content deleted Content added
{{compu-prog-stub}} |
Citation bot (talk | contribs) Added series. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
||
| (11 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Infobox cryptographic hash function
| name = Toeplitz Hash
Line 20 ⟶ 19:
}}
The '''Toeplitz Hash Algorithm''' describes [[hash function]]s that compute hash values through [[matrix multiplication]] of the key with a suitable [[Toeplitz matrix]].<ref name="Krawczyk1995">{{cite conference|last1=Krawczyk|first1=Hugo|authorlink1=Hugo Krawczyk|title=New Hash Functions for Message Authentication|conference=EUROCRYPT '95|series=Lecture Notes in Computer Science|volume=921|year=1995|pages=301–310|issn=0302-9743|doi=10.1007/3-540-49264-X_24|doi-access=free}}</ref> The Toeplitz Hash Algorithm is used in many [[Network interface controller|network interface controllers]] for receive side scaling.<ref name="kernel-org-scaling">{{cite web|url=https://www.kernel.org/doc/Documentation/networking/scaling.txt|title=Scaling in the Linux Networking Stack|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522233520/https://www.kernel.org/doc/Documentation/networking/scaling.txt|archivedate=22 May 2014|url-status=live}}</ref><ref name="microsoft-ndis-rss">{{cite web|url=http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|title=Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522235610/http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|archivedate=22 May 2014|url-status=live}}</ref>
As an example, with the Toeplitz matrix <math>T</math> the key <math>k</math> results in a hash <math>h</math> as follows:
<!-- in python: import scipy as sc; T=sc.linalg.toeplitz([1,0,1],[1,1,0,1]); k=[1,1,0,0]; h=T.dot(k)%2; print('h =',h) -->
:<math>h = T\cdot k
= \begin{pmatrix}1 & 1 & 0 & 1 \\0 & 1 & 1 & 0 \\1 & 0 & 1 & 1 \\\end{pmatrix}
\cdot \begin{pmatrix}1\\1\\0\\0\\\end{pmatrix}
= \begin{pmatrix}0 \\1 \\1 \\\end{pmatrix}</math>
where the entries are bits and all operations are modulo 2. In implementations the highly redundant matrix is not necessarily explicitly stored.
==References==
| |||