Patent · US Active

Pseudorandom number generation with expander graphs

US7907726B2 · kind B2 · utility

6Cited by

1References

18Claims

0Family size

Assignee

Microsoft Corporation · US

Inventors

Kristin E. Lauter · Redmond, US
Denis X. Charles · Redmond, US
Eyal Goren · Nes Ziona, IL

Key dates

Filing date	Jan 19, 2006
Grant date	Mar 15, 2011
Priority date	—
Expiry date	Dec 7, 2028

Classification

Technology area (CPC H)Electricity
CPC primaryH04L9/0662
WIPO fieldDigital communication
WIPO sectorElectrical engineering

Abstract

Pseudorandom numbers may be generated from input seeds using expander graphs. Expander graphs are a collection of vertices that are interconnected via edges. Generally, a walk around an expander graph is determined responsive to an input seed, and a pseudorandom number is produced based on vertex names. Specifically, a next edge, which is one of multiple edges emanating from a current vertex, is selected responsive to an extracted seed chunk. The next edge is traversed to reach a next vertex. The name of the next vertex is ascertained and used as a portion of the pseudorandom number being produced by the walk around the expander graph.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.