[SeqFan] Finding functions that produce periodic sequences.

[Antti Karttunen]

Cheers,

any ideas how to find unary f(x) or binary f(x,y) functions
with integer arguments, so that they produce periodic
sequences like [A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,...]
when supplied with arguments x = g^n mod p, and y=p
(for case f(x,y)), where p is a prime, and g is one of
its generators, and an integer n grows from 1 onward.

We have an example in Legendre symbol L(n/p), which,
when supplied with for example prime 11 and the successive
powers of its generator 2 gives the sequence
http://www.research.att.com/projects/OEIS?Anum=A033999
-1,+1,-1,+1,-1,+1,-1,+1,-1,+1,-1,+1,-1,...
(i.e. L(2/11), L(4/11), L(8/11), L(5/11), L(10/11), L(9/11), L(7/11), 
L(3/11), L(6/11), L(1/11), and then again L(2/11), L(4/11), ...,
you can check this from
http://www.research.att.com/projects/OEIS?Anum=A011582 )

This is the specific reason one should not "commit oneself"
to the least significant bit of the plaintext "n",
when using Diffie-Hellman key-exhange.

Now, if we could find a "simple" function that produced
a 4-periodic sequence:
[A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,...]
or even
[A,A,B,B,A,A,B,B,A,A,B,B,A,A,B,B,...]
we would have a nice method of finding ALSO the
next-to-least-significant bit of the plaintext
(from the ciphertext) in Diffie-Hellman exchange.
(By "simple" I mean something not involving explicit
computing of the discrete logarithm).


Terveisin,

Antti Karttunen

PS. Is Simon Colton still on this list? I remember he had
interesting ideas concerning OEIS "data mining". Any progress
there?