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:
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.