Abstract
Here, first of all, the authors investigated power Fibonacci sequence modulo k and formulas for the periods of these sequences, based on the period of the Fibonacci sequence modulo k. And then, the authors described a new power sequence for positive integer modulus. They named these sequences power Pell sequences modulo k. After that the authors determined those positive integer moduli for which this sequence exists and the number of such sequences for a given modulo k. In addition, the authors provide formulas for the periods of these sequences, based on the period of the Pell sequence modulo k, and they studied sequence/subsequence relationships between power Pell sequences. Finally, the authors examined ElGamal cryptosystem which is one of the asymmetric cryptographic systems and ElGamal cryptosystem which is obtained by using some power sequences. And they obtained asymmetric cryptographic applications by using power Pell sequences which the authors described.
TopIntroduction
The Fibonacci sequence, , is a sequence of numbers, beginning with the integer couple 0 and 1, in which the value of any element is computed by taking the summation of the two antecedent numbers. If so, for , (Koshy, 2001). The first eight terms of this sequence are .
There have been many studies in the literature dealing with the Fibonacci sequences. Some authors obtained generalization of the Fibonacci sequence by changing only the first two terms of the sequence or with minor changes only the recurrence relation, while others obtained generalizations of the Fibonacci sequence by changing both of them. In addition, the Fibonacci sequence has come to the fore for centuries, as it seems there is no end to its many surprising properties. It is seen that the popular number sequence has been found to have important properties when the sequence reduced under a modulus. It is well known, the Fibonacci sequence and the other sequences which is obtained by changing the recurrence relation or the first two terms of Fibonacci sequence under a modulus is periodic. denote the period of the Fibonacci sequence modulo , formulas are known for computing based on the prime factorization of . But if is prime number, there is no formula for . On the other hand, some equations are provided. For example, if is prime number and if , and if , (Renault, 2013).
In this study, the authors used Pell sequence which is obtained by changing only the recurrence relation of Fibonacci sequence, power Fibonacci sequence modulo , the relationship of periods of these sequences as material. These structures the authors used in this article are introduced as follows:
Definition 1. The Pell sequence is defined recursively by the equation for , where and (Koshy, 2001).
Key Terms in this Chapter
Generator: It is an element in the group in which all the different powers of that element give all the different elements of the group.
Cryptography: It is a process of protecting information and communications such that the only one for whom the information is intended can understand.
One Way Function: It is a function that is easy to compute on every input, but it is hard to invert given the image of a random input.
Cyclic Group: It is a group which is generated the only one element.
Recurrence Sequences: Recurrence sequence is a sequence of numbers indexed by an integer and generated by solving a recurrence equation.
Quadratic Residue: An integer is called a quadratic residue modulo if there exists an integer such that .
Fibonacci Sequence: It is a recurrence sequence that beginning with the integer couple 0 and 1, in which the value of any element is computed by taking the summation of the two antecedent numbers.
Power Fibonacci Sequence Modulo: If a sequence that satisfying the Fibonacci recurrence relation also provides for some modulus , then this sequence is named a power Fibonacci sequence modulo .
Period: The period of a sequence is the number of terms within the repeated part of a sequence.
Trapdoor: It is special information which is used to find inverse.
Pell Sequence: It is a recurrence sequence that beginning with the integer couple 0 and 1, in which the value of any element is computed by taking the summation of twice the previous term and two previous terms.