Published October 30, 2009 | Version v1
Journal article Metadata-only

Finding passwords by random walks: how long does it take?

Creators

  • 1. Dobrushin Mathematical Laboratory, Institute of Information Transmission Problems, Russian Academy of Sciences, Bolshoy Karetniy 19, Moscow GSP-4 101 447 (Russian Federation)
  • 2. Laboratory J-V Poncelet (UMI CNRS 2615), Independent University of Moscow, Bolshoy Vlasyevskiy Pereulok 11, 119002 Moscow (Russian Federation)

Description

We compare the efficiency of a deterministic 'lawnmower' and random search strategies for finding a prescribed sequence of letters (a password) of length M in which all letters are taken from the same Q-ary alphabet. We show that, at best, a random search takes two times longer than a 'lawnmower' search.

Availability note (English)

Available from http://dx.doi.org/10.1088/1751-8113/42/43/434016

Additional details

Identifiers

DOI
10.1088/1751-8113/42/43/434016;
PII
S1751-8113(09)22050-6;

Publishing Information

Journal Title
Journal of Physics. A, Mathematical and Theoretical (Online)
Journal Volume
42
Journal Issue
43
Journal Page Range
[6 p.]
ISSN
1751-8121

INIS

Country of Publication
United Kingdom
Country of Input or Organization
International Atomic Energy Agency (IAEA)
INIS RN
41054208
Subject category
S07: ISOTOPES AND RADIATION SOURCES; S97: MATHEMATICAL METHODS AND COMPUTING;
Descriptors DEI
COMPARATIVE EVALUATIONS; EFFICIENCY; GRAPH THEORY; LENGTH; RANDOMNESS
Descriptors DEC
DIMENSIONS; EVALUATION; MATHEMATICS