Consider straight-line algorithms over a Finite Field with elements. Then the -straight line complexity of a function is defined as the length of the shortest straight-line algorithm which computes a function such that is satisfied for at least elements of . A function is straight-line ``one way'' of range if satisfies the properties:

- 1. There exists an infinite set of finite fields such that is defined in every and is One-to-One in every .
- 2. For every such that , tends to infinity as the cardinality of approaches infinity.
- 3. For every such that
, the ``work function'' satisfies

**References**

Ziv, J. ``In Search of a One-Way Function'' §4.1 in
*Open Problems in Communication and Computation* (Ed. T. M. Cover and B. Gopinath).
New York: Springer-Verlag, pp. 104-105, 1987.

© 1996-9

1999-05-26