Information Technology Reference
In-Depth Information
For g
R, with c =0 , we have
g = 1 b
01
,
and
ρ ( g )= M b .
A.5
Pseudocode
Below, is given a pseudo-code description of the construction of the oscillator
system.
1. Choose a prime p.
2. Compute generator g A for the standard torus A .
3. Diagonalize ρ ( g A ) and obtain the basis
B A .
4. For every g
R :
5. Compute the operator ρ ( g ) as follows:
(a) Calculate the Bruhat decomposition of g ,namely,write g in the form
g = u 2 ·
a .
(b) Calculate the operator ρ ( g ), namely, take ρ ( g )= M u 2
a
·
w
·
u 1 or g = u
·
S a
F
M u 1 or
S a .
6. Compute the vectors ρ ( g ) ϕ , for every ϕ
ρ ( g )= M u
∈B A and obtain the basis
B gAg 1 .
Remark 3 (Running time). It is easy to verify that the time complexity of the al-
gorithm presented above is O ( p 4 log p ). This is, in fact, an optimal time complex-
ity, since already to specify p 3 vectors, each of length p ,requires p 4 operations.
Remark about field extensions. All the results in this survey were stated for
the basic finite field
F p for the reason of making the terminology more accessible.
However, they are valid for any field extension of the form
F q with q = p n .
Complete proofs appear in [6].
Acknowledgement. The authors would like to thank J. Bernstein for his in-
terest and guidance in the mathematical aspects of this work. We are grateful
to S. Golomb and G. Gong for their interest in this project. We appreciate the
many talks we had with A. Sahai. We thank B. Sturmfels for encouraging us
to proceed in this line of research. We would like to thank V. Anantharam, A.
Grunbaum for interesting conversations. Finally, the second author is indebted
to B. Porat for so many discussions where each tried to understand the cryptic
terminology of the other.
References
1. Golomb, S.W., Gong, G.: Signal design for good correlation. For wireless communi-
cation, cryptography, and radar. Cambridge University Press, Cambridge (2005)
2. Howard, S.D., Calderbank, A.R., Moran, W.: The finite Heisenberg-Weyl groups in
radar and communications. EURASIP J. Appl. Signal Process (2006)
Search WWH ::




Custom Search