next up previous
Next: Algorithms for repeated squaring Up: Contents Previous: Contents

Computational problems

A computational problem is defined by specifying how the output relates (mathematically) to the output.

Example: modular inverse problem

input: modulus m, standard name b
output: standard name c such that tex2html_wrap_inline65

Example: modular cube problem

input: modulus m, standard name b
output: standard name c such that tex2html_wrap_inline73

Example: modular exponentiation problem

input: modulus m, standard name b, positive integer k
output: standard name c such that

displaymath83

An instance of a computational problem is an assignment of numbers to the inputs to the problem.

Example: an instance of the modular inverse problem is ``the inverse of 160 modulo 937971''



Lisa Eckstein
Tue Oct 22 00:20:45 EDT 1996