Pseudorandom Number Generation with Expander Graphs
AssigneeMicrosoft Corporation
InventorsKristin Lauter, Denis Charles, Eyal Goren
Life of this patent
Estimating the term…
Abstract
Pscudorandom 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.
Claims20
A method comprising:
- selecting a next edge of an expander graph responsive to a seed chunk;
- traversing the next edge of the expander graph to determine a next vertex;
- and
- producing a pseudorandom number portion based on a name of the next vertex.
A device comprising:
- an expander graph having vertices that are interconnected by edges, each vertex connected by edges to at least two other vertices;
- an input seed;
- and
- a pseudorandom number generator that takes a walk over multiple vertices of the expander graph by traversing edges responsive to the input seed, wherein the pseudorandom number generator produces pseudorandom number portions based on the multiple vertices over which the walk is taken.
One or more processor-accessible media comprising processor-executable instructions that include a pseudorandom number generator that is adapted to generate a pseudorandom number using an expander graph having multiple vertices and interconnecting edges.
Dependencies are inferred from the claim text.